Submission #1015684

#TimeUsernameProblemLanguageResultExecution timeMemory
1015684vjudge1Meteors (POI11_met)C++17
24 / 100
185 ms65536 KiB
#include<bits/stdc++.h> using namespace std; #define ll long long #define endl '\n' #define FF first #define SS second #define all(a) a.begin(), a.end() #define mod (ll)(1000000007) int n, m, q, time_; int sum; struct Kind { int L, R; int Cur = 0; }; vector<Kind> V(3e6); int update(int id, int u, int v, int c, int l, int r) { if (l > v || r < u) { return id; } if (!id && !(l == 1 && r == m)) { id = time_++; } if (u <= l && r <= v) { int temp = time_++; V[temp].L = V[id].L; V[temp].R = V[id].R; V[temp].Cur = min(V[id].Cur + c, (int)1e9); return temp; } int md = (l + r) / 2; int temp = time_++; V[temp].L = update(V[id].L, u, v, c, l, md + 0); V[temp].R = update(V[id].R, u, v, c, md + 1, r); V[temp].Cur = V[id].Cur; return temp; } void get(int id, int u, int v, int l, int r) { if (!id && !(l == 1 && r == m)) { id = time_++; } if (l > v || r < u) { return; } sum = min(sum + V[id].Cur, (int)1e9); if (l >= u && r <= v) { return; } int md = (l + r) / 2; get(V[id].L, u, v, l, md + 0), get(V[id].R, u, v, md + 1, r); } int main() { ios_base::sync_with_stdio(0);cin.tie(0); cin >> n >> m; vector<int> Ind[n + 1]; for (int i = 1; i <= m; i++) { int a; cin >> a; Ind[a].push_back(i); } int A[n + 1]; for (int i = 1; i <= n; i++) { cin >> A[i]; } vector<int> Head; cin >> q; int qq = q; while (qq--) { int l, r, x; cin >> l >> r >> x; if (l <= r) { Head.push_back(update((Head.empty() ? time_++ : Head.back()), l, r, x, 1, m)); } else { auto temp = update((Head.empty() ? time_++ : Head.back()), l, m, x, 1, m); Head.push_back(update(temp, 1, r, x, 1, m)); } } for (int i = 1; i <= n; i++) { int l = 0, r = Head.size() - 1, res = -1; while (l <= r) { int md = (l + r) / 2; auto cur = Head[md]; sum = 0; for (auto pos : Ind[i]) { get(cur, pos, pos, 1, m); } if (sum >= A[i]) { res = md, r = md - 1; } else { l = md + 1; } } if (res == -1) { cout << "NIE" << endl; } else { cout << res + 1 << 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...