oj.uz

Submission #344822

# Submission time Handle Problem Language Result Execution time Memory
344822 2021-01-06T15:32:24 Z alishahali1382 Street Lamps (APIO19_street_lamps) C++14
100 / 100
 3495 ms 95528 KB 
#include <bits/stdc++.h>
#pragma GCC optimize ("O2,unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
 
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;
 
const int inf=1000000010;
const ll INF=10000000000000010LL;
const int mod=1000000007;
const int MAXN=300010, LOG=20;
 
int n, m, k, u, v, x, y, t, a, b, ans;
int QA[MAXN], QB[MAXN];
int segl[MAXN<<2], segr[MAXN<<2];
pii seg[LOG][MAXN];
int fen[LOG][MAXN];
vector<int> Q[MAXN];
string S, typ[MAXN]; 
set<int> st;
 
void Build(int h, int id, int tl, int tr){
	if (tr-tl==1){
		segr[id]=segl[id];
		for (int i:Q[tl]) seg[h][segr[id]++]={QB[i], i};
		sort(seg[h]+segl[id], seg[h]+segr[id]);
	}
	else{
		int mid=(tl+tr)>>1;
		segl[id<<1]=segl[id];
		Build(h+1, id<<1, tl, mid);
		segl[id<<1 | 1]=segr[id<<1];
		Build(h+1, id<<1 | 1, mid, tr);
		merge(seg[h+1]+segl[id<<1], seg[h+1]+segr[id<<1], seg[h+1]+segl[id<<1 | 1], seg[h+1]+segr[id<<1 | 1], seg[h]+segl[id]);
		segr[id]=segr[id<<1 | 1];
	}
}
inline void add(int h, int pos, int val){
	for (; pos<MAXN; pos+=pos&-pos) fen[h][pos]+=val;
}
inline int get(int h, int pos){
	int res=0;
	for (; pos; pos-=pos&-pos) res+=fen[h][pos];
	return res;
}
void Add(int h, int id, int tl, int tr, int l, int r, int ll, int rr, int val){
	if (r<=tl || tr<=l) return ;
	if (l<=tl && tr<=r){
		int pl=lower_bound(seg[h]+segl[id], seg[h]+segr[id], pii(ll, 0))-seg[h];
		int pr=upper_bound(seg[h]+segl[id], seg[h]+segr[id], pii(rr, inf))-seg[h];
		add(h, pl, +val);
		add(h, pr, -val);
		return ;
	}
	int mid=(tl+tr)>>1;
	Add(h+1, id<<1, tl, mid, l, r, ll, rr, val);
	Add(h+1, id<<1 | 1, mid, tr, l, r, ll, rr, val);
}
int Get(int h, int id, int tl, int tr, int i){
	if (QA[i]<tl || tr<=QA[i]) return 0;
	int res=get(h, lower_bound(seg[h]+segl[id], seg[h]+segr[id], pii(QB[i], i))-seg[h]);
	if (tr-tl==1) return res;
	int mid=(tl+tr)>>1;
	return res+Get(h+1, id<<1, tl, mid, i) + Get(h+1, id<<1 | 1, mid, tr, i);
}
bool check(int l, int r){
	return (*st.lower_bound(l))==(*st.lower_bound(r));
}
 
int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	cin>>n>>m>>S;
	for (int i=1; i<=m; i++){
		cin>>typ[i]>>QA[i];
		if (typ[i]=="query"){
			cin>>QB[i];
			Q[QA[i]].pb(i);
		}
	}
	segl[1]=1;
	Build(0, 1, 1, n+1);
	S="0"+S+"0";
	for (int i=0; i<=n+1; i++) if (S[i]=='0') st.insert(i);
	for (int i=1; i<=m; i++){
		if (typ[i]=="query"){
			ans=Get(0, 1, 1, n+1, i);
			if (check(QA[i], QB[i])) ans+=i;
			cout<<ans<<"\n";
			continue ;
		}
		int pos=QA[i];
		if (S[pos]=='0'){
			auto it=st.lower_bound(pos);
			int x=*--it;
			++it;
			int y=*++it;
			Add(0, 1, 1, n+1, x+1, pos+1, pos+1, y, -i);
			S[pos]='1';
			st.erase(pos);
		}
		else{
			auto it=st.lower_bound(pos);
			int y=*it;
			int x=*--it;
			Add(0, 1, 1, n+1, x+1, pos+1, pos+1, y, +i);
			S[pos]='0';
			st.insert(pos);
		}
	}
	
	return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 17004 KB Output is correct
2 Correct 11 ms 17004 KB Output is correct
3 Correct 11 ms 17004 KB Output is correct
4 Correct 11 ms 17004 KB Output is correct
5 Correct 11 ms 17004 KB Output is correct
6 Correct 11 ms 16876 KB Output is correct
7 Correct 11 ms 16876 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 513 ms 32468 KB Output is correct
2 Correct 737 ms 35040 KB Output is correct
3 Correct 1124 ms 40692 KB Output is correct
4 Correct 1784 ms 65840 KB Output is correct
5 Correct 2040 ms 76560 KB Output is correct
6 Correct 1429 ms 59312 KB Output is correct
7 Correct 3227 ms 95528 KB Output is correct
8 Correct 2705 ms 82828 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 17388 KB Output is correct
2 Correct 12 ms 17388 KB Output is correct
3 Correct 12 ms 17388 KB Output is correct
4 Correct 13 ms 17004 KB Output is correct
5 Correct 640 ms 43312 KB Output is correct
6 Correct 1317 ms 59780 KB Output is correct
7 Correct 2028 ms 75724 KB Output is correct
8 Correct 2578 ms 82228 KB Output is correct
9 Correct 558 ms 37404 KB Output is correct
10 Correct 624 ms 39196 KB Output is correct
11 Correct 579 ms 39532 KB Output is correct
12 Correct 3408 ms 94996 KB Output is correct
13 Correct 2649 ms 82192 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 17132 KB Output is correct
2 Correct 12 ms 17132 KB Output is correct
3 Correct 12 ms 17132 KB Output is correct
4 Correct 14 ms 17132 KB Output is correct
5 Correct 3292 ms 91500 KB Output is correct
6 Correct 2354 ms 75888 KB Output is correct
7 Correct 1504 ms 58672 KB Output is correct
8 Correct 552 ms 34480 KB Output is correct
9 Correct 428 ms 26988 KB Output is correct
10 Correct 207 ms 18796 KB Output is correct
11 Correct 446 ms 26988 KB Output is correct
12 Correct 202 ms 18668 KB Output is correct
13 Correct 426 ms 26860 KB Output is correct
14 Correct 206 ms 18668 KB Output is correct
15 Correct 3495 ms 94860 KB Output is correct
16 Correct 2639 ms 82120 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 17004 KB Output is correct
2 Correct 11 ms 17004 KB Output is correct
3 Correct 11 ms 17004 KB Output is correct
4 Correct 11 ms 17004 KB Output is correct
5 Correct 11 ms 17004 KB Output is correct
6 Correct 11 ms 16876 KB Output is correct
7 Correct 11 ms 16876 KB Output is correct
8 Correct 513 ms 32468 KB Output is correct
9 Correct 737 ms 35040 KB Output is correct
10 Correct 1124 ms 40692 KB Output is correct
11 Correct 1784 ms 65840 KB Output is correct
12 Correct 2040 ms 76560 KB Output is correct
13 Correct 1429 ms 59312 KB Output is correct
14 Correct 3227 ms 95528 KB Output is correct
15 Correct 2705 ms 82828 KB Output is correct
16 Correct 11 ms 17388 KB Output is correct
17 Correct 12 ms 17388 KB Output is correct
18 Correct 12 ms 17388 KB Output is correct
19 Correct 13 ms 17004 KB Output is correct
20 Correct 640 ms 43312 KB Output is correct
21 Correct 1317 ms 59780 KB Output is correct
22 Correct 2028 ms 75724 KB Output is correct
23 Correct 2578 ms 82228 KB Output is correct
24 Correct 558 ms 37404 KB Output is correct
25 Correct 624 ms 39196 KB Output is correct
26 Correct 579 ms 39532 KB Output is correct
27 Correct 3408 ms 94996 KB Output is correct
28 Correct 2649 ms 82192 KB Output is correct
29 Correct 12 ms 17132 KB Output is correct
30 Correct 12 ms 17132 KB Output is correct
31 Correct 12 ms 17132 KB Output is correct
32 Correct 14 ms 17132 KB Output is correct
33 Correct 3292 ms 91500 KB Output is correct
34 Correct 2354 ms 75888 KB Output is correct
35 Correct 1504 ms 58672 KB Output is correct
36 Correct 552 ms 34480 KB Output is correct
37 Correct 428 ms 26988 KB Output is correct
38 Correct 207 ms 18796 KB Output is correct
39 Correct 446 ms 26988 KB Output is correct
40 Correct 202 ms 18668 KB Output is correct
41 Correct 426 ms 26860 KB Output is correct
42 Correct 206 ms 18668 KB Output is correct
43 Correct 3495 ms 94860 KB Output is correct
44 Correct 2639 ms 82120 KB Output is correct
45 Correct 208 ms 23920 KB Output is correct
46 Correct 378 ms 26836 KB Output is correct
47 Correct 1026 ms 41044 KB Output is correct
48 Correct 1872 ms 65116 KB Output is correct
49 Correct 691 ms 40556 KB Output is correct
50 Correct 693 ms 40172 KB Output is correct
51 Correct 710 ms 41040 KB Output is correct
52 Correct 679 ms 45316 KB Output is correct
53 Correct 660 ms 45548 KB Output is correct
54 Correct 649 ms 45164 KB Output is correct