oj.uz

Submission #202194

# Submission time Handle Problem Language Result Execution time Memory
202194 2020-02-14T05:16:56 Z red1108 Street Lamps (APIO19_street_lamps) C++17
40 / 100
 5000 ms 371128 KB 
#include<bits/stdc++.h>
#include<ext/rope>
using namespace std;
using namespace __gnu_cxx;
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false);cin.tie(0)
#define fopen freopen("input.txt", "r", stdin)
#define eb emplace_back
#define em emplace
#define prec(a) cout<<fixed;cout.precision(a);
#define all(a) (a).begin(), (a).end()
typedef long long ll;typedef long double ld;typedef unsigned long long ul;typedef unsigned int ui;typedef pair<int,int> pii;typedef pair<ll,ll> pll;
typedef tuple<int,int,int> tiii;
const ll INF = 2e18;
const int inf = 2e9;
template<class T>
void pr(T t) {cerr << t << " ";}
template<class T, class ...Args>
void pr(T a, Args ...args) {cerr << a << " ";pr(args...);}
template<class ...Args>
void prl(Args ...args) {pr(args...);cerr << endl;}


int n,q,cur[300010];
tiii seg[1200000];
string in;
void gang(int x, int l, int r, int s, int e, int t){
	if(s>e||r<s||e<l) return ;
	if(s<=l&&r<=e){
		seg[x]=tiii(t,s,e);
		return ;
	}
	gang(x*2,l,(l+r)/2,s,e,t);gang(x*2+1,(l+r)/2+1,r,s,e,t);
}
tiii get(int x, int l, int r, int ind){
	if(ind<l||r<ind) return tiii(0,0,0);
	if(l==r) return seg[x];
	return max({seg[x],get(x*2,l,(l+r)/2,ind), get(x*2+1,(l+r)/2+1,r,ind)});
}
struct Node{
	int cnt=0, l=0, r=0, lsum=0, dsum=0;
	Node(){}
};
struct SEG{
	vector<Node> seg;
	SEG(){seg.eb(Node());seg.eb(Node());}
	void gang(int x, int l, int r, int ind, int t, int bac){
		if(l==r){
			if(bac==-1){
				seg[x].cnt+=1;
				seg[x].lsum+=t;
			}
			else{
				seg[x].cnt--;
				seg[x].dsum += (t - bac);
				seg[x].lsum -=bac;
			}
			return ;
		}
		int m = (l+r)/2;
		if(ind<=m){
			if(!seg[x].l){
				seg[x].l = seg.size();seg.eb(Node());
			}
			gang(seg[x].l,l,(l+r)/2,ind,t,bac);
		}
		else{
			if(!seg[x].r){
				seg[x].r = seg.size();seg.eb(Node());
			}
			gang(seg[x].r,(l+r)/2+1,r,ind,t,bac);
		}
		seg[x].cnt = seg[seg[x].l].cnt + seg[seg[x].r].cnt;
		seg[x].lsum = seg[seg[x].l].lsum + seg[seg[x].r].lsum;
		seg[x].dsum = seg[seg[x].l].dsum + seg[seg[x].r].dsum;
	}
	ll hap(int x, int l, int r, int ind, ll t){
		//prl("hap", x, l, r, ind, t);
		if(x==0||ind<l) return 0;
		if(r<=ind){
			return t * seg[x].cnt - seg[x].lsum + seg[x].dsum;
		}
		return hap(seg[x].l, l, (l+r)/2,ind, t) + hap(seg[x].r,(l+r)/2+1,r,ind,t);
	}
}fen[300010];
void add(int x, int y, int t){
	//prl("add", "x=",x,"y=",y,"time=",t);
	for(;x<=n;x+=x&-x){
		fen[x].gang(1,1,n,y,t,-1);
	}
}
void del(int x, int y, int t, int bac){
	for(;x<=n;x+=x&-x) fen[x].gang(1,1,n,y,t,bac);
}
ll hap(int x, int y, int t){
	//prl("hap", x, y, t);
	ll ret=0;
	for(;x>=1;x-=x&-x){
		//prl("x=", x);
		ret += fen[x].hap(1,1,n,y,t);
	}
	return ret;
}
int main(){
	fastio;
	cin>>n>>q;
	cin>>in;
	int bac = 1;
	n++;
	for(int i=0;i<n-1;i++){
		cur[i+1]=in[i]-'0';
		if(in[i]=='0') {
			gang(1,1,n,bac,i+1,0);
			add(bac,n-i,0);
			bac = i+2;
		}
	}
	gang(1,1,n,bac,n,0);
	add(bac,1,0);
	for(int i=1;i<=q;i++){
		string c;int a, b;
		cin>>c;
		if(c[0]=='q'){
			cin>>a>>b;
			cout<<hap(a,n-b+1,i)<<"\n";
		}
		else{
			cin>>a;
			int l,r,x,t;
			if(cur[a]){
				tie(t,l,r) = get(1,1,n,a);
				del(l,n-r+1,i,t);
				gang(1,1,n,l,a,i);
				gang(1,1,n,a+1,r,i);
				add(l,n-a+1,i);
				add(a+1,n-r+1,i);
			}
			else{
				tie(t,l,x) = get(1,1,n,a);
				del(l,n-x+1,i,t);
				tie(t,x,r) = get(1,1,n,a+1);
				del(x,n-r+1,i,t);
				gang(1,1,n,l,r,i);
				add(l,n-r+1,i);
			}
			cur[a]=!cur[a];
		}
	}
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 21496 KB Output is correct
2 Correct 41 ms 21496 KB Output is correct
3 Correct 41 ms 21496 KB Output is correct
4 Correct 44 ms 21496 KB Output is correct
5 Correct 45 ms 21496 KB Output is correct
6 Correct 43 ms 21496 KB Output is correct
7 Correct 41 ms 21496 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 318 ms 24932 KB Output is correct
2 Correct 429 ms 25080 KB Output is correct
3 Correct 845 ms 30676 KB Output is correct
4 Correct 3562 ms 290004 KB Output is correct
5 Correct 2972 ms 254660 KB Output is correct
6 Correct 3827 ms 296900 KB Output is correct
7 Correct 1950 ms 334152 KB Output is correct
8 Correct 324 ms 25228 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 22264 KB Output is correct
2 Correct 47 ms 22136 KB Output is correct
3 Correct 47 ms 22012 KB Output is correct
4 Correct 41 ms 21496 KB Output is correct
5 Execution timed out 5078 ms 371128 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 21880 KB Output is correct
2 Correct 46 ms 21880 KB Output is correct
3 Correct 47 ms 22008 KB Output is correct
4 Correct 62 ms 22076 KB Output is correct
5 Correct 1054 ms 241044 KB Output is correct
6 Correct 2287 ms 273092 KB Output is correct
7 Correct 3656 ms 296204 KB Output is correct
8 Execution timed out 5085 ms 314132 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 21496 KB Output is correct
2 Correct 41 ms 21496 KB Output is correct
3 Correct 41 ms 21496 KB Output is correct
4 Correct 44 ms 21496 KB Output is correct
5 Correct 45 ms 21496 KB Output is correct
6 Correct 43 ms 21496 KB Output is correct
7 Correct 41 ms 21496 KB Output is correct
8 Correct 318 ms 24932 KB Output is correct
9 Correct 429 ms 25080 KB Output is correct
10 Correct 845 ms 30676 KB Output is correct
11 Correct 3562 ms 290004 KB Output is correct
12 Correct 2972 ms 254660 KB Output is correct
13 Correct 3827 ms 296900 KB Output is correct
14 Correct 1950 ms 334152 KB Output is correct
15 Correct 324 ms 25228 KB Output is correct
16 Correct 52 ms 22264 KB Output is correct
17 Correct 47 ms 22136 KB Output is correct
18 Correct 47 ms 22012 KB Output is correct
19 Correct 41 ms 21496 KB Output is correct
20 Execution timed out 5078 ms 371128 KB Time limit exceeded
21 Halted 0 ms 0 KB -