oj.uz

Submission #254855

# Submission time Handle Problem Language Result Execution time Memory
254855 2020-07-30T18:15:22 Z Lawliet Street Lamps (APIO19_street_lamps) C++17
20 / 100
 1575 ms 10780 KB 
#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.0

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

Subtask #2
0 / 20.0

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

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 538 ms 7032 KB Output is correct
6 Correct 810 ms 7832 KB Output is correct
7 Correct 1111 ms 8440 KB Output is correct
8 Correct 1575 ms 10744 KB Output is correct
9 Correct 757 ms 3960 KB Output is correct
10 Correct 799 ms 4600 KB Output is correct
11 Correct 802 ms 4832 KB Output is correct
12 Correct 1349 ms 9464 KB Output is correct
13 Correct 1567 ms 10780 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Incorrect 3 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

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