제출 #1015646

#제출 시각아이디문제언어결과실행 시간메모리
1015646vjudge1새로운 문제 (POI11_met)C++17
24 / 100
117 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; ll sum; struct Kind { Kind *L, *R; ll Cur = 0; }; Kind *update(Kind *id, int u, int v, int c, int l, int r) { if (!id) { id = new Kind(); } if (l > v || r < u) { return id; } if (u <= l && r <= v) { Kind *temp = new Kind(); temp->L = id->L; temp->R = id->R; temp->Cur = id->Cur + c; return temp; } int md = (l + r) / 2; Kind *temp = new Kind(); temp->L = update(id->L, u, v, c, l, md + 0); temp->R = update(id->R, u, v, c, md + 1, r); temp->Cur = id->Cur; return temp; } void get(Kind *id, int u, int v, int l, int r) { if (!id) { id = new Kind(); } if (l > v || r < u) { return; } sum += id->Cur; if (l >= u && r <= v) { return; } int md = (l + r) / 2; get(id->L, u, v, l, md + 0), get(id->R, u, v, md + 1, r); } int main() { ios_base::sync_with_stdio(0);cin.tie(0); cin >> n >> m; vector<vector<int>> Ind(n + 1); for (int i = 1; i <= m; i++) { int a; cin >> a; Ind[a].push_back(i); } vector<int> A(n + 1); for (int i = 1; i <= n; i++) { cin >> A[i]; } vector<Kind*> 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() ? new Kind() : Head.back()), l, r, x, 1, m)); } else { auto temp = update((Head.empty() ? new Kind() : 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...