Submission #447872

#	Time	Username	Problem	Language	Result	Execution time	Memory
447872		AmShZ	Street Lamps (APIO19_street_lamps)	C++17	20 / 100	5085 ms	311212 KiB

street_lamps

//khodaya khodet komak kon
# include <bits/stdc++.h>
/*
# pragma GCC optimize("Ofast,unroll-loops")
# pragma comment(linker, "/stack:200000000")
# pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma,tune=native")
*/

using namespace std;

typedef long long                                        ll;
typedef long double                                      ld;
typedef pair <int, int>                                  pii;
typedef pair <pii, int>                                  ppi;
typedef pair <int, pii>                                  pip;
typedef pair <pii, pii>                                  ppp;
typedef pair <ll, ll>                                    pll;

# define A                                               first
# define B                                               second
# define endl                                            '\n'
# define sep                                             ' '
# define all(x)                                          x.begin(), x.end()
# define kill(x)                                         return cout << x << endl, 0
# define SZ(x)                                           int(x.size())
# define lc                                              id << 1
# define rc                                              id << 1 | 1
# define fast_io                                         ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);

ll power(ll a, ll b, ll md) {return (!b ? 1 : (b & 1 ? a * power(a * a % md, b / 2, md) % md : power(a * a % md, b / 2, md) % md));}

const int xn = 3e5 + 10;
const int xm = - 20 + 10;
const int sq = 320;
const int inf = 1e9 + 10;
const ll INF = 1e18 + 10;
const ld eps = 1e-15;
const int mod = 998244353;
const int base = 257;

int n, q;
map <int, int> fen[xn];
string S;
set <int> st;
bool fl[xn];

void mofen(int x, int y, int val){
	int ly = y;
	for (x += 5; x < xn; x += x & - x){
		y = ly;
		for (y += 5; y < xn; y += y & - y)
			fen[x][y] += val;
	}
}
int gefen(int x, int y){
	int res = 0, ly = y;
	for (x += 5; 0 < x; x -= x & - x){
		y = ly;
		for (y += 5; 0 < y; y -= y & - y)
			//if (fen[x].find(i) != fen[x].end())
			res += fen[x][y];
	}
	return res;
}
void upd(int l1, int r1, int l2, int r2, int val){
	mofen(l1, l2, val);
	mofen(l1, r2 + 1, - val);
	mofen(r1 + 1, l2, - val);
	mofen(r1 + 1, r2 + 1, val);
}

int main(){
	fast_io;

	cin >> n >> q >> S;
	S = '.' + S;
	st.insert(0);
	st.insert(n + 1);
	int last = n + 1;
	for (int i = n; 1 <= i; -- i){
		if (S[i] == '0')
			last = i, st.insert(i);
		fl[i] = S[i] - '0';
		upd(i - 1, i - 1, i - 1, last - 1, q);
	}
	for (int i = 1; i <= q; ++ i){
		int l, r, ind;
		cin >> S;
		if (S[0] == 't'){
			cin >> ind;
			if (!fl[ind]){
				int y = *st.lower_bound(ind + 1);
				int x = *prev(st.lower_bound(ind));
				upd(x, ind - 1, ind, y - 1, q - i);
				st.erase(ind);
			}
			else{
				int y = *st.lower_bound(ind + 1);
				int x = *prev(st.lower_bound(ind));
				upd(x, ind - 1, ind, y - 1, i - q);
				st.insert(ind);
			}
			fl[ind] ^= 1;
		}
		else{
			cin >> l >> r;
			int ans = gefen(l - 1, r - 1);
			if (r <= *st.lower_bound(l))
				ans -= q - i;
			cout << ans << endl;
		}
	}

	return 0;
}

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