제출 #383236

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
383236		milleniumEeee	가로등 (APIO19_street_lamps)	C++17	20 / 100	1129 ms	32172 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');
}

struct node {
	int mx, cnt;
	node () {
		mx = -INF, cnt = 0;
	}
	node (int x) {
		mx = x, cnt = 1;
	}
	node (int mx_, int cnt_) {
		mx = mx_;
		cnt = cnt_;
	}
};

node operator + (const node &a, const node &b) {
	node res;
	res.mx = max(a.mx, b.mx);
	res.cnt = a.cnt + b.cnt;
	return res;
}

node tree[MAXN * 4];

void upd(int pos, int val, int v = 1, int tl = 1, int tr = MAXN) {
	if (tl == tr) {
		tree[v] = node(val);
		return;
	}
	int mid = (tl + tr) >> 1;
	if (pos <= mid) {
		upd(pos, val, v + v, tl, mid);
	} else {
		upd(pos, val, v + v + 1, mid + 1, tr);
	}
	tree[v] = tree[v + v] + tree[v + v + 1];
}

node get(int l, int r, int v = 1, int tl = 1, int tr = MAXN) {
	if (l > tr || tl > r) {
		return node(-INF, 0);
	}
	if (l <= tl && tr <= r) {
		return tree[v];
	}
	int mid = (tl + tr) >> 1;
	return get(l, r, v + v, tl, mid) + get(l, r, v + v + 1, mid + 1, tr);
}

int get_len(int l, int r) {
	return r - l + 1;
}

signed main() {
	fastInp;
	fill(tree, tree + MAXN * 4, node(-INF, 0));
	int n, q;
	cin >> n >> q;
	for (int i = 1; i <= n; i++) {
		cin >> c[i];
		if (c[i] == '1') {
			upd(i, 0);
		}
	}
	string type;
	
	//for (int i = 1; i <= n; i++) {
		//cout << get(i, i).cnt << " ";
	//}cout << endl;
	
	for (int xod = 1, tiktak = 1; xod <= q; xod++, tiktak++) {
		cin >> type;
		if (type == "query") {
			int l, r;
			cin >> l >> r;
			node cur = get(l, r - 1);
			if (cur.cnt == get_len(l, r - 1)) {
				cout << get_len(cur.mx, tiktak - 1) << endl;
			} else {
				cout << 0 << endl;
			}
		}
		if (type == "toggle") {
			int pos;
			cin >> pos;
			upd(pos, tiktak);
		}
	}
}
/*
5 7
11011
query 1 2
*/

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