oj.uz

Submission #367795

# Submission time Handle Problem Language Result Execution time Memory
367795 2021-02-18T11:35:17 Z YJU Street Lamps (APIO19_street_lamps) C++14
20 / 100
 5000 ms 38972 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;

ll find_R(ll id,ll l,ll r,ll idx){
	for(int i=idx-1;i<=n;i++){
		if(state[i+1]==0)return i;
	}
}

ll find_L(ll id,ll l,ll r,ll idx){
	for(int i=idx+1;i>=1;i--){
		if(state[i-1]==0)return i;
	}
}

void upd(ll idx){
	state[idx]^=1;
}
/*
void build(ll id,ll l,ll r){
	if(l==r-1){QL[id]=l;QR[id]=l;return ;}
	ll mid=(l+r)>>1;
	build(id*2,l,mid);
	build(id*2+1,mid,r);
}*/

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>n>>q;
	//build(1,1,n+1);
	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(1,1,n+1,x)>=y){ans[i]+=i;}
			ioi.pb(mp(mp(i,x),mp(y,0)));
		}else{
			ty[i]=1;
			cin>>x;
			ll L=find_L(1,1,n+1,x-1),R=find_R(1,1,n+1,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;
}

Compilation message

street_lamps.cpp: In function 'll find_R(ll, ll, ll, ll)':
street_lamps.cpp:32:1: warning: control reaches end of non-void function [-Wreturn-type]
   32 | }
      | ^
street_lamps.cpp: In function 'll find_L(ll, ll, ll, ll)':
street_lamps.cpp:38:1: warning: control reaches end of non-void function [-Wreturn-type]
   38 | }
      | ^

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 364 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 5059 ms 38972 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 620 KB Output is correct
4 Correct 2 ms 492 KB Output is correct
5 Runtime error 10 ms 4608 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 3 ms 492 KB Output is correct
3 Correct 4 ms 620 KB Output is correct
4 Correct 1 ms 620 KB Output is correct
5 Runtime error 11 ms 4588 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 364 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 5059 ms 38972 KB Time limit exceeded
9 Halted 0 ms 0 KB -