oj.uz

Submission #202192

# Submission time Handle Problem Language Result Execution time Memory
202192 2020-02-14T05:14:07 Z red1108 Street Lamps (APIO19_street_lamps) C++17
40 / 100
 5000 ms 524288 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;
	ll 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 51 ms 30904 KB Output is correct
2 Correct 47 ms 30840 KB Output is correct
3 Correct 52 ms 30968 KB Output is correct
4 Correct 52 ms 30968 KB Output is correct
5 Correct 51 ms 30968 KB Output is correct
6 Correct 52 ms 30968 KB Output is correct
7 Correct 47 ms 30844 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 322 ms 35320 KB Output is correct
2 Correct 416 ms 35964 KB Output is correct
3 Correct 900 ms 45036 KB Output is correct
4 Correct 3875 ms 451032 KB Output is correct
5 Correct 3161 ms 395560 KB Output is correct
6 Correct 4045 ms 462552 KB Output is correct
7 Correct 2098 ms 521536 KB Output is correct
8 Correct 351 ms 40460 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 31992 KB Output is correct
2 Correct 54 ms 31864 KB Output is correct
3 Correct 55 ms 31608 KB Output is correct
4 Correct 48 ms 30840 KB Output is correct
5 Runtime error 3446 ms 524288 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 31480 KB Output is correct
2 Correct 54 ms 31608 KB Output is correct
3 Correct 56 ms 31864 KB Output is correct
4 Correct 56 ms 31736 KB Output is correct
5 Correct 1119 ms 375920 KB Output is correct
6 Correct 2427 ms 426124 KB Output is correct
7 Correct 3854 ms 462144 KB Output is correct
8 Execution timed out 5088 ms 486960 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 30904 KB Output is correct
2 Correct 47 ms 30840 KB Output is correct
3 Correct 52 ms 30968 KB Output is correct
4 Correct 52 ms 30968 KB Output is correct
5 Correct 51 ms 30968 KB Output is correct
6 Correct 52 ms 30968 KB Output is correct
7 Correct 47 ms 30844 KB Output is correct
8 Correct 322 ms 35320 KB Output is correct
9 Correct 416 ms 35964 KB Output is correct
10 Correct 900 ms 45036 KB Output is correct
11 Correct 3875 ms 451032 KB Output is correct
12 Correct 3161 ms 395560 KB Output is correct
13 Correct 4045 ms 462552 KB Output is correct
14 Correct 2098 ms 521536 KB Output is correct
15 Correct 351 ms 40460 KB Output is correct
16 Correct 59 ms 31992 KB Output is correct
17 Correct 54 ms 31864 KB Output is correct
18 Correct 55 ms 31608 KB Output is correct
19 Correct 48 ms 30840 KB Output is correct
20 Runtime error 3446 ms 524288 KB Execution killed with signal 9 (could be triggered by violating memory limits)
21 Halted 0 ms 0 KB -