oj.uz

답안 #158039

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
158039 2019-10-14T13:19:57 Z nvmdava 가로등 (APIO19_street_lamps) C++17
0 / 100
 1816 ms 311572 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second
 
#define N 300005
#define INF 0x3f3f3f3f3f3f3f3f

struct Node{
	Node *l = NULL, *r = NULL;
	int val = 0;

	int query(int le, int ri, int x){

		if(le == ri) return val;
		int m = (le + ri) >> 1;
		if(m < x)
			return val + (r == NULL ? 0 : r -> query(m + 1, ri, x));
		return val + (l == NULL ? 0 : l -> query(le, m, x));
	}

	void update(int le, int ri, int R, int v){
		if(ri <= R){
			val += v;
			return;
		}

		int m = (le + ri) >> 1;
		
		if(l == NULL)
			l = new Node();
		l -> update(le, m, R, v);

		if(m < R){
			if(r == NULL)
				r = new Node();
			r -> update(m + 1, ri, R, v);
		}
	}
} *ans[N << 2];

int n, q;

void update(int id, int l, int r, int L, int R, int val){
	if(L <= l && r <= R){
		ans[id] -> update(1, n, R, val);
		return;
	}
	if(r < L || l > R){
		return;
	}
	int m = (l + r) >> 1;
	update(id << 1, l, m, L, R, val);
	update(id << 1 | 1, m + 1, r, L, R, val);
}

int query(int id, int l, int r, int x, int a){
	if(l == r){
		return ans[id] -> query(1, n, a);
	}
	int m = (l + r) >> 1;

	if(m < x)
		return ans[id] -> query(1, n, a) + query(id << 1 | 1, m + 1, r, x, a);
	return ans[id] -> query(1, n, a) + query(id << 1, l, m, x, a);
}

set<pair<pair<int, int>, int> > s;
int t;

void remove(set<pair<pair<int, int>, int> >::iterator it){
	update(1, 1, n, it -> ff.ss, it -> ff.ff, t - it -> ss);
	s.erase(it);
}

int st[N];

pair<int, int> tmp;

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin>>n>>q;
	tmp.ff = n + 1;

	for(int i = 1; i < (N << 2); ++i)
		ans[i] = new Node();

	for(int i = 1; i <= n; i++){
		char c;
		cin>>c;
		st[i] = c - '0';
		if(st[i] == 1){
			if(tmp.ff > n)
				tmp.ss = i;
			tmp.ff = i;
		} else {
			if(tmp.ff <= n){
				s.insert({tmp, 0});
				tmp.ff = n + 1;
			}
		}
	}
	
	if(tmp.ss <= n)
		s.insert({tmp, 0});



	for(t = 1; t <= q; t++){
		string q;
		int a, b;
		cin>>q;
		if(q[0] == 'q'){
			cin>>a>>b;
			b--;
			auto it = s.lower_bound({{a, a}, 0});
			if(it == s.end())
				cout<<query(1, 1, n, a, b)<<'\n';
			else
				cout<<query(1, 1, n, a, b) + (it -> ff.ss <= a && it -> ff.ff >= b ? t - it -> ss : 0)<<'\n';
		} else {
			cin>>a;
			if(st[a] == 1){
				auto it = s.lower_bound({{a, a}, 0});
				
				int le = it -> ff.ss;
				int ri = it -> ff.ff;

				remove(it);

				if(le < a)
					s.insert({{a = 1, le}, t});
				if(ri > a)
					s.insert({{ri, a + 1}, t});
			} else {
				int ri = a;
				int le = a;
				if(st[a + 1]){
					auto it = s.lower_bound({{a, a}, 0});
					ri = it -> ff.ff;
					remove(it);
				}
				if(st[a - 1]){
					auto it = --s.lower_bound({{a, a}, 0});
					le = it -> ff.ss;
					remove(it);
				}
				s.insert({{ri, le}, t});
			}
			st[a] ^= 1;
		}
	}
}

Subtask #1
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 148 ms 95748 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 307 ms 60756 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 72 ms 47736 KB Output is correct
2 Correct 72 ms 47832 KB Output is correct
3 Correct 72 ms 47724 KB Output is correct
4 Correct 70 ms 47352 KB Output is correct
5 Correct 1816 ms 311572 KB Output is correct
6 Correct 1759 ms 300856 KB Output is correct
7 Correct 1506 ms 260468 KB Output is correct
8 Correct 377 ms 50616 KB Output is correct
9 Incorrect 164 ms 48240 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 79 ms 47352 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 148 ms 95748 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -