제출 #1095277

#제출 시각아이디문제언어결과실행 시간메모리
1095277mohammad86새로운 문제 (POI11_met)C++14
0 / 100
6063 ms20048 KiB
#include <bits/stdc++.h> using namespace std; typedef pair<int, int> pii; typedef long long ll; const int maxn = 3e5 +100; const int k = 550; int n, m, q; pair<pii, int> queries[maxn]; vector<int> segments[maxn]; int o[maxn]; ll p[maxn]; ll p1[maxn]; bool mark[maxn]; int ans[maxn]; ll add[maxn]; int IndToGroup(int index) { return (index-1)/k +1; } int Sgroup(int gr) { return (gr-1) * k +1; } int Fgroup(int gr) { return min(gr * k, q); } void calAns(int x, int gr) { int val = p1[x]; int start = Sgroup(gr); int finish = Fgroup(gr); for (int s : segments[x]) { for (int i = start; i <= finish; i++) { int l = queries[i].first.first; int r = queries[i].first.second; int a = queries[i].second; if (l <= r) { if (l <= s && s <= r) { val -= a; if (val <= 0) { ans[x] = i; mark[x] = true; return; } } } else { if (s <= l) { val -= a; if (val <= 0) { ans[x] = i; mark[x] = true; return; } } else if (s >= r) { val -= a; if (val <= 0) { ans[x] = i; mark[x] = true; return; } } } } } } void update(int last) { int gr = IndToGroup(last); for (int i = 1; i <= m; i++) { add[i] = 0; } for (int i = 1; i <= n; i++) { p1[i] = p[i]; } for (int i = Sgroup(gr); i <= last; i++) { int l = queries[i].first.first; int r = queries[i].first.second; int a = queries[i].second; if (r >= l) { add[l] += a; add[r+1] -= a; } else { add[1] += a; add[r+1] -= a; add[l] += a; add[m+1] -= a; } } ll cnt = 0; for (int i = 1; i <= m; i++) { cnt += add[i]; p[o[i]] -= cnt; } for (int i = 1; i <= n; i++) { if (p[i] <= 0 && !mark[i]) { calAns(i, gr); } } } int main () { ios_base::sync_with_stdio(false); cin >> n >> m; for (int i = 1; i <= m; i++) { cin >> o[i]; segments[o[i]].push_back(i); } for (int i = 1; i <= n; i++) { cin >> p[i]; } cin >> q; int last_gr = 1; for (int i = 1; i <= q; i++) { int gr = IndToGroup(i); if (last_gr != gr) { update(i -1); } int l, r, a; cin >> l >> r >> a; queries[i] = {{l, r}, a}; } update(q); for (int i = 1; i <= n; i++) { if (ans[i] == 0) { cout << "NIE" << endl; } else { cout << ans[i] << endl; } } }
#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...