oj.uz

Submission #367806

# Submission time Handle Problem Language Result Execution time Memory
367806 2021-02-18T12:22:10 Z YJU Street Lamps (APIO19_street_lamps) C++14
20 / 100
 5000 ms 36488 KB 
#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector,Ofast")
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
const ll MOD=1e9+7;
const ll MOD2=998244353;
const ll N=2e5+5;
const ld pi=acos(-1);
const ll INF=(1LL<<60);
#define SQ(i) ((i)*(i))
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define setp setprecision
#define lwb lower_bound
#define SZ(_a) (ll)_a.size()
 
char c;
ll n,q,x,y,state[N],ans[N],ty[N];
string s;
vector<pair<pll,pll> > ioi;
set<ll> loc;
 
ll find_R(ll idx){
	return *loc.lwb(idx)-1;
}
 
ll find_L(ll idx){
	return *prev(loc.lwb(idx+1))+1;
}
 
void upd(ll idx){
	state[idx]^=1;
	if(state[idx]==0){
		loc.insert(idx);
	}else{
		loc.erase(idx);
	}
}
 
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>n>>q;
	REP(i,n+2)loc.insert(i);
	REP1(i,n){
		cin>>c;
		if(c=='1')upd(i);
	}
	REP1(i,q){
		cin>>s;
		if(s[0]=='q'){
			ty[i]=2;
			cin>>x>>y;
			--y;
			///cout<<"query "<<i<<" "<<x<<" "<<y<<" "<<find_R(1,1,n+1,x)<<"\n";
			if(find_R(x)>=y){ans[i]+=i;}
			ioi.pb(mp(mp(i,x),mp(y,0)));
		}else{
			ty[i]=1;
			cin>>x;
			ll L=find_L(x-1),R=find_R(x+1);
			//cout<<x<<" "<<L<<" "<<R<<"\n";
			if(state[x]==0){
				//[L,x] [x,R]-=i;
				ioi.pb(mp(mp(i,L),mp(x,-1)));
				ioi.pb(mp(mp(i,L),mp(R+1,1)));
				ioi.pb(mp(mp(i,x+1),mp(x,1)));
				ioi.pb(mp(mp(i,x+1),mp(R+1,-1)));
			}else{
				//[L,x] [x,R] +=i ;
				ioi.pb(mp(mp(i,L),mp(x,1)));
				ioi.pb(mp(mp(i,L),mp(R+1,-1)));
				ioi.pb(mp(mp(i,x+1),mp(x,-1)));
				ioi.pb(mp(mp(i,x+1),mp(R+1,1)));
			}
			upd(x);
		}
	}
	sort(ioi.begin(),ioi.end());
	REP(i,SZ(ioi)){
		if(ioi[i].Y.Y==0){
			REP(j,i){
				if(ioi[j].Y.Y!=0&&ioi[j].X.Y<=ioi[i].X.Y&&ioi[j].Y.X<=ioi[i].Y.X){
					ans[ioi[i].X.X]+=(ioi[j].X.X*ioi[j].Y.Y);
				}
			}
		}
	}
	REP1(i,q){
		if(ty[i]==2)cout<<ans[i]<<"\n";
	}
	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 384 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5060 ms 36488 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 620 KB Output is correct
2 Correct 3 ms 620 KB Output is correct
3 Correct 4 ms 640 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Runtime error 94 ms 32748 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 492 KB Output is correct
2 Correct 4 ms 640 KB Output is correct
3 Correct 4 ms 620 KB Output is correct
4 Correct 2 ms 620 KB Output is correct
5 Runtime error 104 ms 32236 KB Execution killed with signal 11
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 384 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Execution timed out 5060 ms 36488 KB Time limit exceeded
9 Halted 0 ms 0 KB -