Submission #132156

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
132156	2019-07-18T11:07:37 Z	MvC	Street Lamps (APIO19_street_lamps)	C++11	60 / 100	409 ms	17376 KB

street_lamps

#pragma GCC target("avx2")
#pragma GCC optimization("O3")
#pragma GCC optimization("unroll-loops")
#include<bits/stdc++.h>
//#include "aliens.h"
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define mkp make_pair
#define in insert
#define er erase
#define fd find
#define fr first
#define sc second
typedef long long ll;
typedef long double ld;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll llinf=(1LL<<62);
const int inf=(1<<30);
const int nmax=3e5+50;
const int mod=1e9+7;
using namespace std;
int n,q,a[nmax],nr[105][105],x,y,i,j,ta[nmax],tt[nmax],rs,sb2,t,b[nmax],sb3,st[4*nmax];
string s;
char c;
vector<pair<int,int> >qr;
void upd(int nod,int l,int r,int p,int v)
{
	if(l==r)
	{
		st[nod]=v;
		return;
	}
	int mid=(l+r)/2;
	if(p<=mid)upd(2*nod,l,mid,p,v);
	else upd(2*nod+1,mid+1,r,p,v);
	st[nod]=max(st[2*nod],st[2*nod+1]);
}
int qry(int nod,int l,int r,int tl,int tr)
{
	if(tr<l || tl>r)return 0;
	if(tl<=l && r<=tr)return st[nod];
	int mid=(l+r)/2;
	return max(qry(2*nod,l,mid,tl,tr),qry(2*nod+1,mid+1,r,tl,tr));
}
int main()
{
	//freopen("sol.in","r",stdin);
	//freopen("sol.out","w",stdout);
	//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
	cin>>n>>q;
	for(i=1;i<=n;i++)
	{
		cin>>c;
		a[i]=c-'0';
		b[i]=a[i];
	}
	sb2=1,sb3=1;
	for(i=1;i<=q;i++)
	{
		cin>>s;
		if(s[0]=='t')
		{
			cin>>x;
			b[x]^=1;
			if(!b[x])sb3=0;
			qr.pb(mkp(x,0));
		}
		else
		{
			cin>>x>>y;
			qr.pb(mkp(x,y));
			if(x+1!=y)sb2=0;
		}
	}
	if(sb2)
	{
		//cout<<1<<endl;
		for(i=1;i<=q;i++)
		{
			x=qr[i-1].fr,y=qr[i-1].sc;
			if(!y)
			{
				a[x]^=1;
				if(!a[x])tt[x]+=i-ta[x];
				else ta[x]=i;
			}
			else
			{
				rs=tt[x];
				if(a[x])rs+=i-ta[x];
				cout<<rs<<'\n';
			}
		}
	}
	else if(sb3)
	{
		for(i=1;i<=n;i++)
		{
			if(a[i])upd(1,1,n,i,0);
			else upd(1,1,n,i,inf);
		}
		for(i=1;i<=q;i++)
		{
			x=qr[i-1].fr,y=qr[i-1].sc;
			if(!y)
			{
				a[x]^=1;
				upd(1,1,n,x,i);
			}
			else
			{
				rs=qry(1,1,n,x,y-1);
				if(rs==inf)cout<<0<<'\n';
				else cout<<i-rs<<'\n';
			}
		}
	}
	else
	{
		for(t=0;t<q;t++)
		{
			for(i=1;i<=n;i++)
			{
				for(j=i;j<=n;j++)
				{
					if(!a[j])break;
					nr[i][j]++;
				}
			}
			x=qr[t].fr,y=qr[t].sc;
			if(!y)a[x]^=1;
			else cout<<nr[x][y-1]<<'\n';
		}
	}
    return 0;
}
/*
5 11
10010
q 1 2
q 2 3
q 3 4
q 4 5
q 5 6
t 1
q 1 2
t 2
q 2 3
t 2
q 2 3
*/

Compilation message

street_lamps.cpp:2:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization("O3")
 
street_lamps.cpp:3:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization("unroll-loops")

Subtask #1

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct

Subtask #2

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	88 ms	4684 KB	Output is correct
2	Correct	92 ms	4656 KB	Output is correct
3	Correct	97 ms	4656 KB	Output is correct
4	Correct	132 ms	8312 KB	Output is correct
5	Correct	131 ms	7352 KB	Output is correct
6	Correct	128 ms	8160 KB	Output is correct
7	Correct	135 ms	6964 KB	Output is correct
8	Correct	143 ms	7348 KB	Output is correct

Subtask #3

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	3 ms	380 KB	Output is correct
4	Correct	3 ms	376 KB	Output is correct
5	Correct	223 ms	13748 KB	Output is correct
6	Correct	261 ms	14444 KB	Output is correct
7	Correct	294 ms	14956 KB	Output is correct
8	Correct	330 ms	17376 KB	Output is correct
9	Correct	102 ms	6124 KB	Output is correct
10	Correct	113 ms	7656 KB	Output is correct
11	Correct	115 ms	7784 KB	Output is correct
12	Correct	409 ms	15912 KB	Output is correct
13	Correct	325 ms	17272 KB	Output is correct

Subtask #4

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	7 ms	760 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #5

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct
8	Correct	88 ms	4684 KB	Output is correct
9	Correct	92 ms	4656 KB	Output is correct
10	Correct	97 ms	4656 KB	Output is correct
11	Correct	132 ms	8312 KB	Output is correct
12	Correct	131 ms	7352 KB	Output is correct
13	Correct	128 ms	8160 KB	Output is correct
14	Correct	135 ms	6964 KB	Output is correct
15	Correct	143 ms	7348 KB	Output is correct
16	Correct	2 ms	376 KB	Output is correct
17	Correct	2 ms	376 KB	Output is correct
18	Correct	3 ms	380 KB	Output is correct
19	Correct	3 ms	376 KB	Output is correct
20	Correct	223 ms	13748 KB	Output is correct
21	Correct	261 ms	14444 KB	Output is correct
22	Correct	294 ms	14956 KB	Output is correct
23	Correct	330 ms	17376 KB	Output is correct
24	Correct	102 ms	6124 KB	Output is correct
25	Correct	113 ms	7656 KB	Output is correct
26	Correct	115 ms	7784 KB	Output is correct
27	Correct	409 ms	15912 KB	Output is correct
28	Correct	325 ms	17272 KB	Output is correct
29	Incorrect	7 ms	760 KB	Output isn't correct
30	Halted	0 ms	0 KB	-