Submission #197108

#TimeUsernameProblemLanguageResultExecution timeMemory
197108AnaiStreet Lamps (APIO19_street_lamps)C++14
20 / 100
709 ms90236 KiB
#include <bits/stdc++.h> #define x first #define y second using namespace std; using pii = pair<int, int>; const int N = 3e5 + 5; struct Iv { int st, dr, val; }; struct Query { int st, dr, idx; }; struct Update { int pos, idx; }; class SegTree { struct Nod { int st, dr; int lazy, sum; }; vector<Nod> acc; int pom[N * 5]; int ql, qr, qval, qh; int make_nod() { acc.push_back({0, 0, 0, 0}); return acc.size() - 1; } void prop(int nod, int st, int dr) { if (acc[nod].st == 0) acc[nod].st = make_nod(); if (acc[nod].dr == 0) acc[nod].dr = make_nod(); acc[nod].sum+= acc[nod].lazy * (dr - st + 1); acc[acc[nod].st].lazy+= acc[nod].lazy; acc[acc[nod].dr].lazy+= acc[nod].lazy; acc[nod].lazy = 0; } int eval(int nod, int st, int dr) { return acc[nod].sum + (dr - st + 1) * acc[nod].lazy; } int update_deep(int nod, int st, int dr) { if (nod == 0) nod = make_nod(); if (ql <= st && dr <= qr) { acc[nod].lazy+= qval; return nod; } int mid = (st + dr) / 2; prop(nod, st, dr); if (ql <= mid) acc[nod].st = update_deep(acc[nod].st, st, mid); if (mid < qr) acc[nod].dr = update_deep(acc[nod].dr, mid + 1, dr); acc[nod].lazy = 0; acc[nod].sum = eval(acc[nod].st, st, mid) + eval(acc[nod].dr, mid + 1, dr); return nod; } void update_shallow(int nod, int st, int dr) { pom[nod] = update_deep(pom[nod], 0, N); if (st == dr) return; int mid = (st + dr) / 2; if (qh <= mid) update_shallow(2 * nod, st, mid); else update_shallow(2 * nod + 1, mid + 1, dr); } pii query_deep(int nod, int st, int dr) { if (nod == 0) nod = make_nod(); if (ql <= st && dr <= qr) return pii(nod, eval(nod, st, dr)); int mid = (st + dr) / 2, ans = 0; prop(nod, st, dr); if (ql <= mid) { pii ret = query_deep(acc[nod].st, st, mid); acc[nod].st = ret.x; ans+= ret.y; } if (mid < qr) { pii ret = query_deep(acc[nod].dr, mid + 1, dr); acc[nod].dr = ret.x; ans+= ret.y; } return pii(nod, ans); } int query_shallow(int nod, int st, int dr) { if (st > qh) return 0; if (dr <= qh) return query_deep(pom[nod], 0, N).y; int ans = 0, mid = (st + dr) / 2; ans+= query_shallow(2 * nod, st, mid); ans+= query_shallow(2 * nod + 1, mid + 1, dr); return ans; } public: void update(int st, int dr, int h, int val) { ql = st, qr = dr, qh = h, qval = val; update_shallow(1, 0, N); } int query(int st, int dr, int h) { ql = st, qr = dr, qh = h; return query_shallow(1, 0, N); } SegTree() { acc.reserve(N * 8); acc.push_back({0, 0, 0, 0}); } }; inline bool operator < (const Iv &a, const Iv &b) { return a.st < b.st; } vector<int> upd; char str[N]; int ans[N]; set<Iv> s; vector<Query> qs; vector<Update> ups; SegTree magic; int n, q; static void apply(int newh, int st, int dr) { if (st > dr) return; auto it = prev(s.upper_bound(Iv {st, st, st})); Iv fst, lst; fst = lst = *it; for (; it != end(s) && it->st <= dr;) { lst = *it; auto inc = next(it); magic.update(it->st, it->dr, it->val, -1); s.erase(it); it = inc; } magic.update(st, dr, newh, 1); s.insert(Iv {st, dr, newh}); if (fst.st <= st - 1) { magic.update(fst.st, st - 1, fst.val, 1); s.insert(Iv {fst.st, st - 1, fst.val}); } if (dr + 1 <= lst.dr) { magic.update(dr + 1, lst.dr, lst.val, 1); s.insert(Iv {dr + 1, lst.dr, lst.val}); } } int main() { #ifdef HOME freopen("streetlights.in", "r", stdin); freopen("streetlights.out", "w", stdout); #endif ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); int ptru(0), ptrq(0); cin >> n >> q >> (str + 1); upd.reserve(2 * N); qs.reserve(N); for (int i = 1; i <= q; ++i) { string op; cin >> op; if (op == "query") { int l, r; cin >> l >> r; qs.push_back({l, r - 1, i}); } else { int pos; cin >> pos; ups.push_back({pos, i}); } } for (int i = 1; i <= n; ++i) if (str[i] == '0') ups.push_back({i, 0}); sort(begin(qs), end(qs), [&](const Query &a, const Query &b) { return pii(a.dr, a.idx) < pii(b.dr, b.idx); }); sort(begin(ups), end(ups), [&](const Update &a, const Update &b) { return pii(a.pos, a.idx) < pii(b.pos, b.idx); }); s.insert(Iv {0, q, 1}); magic.update(0, q, 1, 1); for (int i = 1; i <= n; ++i) { vector<pii> upd; bool par = true; int lst_tid = -1; while (ptru < ups.size() && ups[ptru].pos <= i) { upd.emplace_back(lst_tid + 1, ups[ptru].idx); lst_tid = ups[ptru].idx; ptru+= 1; } upd.emplace_back(lst_tid + 1, q); for (int j = 1; j < upd.size(); j+=2) { apply(i + 1, upd[j].x, upd[j].y); } while (ptrq < qs.size() && qs[ptrq].dr <= i) { ans[qs[ptrq].idx] = magic.query(1, qs[ptrq].idx, qs[ptrq].st); ptrq+= 1; } } sort(begin(qs), end(qs), [&](const Query &a, const Query &b) { return a.idx < b.idx; }); for (auto i: qs) cout << ans[i.idx] << '\n'; return 0; }

Compilation message (stderr)

street_lamps.cpp: In function 'int main()':
street_lamps.cpp:205:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while (ptru < ups.size() && ups[ptru].pos <= i) {
                ~~~~~^~~~~~~~~~~~
street_lamps.cpp:212:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 1; j < upd.size(); j+=2) {
                         ~~^~~~~~~~~~~~
street_lamps.cpp:216:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while (ptrq < qs.size() && qs[ptrq].dr <= i) {
                ~~~~~^~~~~~~~~~~
street_lamps.cpp:202:14: warning: unused variable 'par' [-Wunused-variable]
         bool par = true;
              ^~~
#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...