oj.uz

Submission #158044

# Submission time Handle Problem Language Result Execution time Memory
158044 2019-10-14T13:31:40 Z nvmdava Street Lamps (APIO19_street_lamps) C++17
20 / 100
 1803 ms 311508 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.ff <= 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, 0}, 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 - 1, 0}, 0});
					le = it -> ff.ss;
					remove(it);
				}
				s.insert({{ri, le}, t});
			}
			st[a] ^= 1;
		}
	}
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 764 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 888 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1016 KB Output is correct
2 Correct 4 ms 1016 KB Output is correct
3 Correct 4 ms 888 KB Output is correct
4 Correct 3 ms 504 KB Output is correct
5 Correct 1803 ms 311508 KB Output is correct
6 Correct 1632 ms 300880 KB Output is correct
7 Correct 1399 ms 260280 KB Output is correct
8 Correct 326 ms 50456 KB Output is correct
9 Correct 94 ms 1272 KB Output is correct
10 Correct 102 ms 2628 KB Output is correct
11 Correct 102 ms 2552 KB Output is correct
12 Correct 340 ms 55076 KB Output is correct
13 Correct 321 ms 56340 KB Output is correct

Subtask #4
0 / 20.0

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

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 764 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -