Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <iomanip>
- #include <ctime>
- #include <cmath>
- #include <sstream>
- #include <complex>
- #include <fstream>
- #include <bitset>
- #include <chrono>
- #include <random>
- #include <fstream>
- #include <assert.h>
- #include <vector>
- #include <set>
- #include <map>
- #include <unordered_set>
- #include <unordered_map>
- #include <queue>
- #include <deque>
- #include <algorithm>
- #include <stack>
- #include <string>
- using namespace std;
- mt19937 rd(chrono::system_clock::now().time_since_epoch().count());
- typedef long long ll;
- typedef long double ld;
- const int INF = 1e9 + 5, M = 998244353, SIZE = 1.7e7;
- const ld eps = 1e-8;
- ll INF_LL = 1e18;
- /*#pragma GCC optimize("Ofast")
- #pragma GCC optimize("unroll-loops")
- #pragma GCC optimize("no-stack-protector")
- #pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native")
- #pragma GCC optimize("fast-math")*/
- struct Node {
- int add;
- int l, r;
- Node() {
- add = 0;
- l = r = -1;
- }
- };
- Node tree[SIZE];
- int tree_sz = 0;
- int add() {
- tree[tree_sz] = Node();
- tree_sz++;
- return tree_sz - 1;
- }
- int clone(int i) {
- tree[tree_sz] = tree[i];
- tree_sz++;
- return tree_sz - 1;
- }
- void build(int i, int L, int R) {
- if (L + 1 == R)
- return;
- int m = (L + R) >> 1;
- tree[i].l = add();
- tree[i].r = add();
- build(tree[i].l, L, m);
- build(tree[i].r, m, R);
- }
- int mod(int i, int L, int R, int l, int r, ll x) {
- if (r <= L || R <= l)
- return i;
- int v = clone(i);
- if (l <= L && R <= r) {
- if (tree[v].add > INF)
- return v;
- tree[v].add += x;
- return v;
- }
- int m = (L + R) >> 1;
- tree[v].l = mod(tree[v].l, L, m, l, r, x);
- tree[v].r = mod(tree[v].r, m, R, l, r, x);
- return v;
- }
- void get(int i, int L, int R, int ind, ll &ans) {
- ans += tree[i].add;
- if (L + 1 == R)
- return;
- int m = (L + R) >> 1;
- if (ind < m)
- get(tree[i].l, L, m, ind, ans);
- else
- get(tree[i].r, m, R, ind, ans);
- }
- int main() {
- #ifdef LOCAL
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #endif
- ios::sync_with_stdio(0);
- int n, m, k;
- cin >> n >> m;
- vector<int> v(1, 0);
- v[0] = add();
- build(0, 0, m);
- vector<vector<int>> se(m);
- for (int i = 0; i < m; i++) {
- int o;
- cin >> o;
- o--;
- se[o].push_back(i);
- }
- vector<ll> p(n);
- for (int i = 0; i < n; i++)
- cin >> p[i];
- cin >> k;
- for (int i = 0; i < k; i++) {
- int l, r, a;
- cin >> l >> r >> a;
- l--;
- if (l < r) {
- v.push_back(mod(v.back(), 0, m, l, r, a));
- }
- else {
- v.push_back(mod(v.back(), 0, m, l, m, a));
- v.back() = mod(v.back(), 0, m, 0, r, a);
- }
- }
- for (int i = 0; i < n; i++) {
- ll sum = 0;
- for (int j : se[i])
- get(v.back(), 0, m, j, sum);
- if (sum < p[i]) {
- cout << "NIE\n";
- continue;
- }
- int l = 0, r = v.size();
- while (l + 1 < r) {
- int mid = (l + r) >> 1;
- sum = 0;
- for (int j : se[i])
- get(v[mid], 0, m, j, sum);
- if (sum >= p[i]) {
- r = mid;
- }
- else {
- l = mid;
- }
- }
- cout << r << '\n';
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement