Submission #254855

#	Time	Username	Problem	Language	Result	Execution time	Memory
254855		Lawliet	Street Lamps (APIO19_street_lamps)	C++17	20 / 100	1575 ms	10780 KiB

street_lamps

#include <bits/stdc++.h>
 
using namespace std;
 
const int SQRT = 1010;
const int MAXN = 300010;
const int INF = 1000000010;
 
int n, q;
int raiz;
 
int indBucket[MAXN];
int endBucket[SQRT];
int startBucket[SQRT];
int v[MAXN], mx[SQRT];

string s;
 
void update(int ind, int val)
{
	v[ind] = val;

	int b = indBucket[ind];
	mx[ indBucket[ind] ] = val;

	for(int i = startBucket[b] ; i <= endBucket[b] ; i++)
		mx[b] = max( mx[b] , v[i] );
}

int query(int L, int R)
{
	int bL = indBucket[L];
	int bR = indBucket[R];
	int ans = 0;

	for(int i = L ; i <= endBucket[bL] && i <= R ; i++)
		ans = max( ans , v[i] );

	for(int i = bL + 1 ; i < bR ; i++)
		ans = max( ans , mx[i] );

	for(int i = R ; i >= startBucket[bR] && i >= L ; i--)
		ans = max( ans , v[i] );

	return ans;
}

int main()
{
	cin >> n >> q;

	raiz = sqrt(n) + 1;

	for(int i = 0 ; i < n ; i++)
	{
		v[i] = INF;
		indBucket[i] = i/raiz;
	}

	for(int i = 0 ; i <= indBucket[n - 1] ; i++)
	{
		mx[i] = INF;
		startBucket[i] = i*raiz;
		endBucket[i] = min( n - 1 , (i + 1)*raiz - 1 );
	}

	for(int i = 0 ; i < n ; i++)
	{
		char c;
		cin >> c;

		if( c == '1' )
			update( i , 0 );
	}
 
	for(int i = 1 ; i <= q ; i++)
	{
		string type;
		cin >> type;
  
		if( type == "toggle" )
		{
			int ind;
			cin >> ind; ind--;

			update( ind , i );
		}
		if( type == "query" )
		{
			int l, r;
			cin >> l >> r; l--; r--;
  
			int minTime = query( l , r - 1 );

			if( minTime == INF ) printf("0\n");
			else printf("%d\n",i - minTime);
 		}
	}
}

• Subtask 1: 0 / 20
• Subtask 2: 0 / 20
• Subtask 3: 20 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20