oj.uz

Submission #172139

# Submission time Handle Problem Language Result Execution time Memory
172139 2019-12-31T11:10:55 Z super_j6 Street Lamps (APIO19_street_lamps) C++14
100 / 100
 2004 ms 350800 KB 
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <string.h>
using namespace std;
#define endl '\n'
#define pi pair<int, int>
#define pii pair<int, pi>
#define f first
#define s second

const int maxn = 300000;

struct segTree{
	int l, r;
	segTree *left = NULL, *right = NULL;
	long val = 0, lazy = 0;
 
	segTree(int a, int b){
		l = a;
		r = b;
	}
	
	void push(){
		if(left) left->lazy += lazy;
		if(right) right->lazy += lazy;
		lazy = 0;
	}
	
	void set(int x, int v){
		if(l == r){
			val = v;
			lazy = 0;
			return;
		}
 
		push();
		
		int mid = (l + r) / 2;
		if(x <= mid){
			if(!left) left = new segTree(l, mid);
			left->set(x, v);
		}
		if(x > mid){
			if(!right) right = new segTree(mid + 1, r);
			right->set(x, v);
		}
	}
 
	void add(int a, int b, int v){
		if(a <= l && r <= b){
			lazy += v;
			return;
		}
 
		push();
		
		int mid = (l + r) / 2;
		if(left && a <= mid) left->add(a, b, v);
		if(right && b > mid) right->add(a, b, v);
	}
 
	long qry(int x){
		if(l == r) return val + lazy;
		push();
		int mid = (l + r) / 2;
		if(left && x <= mid) return left->qry(x);
		if(right && x > mid) return right->qry(x);
		return -1;
	}
};

struct segTree2d{
	int l, r;
	segTree2d *left = NULL, *right = NULL;
	segTree *val = NULL;
	vector<pii> lazy;
 
	segTree2d(int a, int b){
		l = a;
		r = b;
	}
	
	void push(){
		for(pii i : lazy){
			if(left) left->lazy.push_back(i);
			if(right) right->lazy.push_back(i);
			if(val) val->add(i.s.f, i.s.s, i.f);
		}
		lazy.clear();
		
	}
	
	void set(int x, int y, int v){
		push();
		if(l == r){
			if(!val) val = new segTree(0, maxn);
			val->set(y, v);
			return;
		}
		
		int mid = (l + r) / 2;
		if(x <= mid){
			if(!left) left = new segTree2d(l, mid);
			left->set(x, y, v);
		}
		if(x > mid){
			if(!right) right = new segTree2d(mid + 1, r);
			right->set(x, y, v);
		}
	}
 
	void add(int x, int X, int y, int Y, int v){
		push();
		if(x <= l && r <= X){
			lazy.push_back({v, {y, Y}});
			return;
		}
		
		int mid = (l + r) / 2;
		if(left && x <= mid) left->add(x, X, y, Y, v);
		if(right && X > mid) right->add(x, X, y, Y, v);
	}
 
	long qry(int x, int y){
		push();
		if(l == r) return (val ? val->qry(y) : -1);
		int mid = (l + r) / 2;
		if(left && x <= mid) return left->qry(x, y);
		if(right && x > mid) return right->qry(x, y);
		return -1;
	}
};

int n, m;
int a[maxn];
pii q[maxn];
segTree l(0, maxn), r(0, maxn);
segTree2d tre(0, maxn);

int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin >> n >> m;
	
	for(int i = 0, j = 0; i < n; i++){
		char c;
		cin >> c;
		a[i] = c - '0';
		if(a[i]){
			l.set(i, j);
			r.set(i, i);
			r.add(j, i - 1, 1);
		}else{
			l.set(i, -1);
			r.set(i, -1);
			j = i + 1;
		}
	}
	
	for(int i = 0; i < m; i++){
		string s;
		cin >> s;
		if(s[0] == 'q'){
			q[i].f = 1;
			cin >> q[i].s.f >> q[i].s.s;
			q[i].s.f--, q[i].s.s -= 2;
			tre.set(q[i].s.f, q[i].s.s, (r.qry(q[i].s.f) >= q[i].s.s));
		}else{
			q[i].f = 0;
			cin >> q[i].s.f;
			q[i].s.f--;
		}
	}
	
	for(int i = 0; i < m; i++){
		if(q[i].f){
			cout << (tre.qry(q[i].s.f, q[i].s.s) + i * (r.qry(q[i].s.f) >= q[i].s.s)) << endl;
		}else{
			if(a[q[i].s.f]){
				int lq = l.qry(q[i].s.f), rq = r.qry(q[i].s.f);
				r.add(lq, q[i].s.f - 1, q[i].s.f - rq - 1);
				l.add(q[i].s.f + 1, rq, q[i].s.f - lq + 1);
				tre.add(lq, q[i].s.f, q[i].s.f, rq, i);
				l.set(q[i].s.f, -1), r.set(q[i].s.f, -1);
			}else{
				int lq = (q[i].s.f && a[q[i].s.f - 1] ? l.qry(q[i].s.f - 1) : q[i].s.f);
				int rq = (q[i].s.f < n - 1 && a[q[i].s.f + 1] ? r.qry(q[i].s.f + 1) : q[i].s.f);
				r.add(lq, q[i].s.f - 1, rq - q[i].s.f + 1);
				l.add(q[i].s.f + 1, rq, lq - q[i].s.f - 1);
				tre.add(lq, q[i].s.f, q[i].s.f, rq, -i);
				l.set(q[i].s.f, lq), r.set(q[i].s.f, rq);
			}
			a[q[i].s.f] ^= 1;
		}
	}

	return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 380 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 424 KB Output is correct
