oj.uz

Submission #383236

# Submission time Handle Problem Language Result Execution time Memory
383236 2021-03-29T09:20:37 Z milleniumEeee Street Lamps (APIO19_street_lamps) C++17
20 / 100
 1129 ms 32172 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 23788 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 504 ms 24448 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23788 KB Output is correct
2 Correct 19 ms 23788 KB Output is correct
3 Correct 19 ms 23788 KB Output is correct
4 Correct 23 ms 23788 KB Output is correct
5 Correct 203 ms 28396 KB Output is correct
6 Correct 467 ms 29164 KB Output is correct
7 Correct 783 ms 29852 KB Output is correct
8 Correct 1083 ms 32172 KB Output is correct
9 Correct 729 ms 27500 KB Output is correct
10 Correct 790 ms 27884 KB Output is correct
11 Correct 767 ms 28020 KB Output is correct
12 Correct 1078 ms 29276 KB Output is correct
13 Correct 1129 ms 30824 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 23788 KB Output is correct
2 Incorrect 20 ms 23788 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 23788 KB Output isn't correct
2 Halted 0 ms 0 KB -