제출 #383226

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
383226		milleniumEeee	Street Lamps (APIO19_street_lamps)	C++17	20 / 100	908 ms	43016 KiB

street_lamps

#include <bits/stdc++.h>
#define fastInp ios_base::sync_with_stdio(0); cin.tie(0);
#define pii pair<int, int>
#define fr first
#define sc second
#define mk make_pair
#define pb push_back
#define szof(s) (int)s.size()
#define all(s) s.begin(), s.end()
using namespace std;

const int MAXN = (int)3e5 + 5;
const int INF = 1e9;

char c[MAXN];
vector <pii> seg[MAXN];
vector <pii> qvec;
vector <int> pref[MAXN];

char rev(char x) {
	return (x == '1' ? '0' : '1');
}

signed main() {
	fastInp;
	int n, q;
	cin >> n >> q;
	for (int i = 1; i <= n; i++) {
		cin >> c[i];
		if (c[i] == '1') {
			seg[i].pb({0, INF});
		}
	}
	string type;
	for (int xod = 1, tiktak = 1; xod <= q; xod++, tiktak++) {
		cin >> type;
		if (type == "query") {
			int l, r;
			cin >> l >> r;
			assert(l + 1 == r);
			qvec.pb({xod, l});
		}
		if (type == "toggle") {
			int pos;
			cin >> pos;
			if (c[pos] == '0') {
				seg[pos].pb({xod, INF});
			}
			else if (c[pos] == '1') {
				seg[pos].back().second = xod - 1;
			}
			c[pos] = rev(c[pos]);
		}
	}
	
	//cout << "seg: " << endl;
	//for (int i = 1; i <= n; i++) {
		//cout << i << ": " << endl;
		//for (auto el : seg[i]) {
			//cout << el.fr << " " << el.sc << endl;
		//}
	//}
	
	for (int i = 1; i <= n; i++) {
		if (seg[i].empty()) {
			continue;
		}
		for (int j = 0; j < szof(seg[i]); j++) {
			if (j == 0) {
				pref[i].pb(seg[i][j].sc - seg[i][j].fr + 1);
			} else {
				pref[i].pb(pref[i].back() + seg[i][j].sc - seg[i][j].fr + 1);
			}
		}
	}
	
	for (auto el : qvec) {
		int tiktak = el.fr, pos = el.sc;
		if (seg[pos].empty()) {
			cout << 0 << endl;
		} else {
			if (seg[pos][0].fr < tiktak) {
				int l = 0, r = szof(seg[pos]);
				while (r - l > 1) {
					int mid = (l + r) >> 1;
					if (seg[pos][mid].fr < tiktak) {
						l = mid;
					} else {
						r = mid;
					}
				}
				int ans = 0;
				if (l >= 1) {
					ans = pref[pos][l - 1];
				}
				if (seg[pos][l].sc < tiktak) {
					ans += seg[pos][l].sc - seg[pos][l].fr + 1;
				} else {
					ans += (tiktak - 1) - seg[pos][l].fr + 1;
				}
				cout << ans << endl;
			} else {
				cout << 0 << endl;
			}
		}
	}
}

/*
6 4
101001
toggle 2 
toggle 2
toggle 4
query 2 3
*/

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