6 Correct 2 ms 632 KB Output is correct
7 Correct 2 ms 376 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 385 ms 8436 KB Output is correct
2 Correct 438 ms 8848 KB Output is correct
3 Correct 641 ms 15952 KB Output is correct
4 Correct 1525 ms 199224 KB Output is correct
5 Correct 1793 ms 226264 KB Output is correct
6 Correct 1560 ms 179856 KB Output is correct
7 Correct 1689 ms 269016 KB Output is correct
8 Correct 1803 ms 270396 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 504 KB Output is correct
2 Correct 4 ms 888 KB Output is correct
3 Correct 5 ms 1144 KB Output is correct
4 Correct 5 ms 1400 KB Output is correct
5 Correct 981 ms 70460 KB Output is correct
6 Correct 1483 ms 168576 KB Output is correct
7 Correct 1801 ms 255764 KB Output is correct
8 Correct 1853 ms 350800 KB Output is correct
9 Correct 225 ms 7644 KB Output is correct
10 Correct 246 ms 8020 KB Output is correct
11 Correct 247 ms 8696 KB Output is correct
12 Correct 1875 ms 349072 KB Output is correct
13 Correct 1848 ms 350624 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1292 KB Output is correct
2 Correct 5 ms 1144 KB Output is correct
3 Correct 4 ms 888 KB Output is correct
4 Correct 4 ms 632 KB Output is correct
5 Correct 2004 ms 346892 KB Output is correct
6 Correct 1732 ms 274308 KB Output is correct
7 Correct 1374 ms 193572 KB Output is correct
8 Correct 917 ms 70008 KB Output is correct
9 Correct 539 ms 15864 KB Output is correct
10 Correct 453 ms 7672 KB Output is correct
11 Correct 539 ms 15648 KB Output is correct
12 Correct 454 ms 7544 KB Output is correct
13 Correct 540 ms 15608 KB Output is correct
14 Correct 456 ms 7560 KB Output is correct
15 Correct 1878 ms 349128 KB Output is correct
16 Correct 1832 ms 350616 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 380 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 424 KB Output is correct
6 Correct 2 ms 632 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 385 ms 8436 KB Output is correct
9 Correct 438 ms 8848 KB Output is correct
10 Correct 641 ms 15952 KB Output is correct
11 Correct 1525 ms 199224 KB Output is correct
12 Correct 1793 ms 226264 KB Output is correct
13 Correct 1560 ms 179856 KB Output is correct
14 Correct 1689 ms 269016 KB Output is correct
15 Correct 1803 ms 270396 KB Output is correct
16 Correct 4 ms 504 KB Output is correct
17 Correct 4 ms 888 KB Output is correct
18 Correct 5 ms 1144 KB Output is correct
19 Correct 5 ms 1400 KB Output is correct
20 Correct 981 ms 70460 KB Output is correct
21 Correct 1483 ms 168576 KB Output is correct
22 Correct 1801 ms 255764 KB Output is correct
23 Correct 1853 ms 350800 KB Output is correct
24 Correct 225 ms 7644 KB Output is correct
25 Correct 246 ms 8020 KB Output is correct
26 Correct 247 ms 8696 KB Output is correct
27 Correct 1875 ms 349072 KB Output is correct
28 Correct 1848 ms 350624 KB Output is correct
29 Correct 5 ms 1292 KB Output is correct
30 Correct 5 ms 1144 KB Output is correct
31 Correct 4 ms 888 KB Output is correct
32 Correct 4 ms 632 KB Output is correct
33 Correct 2004 ms 346892 KB Output is correct
34 Correct 1732 ms 274308 KB Output is correct
35 Correct 1374 ms 193572 KB Output is correct
36 Correct 917 ms 70008 KB Output is correct
37 Correct 539 ms 15864 KB Output is correct
38 Correct 453 ms 7672 KB Output is correct
39 Correct 539 ms 15648 KB Output is correct
40 Correct 454 ms 7544 KB Output is correct
41 Correct 540 ms 15608 KB Output is correct
42 Correct 456 ms 7560 KB Output is correct
43 Correct 1878 ms 349128 KB Output is correct
44 Correct 1832 ms 350616 KB Output is correct
45 Correct 221 ms 5304 KB Output is correct
46 Correct 287 ms 5752 KB Output is correct
47 Correct 841 ms 118992 KB Output is correct
48 Correct 1528 ms 221108 KB Output is correct
49 Correct 274 ms 8696 KB Output is correct
50 Correct 273 ms 8440 KB Output is correct
51 Correct 278 ms 9080 KB Output is correct
52 Correct 319 ms 20772 KB Output is correct
53 Correct 320 ms 20744 KB Output is correct
54 Correct 323 ms 20884 KB Output is correct