Submission #1236145

#TimeUsernameProblemLanguageResultExecution timeMemory
1236145KluydQStreet Lamps (APIO19_street_lamps)C++20
20 / 100
1122 ms120124 KiB
#include <bits/stdc++.h> #define respagold ios_base::sync_with_stdio(0), cin.tie(0); #define int long long #define ll long long #define int2 __int128_t #define FOR( i, x, n, d ) for( int i = x; i <= n; i += d ) #define FORR( i, x, n, d ) for( int i = x; i >= n; i -= d ) #define F first #define S second #define all(x) x.begin(), x.end() #define sz(x) (int)(x.size()) #define pb push_back #define ins insert #define lb lower_bound #define ub upper_bound #define pii pair <int, int> #define ppi pair <pair <int, int>, int> #define pip pair <int, pair <int, int>> #define mkp make_pair using namespace std; const int N = 3e5 + 123; const int inf = 2e9; const int mod = 1e9 + 7; const double eps = 1e-20; int n, m, x, y, k, z, w, a[N], b[N], ans[N], t[N][2]; string s; set <int> st; mt19937 rng( chrono::steady_clock::now().time_since_epoch().count()); int rand( int l, int r ) { uniform_int_distribution <int> uid( l, r ); return uid( rng ); } struct qu { int i, l, r, tp; }; vector <qu> q; void update( int p, int v, int tp ) { for(; p <= n; p |= (p + 1)) t[p][tp] += v; } int g1( int r, int tp ) { int res = 0; for(; r >= 0; r = (r & (r + 1)) - 1) res += t[r][tp]; return res; } int get( int l, int r, int tp ) { return g1(r, tp) - ( !l ? 0 : g1(l - 1, tp)); } void cdq( int l, int r ) { if( l >= r ) return; int md = l + r >> 1; cdq(l, md); cdq(md + 1, r); vector <qu> ql, qr, temp; vector <pii> c0, c1; FOR( i, l, md, 1 ) ql.pb(q[i]); FOR( i, md + 1, r, 1 ) qr.pb(q[i]); int u1 = 0, u2 = 0; while( u1 < sz(ql) || u2 < sz(qr) ) { if( u2 == sz(qr) || (u1 < sz(ql) && ql[u1].l <= qr[u2].l) ) { update( ql[u1].r, -ql[u1].tp, 1 ); update( ql[u1].r, ql[u1].i * ql[u1].tp, 0 ); c1.pb({ql[u1].r, -ql[u1].tp}); c0.pb({ql[u1].r, ql[u1].i * ql[u1].tp}); temp.pb(ql[u1]); u1 ++; } else { ans[qr[u2].i] += get(qr[u2].r, n, 0) + qr[u2].i * get(qr[u2].r, n, 1); // if( l == 0 && r == 5 && u2 == 0 ) cout << get(qr[u2].r, n, 0); temp.pb(qr[u2]); u2 ++; } } for( auto i : c0 ) update(i.F, -i.S, 0); for( auto i : c1 ) update(i.F, -i.S, 1); FOR( i, l, r, 1 ) q[i] = temp[i - l]; } void solve() { cin >> n >> m >> s; int lst = 0; s = '+' + s; st.ins(0), st.ins(n + 1); FOR( i, 1, n + 1, 1 ) { if( i <= n ) a[i] = s[i] - '0'; if( a[i] == 0 ) { if( lst ) q.pb({ 0, lst, i - 1, -1 }); lst = 0; } else lst = ( !lst ? i : lst ); } FOR( i, 1, m, 1 ) { cin >> s; if( s == "toggle" ) { cin >> x; if( a[x] == 0 ) { st.erase(x); auto i2 = st.ub(x); auto i1 = st.lb(x); i1 --; int L = (*i1) + 1, R = (*i2) - 1; if( L <= x - 1 ) q.pb({ i, L, x - 1, 1 }); if( x + 1 <= R ) q.pb({ i, x + 1, R, 1 }); q.pb({ i, L, R, -1 }); } else { auto i2 = st.ub(x); auto i1 = st.lb(x); i1 --; int L = (*i1) + 1, R = (*i2) - 1; st.ins(x); if( L <= x - 1 ) q.pb({ i, L, x - 1, -1 }); if( x + 1 <= R ) q.pb({ i, x + 1, R, -1 }); q.pb({ i, L, R, 1 }); } a[x] ^= 1; } else { cin >> x >> y; b[i] = 1; q.pb({ i, x, y - 1, 0 }); } } cdq(0, sz(q) - 1); FOR( i, 1, m, 1 ) if(b[i]) cout << ans[i] << '\n'; } signed main() { respagold int test = 1; if( !test ) cin >> test; while( test -- ) solve(); }
#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...