Submission #255217

#	Time	Username	Problem	Language	Result	Execution time	Memory
255217		Atalasion	Street Lamps (APIO19_street_lamps)	C++14	100 / 100	1882 ms	211320 KiB

street_lamps

//khodaya khodet komak kon
#include <bits/stdc++.h>

#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")


using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int N = 300000 + 10;
const ll MOD = 1000000000 + 7;
const ll INF = 1000000010;
const ll LOG = 25;

int koj[LOG][N], n, q, a[N], F[N], R[N];
vi seg[N << 2],fen[N << 2], L[N];
set<int> One, Zero;

bool cmp(int x, int y){
	return R[x] < R[y];
}

inline void add(int ind, int id, int x){
	for (; id < fen[ind].size(); id += id & (-id)) fen[ind][id] += x;
}

inline int get(int ind, int id){
	int res = 0;
	for (; id > 0; id -= id & (-id)) res += fen[ind][id];
	return res;
}

void build(int h, int id, int l, int r){
	if (r - l == 1){
		fen[id].pb(0);
		for (auto u:L[l]) seg[id].pb(u), fen[id].pb(0);
		sort(all(seg[id]), cmp);
		for (int i = 0; i < seg[id].size(); i++) koj[h][seg[id][i]] = i + 1;
  		return;
	}
	int md = (l + r) >> 1;
	build(h + 1, id << 1, l, md);
	build(h + 1, id << 1 |1 , md, r);
	fen[id].pb(0);
	for (auto u:seg[id << 1]) seg[id].pb(u), fen[id].pb(0);
	for(auto u:seg[id << 1 | 1]) seg[id].pb(u), fen[id].pb(0);
	sort(all(seg[id]), cmp);
	for (int i = 0; i < seg[id].size(); i++) koj[h][seg[id][i]] = i + 1;
}

void Add(int id, int lq, int rq, int x, int t, int l, int r){
	if (rq <= l || r <= lq) return;
	if (lq <= l && r <= rq){
		if (seg[id].size() == 0) return;
		int LL = 0, RR = seg[id].size();
		if (R[seg[id][0]] >= x) return;
		while (RR - LL > 1){
			int md = (LL + RR) >> 1;
			if (R[seg[id][md]] < x) LL = md;
			else RR = md;
		}
		int zar = 1;
		add(id, 1, t);
		add(id, RR + 1, -t);
		return;
	}
	int md = (l + r) >> 1;
	Add(id << 1, lq, rq, x, t, l, md);
	Add(id << 1 | 1, lq, rq, x, t, md, r);
}

void Add2(int id, int lq, int rq, int x, int t, int l, int r){
	if (rq <= l || r <= lq) return;
	if (lq <= l && r <= rq){
		if (seg[id].size() == 0) return;
		if (R[seg[id].back()] < x) return;
		int LL = -1, RR = seg[id].size() - 1;
		while (RR - LL > 1){
			int md = (RR + LL) >> 1;
			if (R[seg[id][md]] >= x) RR = md;
			else LL = md;
		}
//		cout << "Query\n";
//		cout << l << ' ' << r - 1 << ' ' << RR + 1 << ' ' << x << ' ';
		add(id, RR + 1, t);
//		cout << get(id, fen[id].size() - 1) << '\n';
		return;
	}
	int md = (l + r) >> 1;
	Add2(id << 1, lq, rq, x, t, l, md);
	Add2(id << 1 | 1, lq, rq, x, t, md, r);
}

int Get(int h, int id, int lq, int rq, int x, int l, int r){
	if (rq <= l || r <= lq)return 0;
	if (lq <= l && r <= rq){
//		cout << l << ' ' << r - 1 << ' ' << x << ' ' << koj[h][x] << ' ' << get(id, koj[h][x]) << '\n';
		return get(id, koj[h][x]);
	}
	int res = get(id, koj[h][x]);
//	cout << l << ' ' << r - 1 << ' ' << x << ' ' << koj[h][x] << ' ' <<res << '\n';
	int md = (l + r) >> 1;
	return (res + Get(h + 1, id << 1, lq, rq, x, l, md) + Get(h + 1, id << 1 | 1, lq, rq, x, md, r));
}

vector<pair<int, pii>> Q;

int32_t main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> q;
	string s;
	cin >> s;
	Zero.insert(0);
	Zero.insert(n + 1);
	One.insert(0), One.insert(n + 1);
	for (int i = 1; i <= n; i++) a[i] = (s[i - 1] == '1');
	for (int i = 1; i <= n; i++){
		if (a[i] == 1) One.insert(i);
		else Zero.insert(i);
	}
	for (int i = 1; i <= q; i++){
		cin >> s;
		if (s == "query"){
			int l, r;
			cin >> l >> r;
			r--;
			R[i] = r;
			L[l].pb(i);
			Q.pb({1, {l, r}});
		}else{
			int x;
			cin >> x;
			Q.pb({2, {x, 0}});
		}
	}
	build(0, 1, 1, n + 1);
	for (int i = 1; i <= q; i++){
		auto u = Q[i - 1];
		int x = u.F;
		if (x == 1){
			int l = u.S.F, r = u.S.S;
			int res = Get(0, 1, l, l + 1, i, 1, n + 1);
			if (a[l] == 1){
				auto koj = Zero.lower_bound(l);
				if ((*koj) > r) res += i;
			} 
			cout << res << '\n';
		}else{
			int l = u.S.F;
			if (a[l] == 1){
				a[l] = 0;
				One.erase(l);
				auto koj = Zero.lower_bound(l);
				auto koj2 = koj;
				koj2--;
//				cout << (*koj2) + 1 << ' ' << l << ' ' << (*koj) << endl;
//				cout << "YES" << endl;
				Add(1, (*koj2) + 1, l + 1, (*koj), i, 1, n + 1);
//				cout << "YES2" << endl;
				Add(1, (*koj2) + 1, l + 1, l, -i, 1, n + 1);
				Zero.insert(l);
			}else{
				a[l] = 1;
				Zero.erase(l);
				auto koj = Zero.lower_bound(l);
				auto koj2 = koj;
				koj2--;
//				cout << "Fuck " << (*koj2) + 1 << ' ' << (*koj) << '\n';
				Add2(1, (*koj2) + 1, l + 1, l, -i, 1, n + 1);
				Add2(1, (*koj2) + 1, l + 1, (*koj), i, 1, n + 1);
				One.insert(l);
			
			}
		}
	}









	return 0;
}

Compilation message (stderr)

street_lamps.cpp: In function 'void add(int, int, int)':
street_lamps.cpp:31:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (; id < fen[ind].size(); id += id & (-id)) fen[ind][id] += x;
         ~~~^~~~~~~~~~~~~~~~~
street_lamps.cpp: In function 'void build(int, int, int, int)':
street_lamps.cpp:45:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < seg[id].size(); i++) koj[h][seg[id][i]] = i + 1;
                   ~~^~~~~~~~~~~~~~~~
street_lamps.cpp:55:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < seg[id].size(); i++) koj[h][seg[id][i]] = i + 1;
                  ~~^~~~~~~~~~~~~~~~
street_lamps.cpp: In function 'void Add(int, int, int, int, int, int, int)':
street_lamps.cpp:69:7: warning: unused variable 'zar' [-Wunused-variable]
   int zar = 1;
       ^~~

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