Submission #622271

#TimeUsernameProblemLanguageResultExecution timeMemory
622271jame0313Meteors (POI11_met)C++17
74 / 100
1816 ms32944 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using pii = pair<int, int>; using ld = long double; using pll = pair<ll, ll>; using tii = tuple<int, int, int>; // and so on int arr[300001]; ll goal[300001]; vector<vector<int> > lst, listeners; vector<tii> Event, query; struct bit { ll tree[1 << 21], siz; void init(int x) { for (siz = 1; siz < x; siz <<= 1) ; } void clear() { for (int i = 0; i <= siz; i++) tree[i] = 0; } void add(int pos, ll x) { while (pos <= siz) { tree[pos] += x; pos += (pos & -pos); } } ll sum(int pos) { ll ret = 0; while (pos) { ret += tree[pos]; pos &= (pos - 1); } return ret; } } Tree; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int Q, N, M; cin >> Q >> N; lst.resize(Q + 1); Tree.init(N + 5); for (int i = 1; i <= N; i++) { cin >> arr[i]; lst[arr[i]].push_back(i); } for (int i = 1; i <= Q; i++) { cin >> goal[i]; } cin >> M; listeners.resize(M + 1); for (int i = 0; i < M; i++) { int l, r, c; cin >> l >> r >> c; Event.push_back({l, r, c}); } for (int i = 0; i <= Q; i++) { query.push_back({0, M-1, 0}); } for (int t = 0; t < 32; t++) { Tree.clear(); for (int i = 1; i <= Q; i++) { auto& [l, r, m] = query[i]; if (l <= r) { m = (l + r) >> 1; listeners[m].push_back(i); } } for (int i = 0; i < M; i++) { auto [l, r, c] = Event[i]; if(l<=r){ Tree.add(l, c); Tree.add(r+1, -c); } else{ Tree.add(l, c); Tree.add(N+1, -c); Tree.add(1, c); Tree.add(r+1, -c); } for (int j : listeners[i]) { auto& [l, r, m] = query[j]; ll sum = 0; for (int k : lst[j]) sum += Tree.sum(k); if (sum < goal[j]) { l = m + 1; } else r = m - 1; } listeners[i].clear(); } } for (int i = 1; i <= Q; i++) { auto [l,r,m] = query[i]; if(l == M) cout<<"NIE\n"; else cout<<l+1<<'\n'; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...