Submission #1226893

#TimeUsernameProblemLanguageResultExecution timeMemory
1226893nh0902Meteors (POI11_met)C++20
74 / 100
2565 ms87988 KiB
#include <bits/stdc++.h> using namespace std; #define int long long const int N = 3e5 + 10; const int M = 1e3 + 100; int n, m, k, p[N], l[N], r[N], a[N]; vector<int> stations[N]; int cur_l[N], cur_r[N], ans[N]; vector<int> cur[N]; // cur[i] : index k that had (cur_l + cur_r) / 2 = mid; //segment tree int st[4 * N]; void build(int id, int l, int r) { st[id] = 0; if (l == r) return; int mid = (l + r) / 2; build(id * 2, l, mid); build(id * 2 + 1, mid + 1, r); } void update(int id, int l, int r, int u, int v, int val) { if (r < u || v < l) return; if (u <= l && r <= v) { st[id] += val; return; } int mid = (l + r) / 2; update(id * 2, l, mid, u, v, val); update(id * 2 + 1, mid + 1, r, u, v, val); } void update(int l, int r, int val) { if (l <= r) update(1, 1, m, l, r, val); else { update(1, 1, m, l, m, val); update(1, 1, m, 1, r, val); } } int sum(int id, int l, int r, int p) { if (l == r) return st[id]; int mid = (l + r) / 2; if (p <= mid) return st[id] + sum(id * 2, l, mid, p); else return st[id] + sum(id * 2 + 1, mid + 1, r, p); } int sum(int i) { return sum(1, 1, m, i); } void prep() { cin >> n >> m; int x; for (int i = 1; i <= m; i ++) { cin >> x; stations[x].push_back(i); } for (int i = 1; i <= n; i ++) { cin >> p[i]; } cin >> k; for (int i = 1; i <= k; i ++) { cin >> l[i] >> r[i] >> a[i]; } for (int i = 1; i <= n; i ++) { cur_l[i] = 1; cur_r[i] = k + 1; } } bool check; void process() { build(1, 1, m); check = false; for (int i = 1; i <= k; i ++) cur[i].clear(); for (int i = 1; i <= n; i ++) { if (cur_l[i] < cur_r[i]) { cur[(cur_l[i] + cur_r[i]) / 2].push_back(i); check = true; } } if (!check) return; for (int i = 1; i <= k; i ++) { update(l[i], r[i], a[i]); for (int j : cur[i]) { int cnt = 0; for (int s : stations[j]) { cnt += sum(s); cnt = min(cnt, p[j]); } if (cnt >= p[j]) cur_r[j] = i; else cur_l[j] = i + 1; } } } void solve() { check = true; while (check) { process(); } for (int i = 1; i <= n; i ++) { //cout << cur_l[i] << "\n"; if (cur_l[i] <= k) cout << cur_l[i] << "\n"; else cout << "NIE\n"; } } signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); prep(); solve(); return 0; }
#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...