oj.uz

Submission #371246

# Submission time Handle Problem Language Result Execution time Memory
371246 2021-02-26T09:37:36 Z super_j6 Street Lamps (APIO19_street_lamps) C++14
20 / 100
 2990 ms 524292 KB 
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
#define endl '\n'
#define ll long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define f first
#define s second

template<int... LR> struct segTred{
	ll vl = 0;
	void add(int v){ vl += v;}
	ll qry(){ return vl;}
};

template<int L, int R, int... LR> struct segTred<L, R, LR...>{
	struct segTree{
		int l, r;
		segTree *tl, *tr;
		segTred<LR...> *vl1, *vl2;
		
		segTree(int l, int r) : l(l), r(r){
			tl = tr = 0, vl1 = vl2 = 0;
		}
		
		template<typename... AB> void add(int v, int a, int b, AB... ab){
			if(b < l || r < a) return;
			if(!vl1) vl1 = new segTred<LR...>();
			vl1->add((min(r, b) - max(l, a) + 1) * v, ab...);
			if(a <= l && r <= b){
				if(!vl2) vl2 = new segTred<LR...>();
				return vl2->add(v, ab...);
			} 
			int mid = (l + r) / 2;
			if(a <= mid){
				if(!tl) tl = new segTree(l, mid);
				tl->add(v, a, b, ab...);
			}
			if(b > mid){
				if(!tr) tr = new segTree(mid + 1, r);
				tr->add(v, a, b, ab...);
			}
		}
		
		template<typename... AB> ll qry(int a, int b, AB... ab){
			if(b < l || r < a) return 0;
			if(a <= l && r <= b) return vl1 ? vl1->qry(ab...) : 0;
			return (vl2 ? (min(r, b) - max(l, a) + 1) * vl2->qry(ab...) : 0) +
				(tl ? tl->qry(a, b, ab...) : 0) +
				(tr ? tr->qry(a, b, ab...) : 0);
		}
	} *vl = 0;
	
	template<typename... AB> void add(int v, int a, int b, AB... ab){
		if(!vl) vl = new segTree(L, R);
		vl->add(v, a, b, ab...);
	}
	
	template<typename... AB> ll qry(int a, int b, AB... ab){ 
		if(!vl) vl = new segTree(L, R);
		return vl->qry(a, b, ab...);
	}
};

const int mxn = 300000;
int n, m;
int a[mxn];
pii q[mxn];
segTred<0, mxn> l, r;
segTred<0, mxn, 0, mxn> tre;
 
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.add(j, i, i);
			r.add(i, i, i);
			r.add(1, j, i - 1);
		}else{
			l.add(-1, i, i);
			r.add(-1, i, i);
			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.add((r.qry(q[i].s.f, q[i].s.f) >= q[i].s.s) - 
				tre.qry(q[i].s.f, q[i].s.f, q[i].s.s, q[i].s.s),
				q[i].s.f, q[i].s.f, q[i].s.s, 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.f, q[i].s.s, q[i].s.s) + 
				i * (r.qry(q[i].s.f, q[i].s.f) >= q[i].s.s)) << endl;
		}else{
			if(a[q[i].s.f]){
				int lq = l.qry(q[i].s.f, q[i].s.f), rq = r.qry(q[i].s.f, q[i].s.f);
				r.add(q[i].s.f - rq - 1, lq, q[i].s.f - 1);
				l.add(q[i].s.f - lq + 1, q[i].s.f + 1, rq);
				tre.add(i, lq, q[i].s.f, q[i].s.f, rq);
				l.add(-1 - l.qry(q[i].s.f, q[i].s.f), q[i].s.f, q[i].s.f);
				r.add(-1 - r.qry(q[i].s.f, q[i].s.f), q[i].s.f, q[i].s.f);
			}else{
				int lq = (q[i].s.f && a[q[i].s.f - 1] ? l.qry(q[i].s.f - 1, 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 + 1) : q[i].s.f);
				r.add(rq - q[i].s.f + 1, lq, q[i].s.f - 1);
				l.add(lq - q[i].s.f - 1, q[i].s.f + 1, rq);
				tre.add(-i, lq, q[i].s.f, q[i].s.f, rq);
				l.add(lq - l.qry(q[i].s.f, q[i].s.f), q[i].s.f, q[i].s.f);
				r.add(rq - r.qry(q[i].s.f, q[i].s.f), q[i].s.f, q[i].s.f);
			}
			a[q[i].s.f] ^= 1;
		}
	}
 
	return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 620 KB Output is correct
4 Correct 2 ms 1132 KB Output is correct
5 Correct 2 ms 1004 KB Output is correct
6 Correct 2 ms 1004 KB Output is correct
7 Correct 2 ms 1004 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1553 ms 9900 KB Output is correct
2 Correct 1683 ms 13540 KB Output is correct
3 Correct 2990 ms 77228 KB Output is correct
4 Runtime error 1122 ms 524292 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 10092 KB Output is correct
2 Correct 23 ms 11116 KB Output is correct
3 Correct 23 ms 10988 KB Output is correct
4 Correct 20 ms 9196 KB Output is correct
5 Runtime error 1140 ms 524292 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 9068 KB Output is correct
2 Correct 20 ms 9452 KB Output is correct
3 Correct 19 ms 8684 KB Output is correct
4 Correct 18 ms 7532 KB Output is correct
5 Runtime error 1014 ms 524292 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 620 KB Output is correct
4 Correct 2 ms 1132 KB Output is correct
5 Correct 2 ms 1004 KB Output is correct
6 Correct 2 ms 1004 KB Output is correct
7 Correct 2 ms 1004 KB Output is correct
8 Correct 1553 ms 9900 KB Output is correct
9 Correct 1683 ms 13540 KB Output is correct
10 Correct 2990 ms 77228 KB Output is correct
11 Runtime error 1122 ms 524292 KB Execution killed with signal 9
12 Halted 0 ms 0 KB -