Submission #1203003

#TimeUsernameProblemLanguageResultExecution timeMemory
1203003agrim_09Meteors (POI11_met)C++20
In queue
0 ms0 KiB
// #pragma GCC optimize("O3,unroll-loops") // #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> using namespace std; using namespace __gnu_pbds; template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; #define endl '\n'; #define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); #define py cout << "YES" << endl; #define pn cout << "NO" << endl; #define all(x) (x).begin(), (x).end() #define pb push_back #define int long long typedef long long ll; typedef unsigned long long ull; const ll inf = 1e18; const ll mod = 1e9+7; // #ifndef ONLINE_JUDGE // #include "algo/Standard_Stuff/debug.cpp" // #else // #define debug(...) 42 // #endif // void judge(){ // srand(time(NULL)); // #ifndef ONLINE_JUDGE // freopen("1.txt","r",stdin); // freopen("2.txt","w",stdout); // #endif // } #pragma once template <typename T> struct BinaryIndexedTree { int N; vector<T> data; BinaryIndexedTree() = default; BinaryIndexedTree(int size) { init(size); } void init(int size) { N = size + 2; data.assign(N + 1, {}); } // get sum of [0,k] T sum(int k) const { if (k < 0) return T{}; // return 0 if k < 0 T ret{}; for (++k; k > 0; k -= k & -k) ret += data[k]; return ret; } // getsum of [l,r] inline T sum(int l, int r) const { return sum(r) - sum(l - 1); } // get value of k inline T operator[](int k) const { return sum(k) - sum(k - 1); } // data[k] += x void add(int k, T x) { for (++k; k < N; k += k & -k) data[k] += x; } // range add x to [l,r] void imos(int l, int r, T x) { add(l, x); add(r + 1, -x); } // minimize i s.t. sum(i) >= w }; /** * @brief Binary Indexed Tree(Fenwick Tree) * @docs docs/data-structure/binary-indexed-tree.md */ struct query{ int l,r,val; }; // Look for edge cases!!! signed main(){ fastio; //judge(); int n,m; cin >> n >> m; vector<int>a(m),target(n); vector<vector<int>> stations(n); for(int i = 0;i<m;i++){ cin >> a[i]; a[i]--; stations[a[i]].pb(i); } for(auto &x : target) cin >> x; int q; cin >> q; vector<query>queries(q); for(auto &[x,y,z]:queries){ cin >> x >> y >> z; x--; y--; } vector<int>ans(n,-1),left(n,0),right(n,q-1); int tmp_max_val = 10; while(true){ vector<vector<int>>to_check(q); bool all_answered = true; for(int i = 0;i<n;i++){ if(left[i]>right[i]){ continue; } all_answered = false; to_check[(left[i]+right[i])/2].pb(i); } if(all_answered){ break; } BinaryIndexedTree<int>bit(m); for(int i = 0;i<q;i++){ int lx = queries[i].l, rx = queries[i].r, cnt = queries[i].val; bit.add(lx, cnt); if(lx<=rx){ if(rx+1!=m){ bit.add(rx+1,-1*cnt); } } else{ bit.add(0,cnt); if(rx+1!=m){ bit.add(rx+1,-1*cnt); } } for(auto state : to_check[i]){ int sum = 0; for(auto idx : stations[state]){ sum += bit.sum(idx); } if(sum>=target[state]){ ans[state] = i+1; right[state] = i-1; } else{ left[state] = i+1; } } } } for(auto x : ans){ if(x==-1){ cout << "NIE" << endl; } else{ cout << x << endl; } } }