Submission #1236148

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236148		KluydQ	Street Lamps (APIO19_street_lamps)	C++20	100 / 100	1213 ms	122116 KiB

street_lamps

#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);
			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);
	
	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; st.ins(i);
		}
		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();
}

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20