Submission #347715

#TimeUsernameProblemLanguageResultExecution timeMemory
347715jesus_coconutMeteors (POI11_met)C++17
0 / 100
200 ms35840 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; struct st{ int l, r; ll x; }; int const N = 300010; vector<int> own[N]; st q[N]; ll mx[N]; template<class T> struct BIT{ vector<T> bit; BIT(int N) : bit(N, 0) {} void add(int pos, T val) { for (; pos < (int) bit.size(); pos += pos & -pos) { bit[pos] += val; } } T sum(int r) { T res{}; for (; r > 0; r -= r & -r) { res += bit[r]; } return res; } T sum(int l, int r) { return sum(r) - sum(l - 1); } }; int sol[N]; BIT<ll> bit(1); void add(int i, int p) { if (q[i].l <= q[i].r) { bit.add(q[i].l, q[i].x * p); bit.add(q[i].r + 1, -q[i].x * p); } else { bit.add(1, q[i].x * p); bit.add(q[i].r + 1, -q[i].x * p); bit.add(q[i].l, q[i].x * p); } } void solve(int lo, int hi, vector<int> const &ind) { if (lo == hi) { for (int i : ind) { sol[i] = lo; } return; } int mid = (lo + hi) / 2; for (int i = lo; i <= mid; ++i) { add(i, 1); } vector<int> l, r; for (int i : ind) { ll suma = 0; for (int a : own[i]) { suma += bit.sum(a); if (suma >= mx[i]) break; } if (suma >= mx[i]) { l.push_back(i); } else r.push_back(i); } solve(mid + 1, hi, r); for (int i = lo; i <= mid; ++i) { add(i, -1); } solve(lo, mid, l); } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; bit.bit.resize(n + 10); for (int i = 1; i <= m; ++i) { int a; cin >> a; own[a].push_back(i); } for (int i = 1; i <= n; ++i) { cin >> mx[i]; } int k; cin >> k; for (int i = 1; i <= k; ++i) { cin >> q[i].l >> q[i].r >> q[i].x; } vector<int> tmp(n); iota(begin(tmp), end(tmp), 1); solve(1, k + 1, tmp); for (int i = 1; i <= n; ++i) { if (sol[i] > k) { cout << "NIE\n"; } else cout << sol[i] << '\n'; } 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...