Submission #158307

#TimeUsernameProblemLanguageResultExecution timeMemory
158307combi1k1Street Lamps (APIO19_street_lamps)C++14
20 / 100
1904 ms524292 KiB
#include<bits/stdc++.h> using namespace std; #define X first #define Y second #define pb emplace_back #define mt make_tuple #define sz(x) x.size() #define all(x) x.begin(),x.end() #define ops tuple<int,int,int> const int N = 3e5 + 1; typedef pair<int,int> ii; namespace BIT { vector<int> val[N]; vector<int> bit[N]; void ini() { for(int i = 1 ; i < N ; ++i) { sort(all(val[i])); val[i].resize(unique(all(val[i])) - val[i].begin()); bit[i].resize(sz(val[i]) + 5); } } void add(int x,int y) { for(; x < N ; x += x & -x) val[x].push_back(y); } void upd(int x,int y,int v) { //v < 0 -> turn on, v > 0 -> turn off for(; x < N ; x += x & -x) { int p = lower_bound(all(val[x]),y) - val[x].begin() + 1; for(; p > 0 ; p -= p & -p) bit[x][p] += v; } } int get(int x,int y) { int X = x, Y = y; int ans = 0; for(; x > 0 ; x -= x & -x) { int p = lower_bound(all(val[x]),y) - val[x].begin() + 1; int K = sz(bit[x]); for(; p < K ; p += p & -p) ans += bit[x][p]; } return ans; } }; bool on[N]; set<ii> S; vector<ops> 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(1,e.X,e.Y); string t; for(int i = 2 ; i <= q ; ++i) { int x, y; cin >> t >> x; if (t == "query") { cin >> y; l[i] = x; r[i] = y - 1; continue; } if (on[x]) { auto it = S.upper_bound({x,x}); ii range = (*--it); int L = range.X; int R = range.Y; if (L < x) S.insert({L,x - 1}), Q[i].pb(1,L,x - 1); if (R > x) S.insert({x + 1,R}), Q[i].pb(1,x + 1,R); S.erase(range); Q[i].pb(0,L,R); } 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(0,x + 1,r); } if ((*L).Y == x - 1) { l = (*L).X; S.erase(L); Q[i].pb(0,l,x - 1); } S.insert({l,r}); Q[i].pb(1,l,r); } on[x] ^= 1; } for(int i = 1 ; i <= q ; ++i) for(ops _ : Q[i]) { int v, x, y; tie(v, x, y) = _; BIT::add(x,y); } BIT::ini(); Q[1].pb(1,N,0); for(int i = 1 ; i <= q ; ++i) { if (Q[i].empty()) { int ans = BIT::get(l[i],r[i]); if (ans < 0) ans += i; cout << ans << "\n"; } for(ops _ : Q[i]) { int v, x, y; tie(v, x, y) = _; if (v) BIT::upd(x,y,-i); else BIT::upd(x,y, i); } } } /* 5 7 11011 query 1 2 query 1 2 query 1 6 query 3 4 toggle 3 query 3 4 query 1 6 */

Compilation message (stderr)

street_lamps.cpp: In function 'int BIT::get(int, int)':
street_lamps.cpp:5:17: warning: unused variable 'first' [-Wunused-variable]
 #define X       first
                 ^
street_lamps.cpp:40:13: note: in expansion of macro 'X'
         int X = x, Y = y;
             ^
street_lamps.cpp:6:17: warning: unused variable 'second' [-Wunused-variable]
 #define Y       second
                 ^
street_lamps.cpp:40:20: note: in expansion of macro 'Y'
         int X = x, Y = y;
                    ^
#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...