답안 #172139

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
172139	2019-12-31T11:10:55 Z	super_j6	가로등 (APIO19_street_lamps)	C++14	100 / 100	2004 ms	350800 KB

street_lamps

#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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