Submission #1089405

#TimeUsernameProblemLanguageResultExecution timeMemory
1089405Mike_VuMeteors (POI11_met)C++14
74 / 100
934 ms31376 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef long double dou; #define pii pair<int, int> #define fi first #define se second #define pb push_back #define BITj(x, j) (((x)>>(j))&1) #define MASK(x) (1LL<<(x)) template<typename T> bool maximize(T &x, const T &y) { if (x < y) {x = y; return 1;} return 0; } template<typename T> bool minimize(T &x, const T &y) { if (x > y) {x = y; return 1;} return 0; } struct BIT{ int n; vector<ll> bit; BIT(int _n = 0) { n = _n; bit.assign(n+1, 0); } void upd(int k, int val) { while (k <= n) { bit[k] += val; k += k & (-k); } } void update(int l, int r, int val) { if (l <= r){ upd(l, val); upd(r+1, -val); } else { upd(1, val); upd(r+1, -val); upd(l, val); } } ll query(int k) { ll ans = 0; while (k > 0) { ans += bit[k]; k -= k & (-k); } return ans; } } bit; struct prediction{ int l, r, val; prediction(int _l, int _r, int _val){ l = _l; r = _r; val = _val; } }; const int maxn = 3e5+5; int n, m, k; vector<int> states[maxn]; vector<prediction> pred; int goal[maxn]; int l[maxn], r[maxn], mid[maxn], ans[maxn]; vector<int> still; bool cmp(int a, int b) { return mid[a] < mid[b]; } void input() { cin >> n >> m; for (int i = 1; i <= m; i++) { int x; cin >> x; states[x].pb(i); } for (int i = 1; i <= n; i++) { cin >> goal[i]; } cin >> k; for (int i = 1; i <= k; i++) { int l, r, val; cin >> l >> r >> val; pred.push_back(prediction(l, r, val)); } } void parallel_binsearch() { //init for (int i = 1; i <= n; i++) { l[i] = 1; r[i] = k; } while (true) { int coustill = 0; still.clear(); for (int i = 1; i <= n; i++) { if (l[i] <= r[i]) { mid[i] = (l[i]+r[i])>>1; ++coustill; still.push_back(i); } } if (coustill == 0) break; bit = BIT(m); sort(still.begin(), still.end(), cmp); int j = 0; for (int i = 0; i < k; i++) { bit.update(pred[i].l, pred[i].r, pred[i].val); // cout << pred[i].l<< ' ' << pred[i].r<< ' ' << pred[i].val << "\n"; while (j < (int)still.size() && mid[still[j]] == i+1) { int id = still[j++]; // cout << id << ' ' << l[id] << ' ' << r[id] << ' ' << mid[id] << ' '; ll sum = 0; for (int station : states[id]) { sum += bit.query(station); } // cout << sum << "\n"; if (sum >= goal[id]) { ans[id] = mid[id]; r[id] = mid[id]-1; } else l[id] = mid[id]+1; // cout << l[id] << ' ' << r[id] << "\n"; } if (j == (int)still.size()) break; } // cout << "\n"; } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); // #define name "task" // if (fopen(name".inp", "r")) { // freopen(name".inp", "r", stdin); // freopen(name".out", "w", stdout); // } input(); memset(ans, -1, sizeof(ans)); parallel_binsearch(); //cout for (int i = 1; i <= n; i++) { if (ans[i] == -1) cout << "NIE"; else cout << ans[i]; cout << "\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...