Submission #157465

#TimeUsernameProblemLanguageResultExecution timeMemory
157465combi1k1Street Lamps (APIO19_street_lamps)C++14
0 / 100
106 ms72228 KiB
#include<bits/stdc++.h> using namespace std; #define ll long long #define X first #define Y second #define pb push_back #define sz(x) x.size() #define all(x) x.begin(),x.end() const int N = 3e5 + 1; typedef pair<int,int> ii; typedef pair<int,ii> pii; namespace BIT { vector<int> val[N]; vector<int> tr1[N]; vector<int> tr2[N]; vector<int> tr3[N]; void ini() { for(int i = 1 ; i < N ; ++i) { sort(all(val[i])); val[i].resize(unique(all(val[i])) - val[i].begin()); tr1[i].resize(sz(val[i]) + 1); tr2[i].resize(sz(val[i]) + 1); tr3[i].resize(sz(val[i]) + 1); } } void add(int x,int y) { for(; x > 0 ; x -= x & -x) val[x].push_back(y); } void upd(int x,int y,int v) { //v < 0 -> turn off, v > 0 -> turn on for(; x > 0 ; x -= x & -x) { int p = lower_bound(all(val[x]),y) - val[x].begin() + 1; for(; p > 0 ; p -= p & -p) { tr1[x][p] += v; if (v < 0) tr2[x][p] = max(tr2[x][p],-v); if (v > 0) tr3[x][p] = max(tr3[x][p], v); } } } int get(int x,int y,int i) { int ans = 0; int lef = 0; //latest time interval [x,y] CANNOT be covered + 1 int rig = 0; //latest time interval [x,y] CAN be covered + 1 for(; x < N ; x += x & -x) { int p = lower_bound(all(val[x]),y) - val[x].begin() + 1; for(; p <= val[x].size() ; p += p & -p) ans += tr1[x][p], lef = max(lef,tr2[x][p]), rig = max(rig,tr3[x][p]); } if (rig < lef) ans += i; return ans; } }; bool on[N]; set<ii> S; vector<pii> Q[N]; int l[N]; int r[N]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin >> n; int q; cin >> q; ++q; S.insert({-1,-1}); for(int i = 1 ; i <= n ; ++i) { char c; cin >> c; if (c == '1') { ii it = (*--S.end()); if (it.Y == i - 1) S.erase(it); else it.X = i; S.insert({it.X,i}); on[i] = 1; } } S.insert({n + 2,n + 2}); for(ii e : S) if (1 <= e.X && e.Y <= n) Q[1].pb(pii(1,e)); string t; for(int i = 2 ; i <= q ; ++i) { int x, y; cin >> t >> x; if (t == "query") { cin >> y; l[i] = n - x + 1; r[i] = y - 1; continue; } if (on[x]) { ii it = (*--S.upper_bound({x,x})); if (it.X < x) S.insert({it.X,x - 1}), Q[i].pb(pii(1,{it.X,x - 1})); if (it.Y > x) S.insert({x + 1,it.Y}), Q[i].pb(pii(1,{x + 1,it.Y})); S.erase(it); Q[i].pb(pii(0,it)); } if(!on[x]) { auto L = S.upper_bound({x,x}); auto R = L--; int l = x; int r = x; if ((*R).X == x + 1) { r = (*R).Y; S.erase(R); Q[i].pb(pii(0,*R)); } if ((*L).Y == x - 1) { l = (*L).X; S.erase(L); Q[i].pb(pii(0,*L)); } S.insert({l,r}); Q[i].pb(pii(1,{l,r})); } on[x] ^= 1; } for(int i = 1 ; i <= q ; ++i) for(pii t : Q[i]) BIT::add(n - t.Y.X + 1,t.Y.Y); BIT::ini(); Q[1].pb(pii(1,{n + 1,0})); for(int i = 1 ; i <= q ; ++i) { if (Q[i].empty()) cout << BIT::get(l[i],r[i],i) << "\n"; for(pii t : Q[i]) { int x = -t.Y.X + n + 1; int y = t.Y.Y; if (t.X) BIT::upd(x,y,-i); if(!t.X) BIT::upd(x,y, i); } } }

Compilation message (stderr)

street_lamps.cpp: In function 'int BIT::get(int, int, int)':
street_lamps.cpp:52:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(; p <= val[x].size() ; p += p & -p)
                   ~~^~~~~~~~~~~~~~~~
#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...