oj.uz

Submission #158033

# Submission time Handle Problem Language Result Execution time Memory
158033 2019-10-14T13:14:10 Z nvmdava Street Lamps (APIO19_street_lamps) C++17
0 / 100
 1793 ms 315936 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.ff, it -> ff.ss, 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.ss = 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.ss > n)
				tmp.ff = i;
			tmp.ss = i;
		} else {
			if(tmp.ss <= n){
				s.insert({tmp, 0});
				tmp.ss = 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 + 1, a + 1}, 0});

			if(it == s.end())
				cout<<query(1, 1, n, a, b)<<'\n';
			else
				cout<<query(1, 1, n, a, b) + (it -> ff.ff <= a && it -> ff.ss >= 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.ff;
				int ri = it -> ff.ss;

				remove(it);

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

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 140 ms 95772 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 137 ms 95708 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 47736 KB Output is correct
2 Correct 72 ms 47736 KB Output is correct
3 Correct 72 ms 47708 KB Output is correct
4 Correct 72 ms 47352 KB Output is correct
5 Correct 1669 ms 315936 KB Output is correct
6 Correct 1793 ms 305576 KB Output is correct
7 Correct 1456 ms 265580 KB Output is correct
8 Correct 332 ms 56420 KB Output is correct
9 Correct 163 ms 50936 KB Output is correct
10 Correct 171 ms 51344 KB Output is correct
11 Correct 177 ms 51500 KB Output is correct
12 Runtime error 161 ms 98388 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 47272 KB Output is correct
2 Incorrect 71 ms 47480 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 140 ms 95772 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -