oj.uz

Submission #202197

# Submission time Handle Problem Language Result Execution time Memory
202197 2020-02-14T05:28:04 Z red1108 Street Lamps (APIO19_street_lamps) C++17
40 / 100
 5000 ms 355432 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-x+(x&-x)+1,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-x+(x&-x)+1,y,t,bac);
}
ll hap(int x, int y, int t){
	ll ret=0;
	for(;x>=1;x-=x&-x) ret += fen[x].hap(1,1,n-x+(x&-x)+1,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 42 ms 21496 KB Output is correct
2 Correct 48 ms 21496 KB Output is correct
3 Correct 42 ms 21496 KB Output is correct
4 Correct 44 ms 21496 KB Output is correct
5 Correct 45 ms 21624 KB Output is correct
6 Correct 45 ms 21496 KB Output is correct
7 Correct 43 ms 21496 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 310 ms 22656 KB Output is correct
2 Correct 413 ms 25336 KB Output is correct
3 Correct 798 ms 30164 KB Output is correct
4 Correct 3377 ms 278720 KB Output is correct
5 Correct 2824 ms 240384 KB Output is correct
6 Correct 3683 ms 285508 KB Output is correct
7 Correct 1827 ms 321456 KB Output is correct
8 Correct 315 ms 25228 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 22136 KB Output is correct
2 Correct 49 ms 22136 KB Output is correct
3 Correct 47 ms 21884 KB Output is correct
4 Correct 41 ms 21496 KB Output is correct
5 Execution timed out 5104 ms 355432 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 21880 KB Output is correct
2 Correct 47 ms 21880 KB Output is correct
3 Correct 49 ms 22008 KB Output is correct
4 Correct 47 ms 22008 KB Output is correct
5 Correct 1025 ms 230976 KB Output is correct
6 Correct 2241 ms 262596 KB Output is correct
7 Correct 3539 ms 284836 KB Output is correct
8 Execution timed out 5083 ms 304188 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 21496 KB Output is correct
2 Correct 48 ms 21496 KB Output is correct
3 Correct 42 ms 21496 KB Output is correct
4 Correct 44 ms 21496 KB Output is correct
5 Correct 45 ms 21624 KB Output is correct
6 Correct 45 ms 21496 KB Output is correct
7 Correct 43 ms 21496 KB Output is correct
8 Correct 310 ms 22656 KB Output is correct
9 Correct 413 ms 25336 KB Output is correct
10 Correct 798 ms 30164 KB Output is correct
11 Correct 3377 ms 278720 KB Output is correct
12 Correct 2824 ms 240384 KB Output is correct
13 Correct 3683 ms 285508 KB Output is correct
14 Correct 1827 ms 321456 KB Output is correct
15 Correct 315 ms 25228 KB Output is correct
16 Correct 54 ms 22136 KB Output is correct
17 Correct 49 ms 22136 KB Output is correct
18 Correct 47 ms 21884 KB Output is correct
19 Correct 41 ms 21496 KB Output is correct
20 Execution timed out 5104 ms 355432 KB Time limit exceeded
21 Halted 0 ms 0 KB -