Submission #254869

#	Time	Username	Problem	Language	Result	Execution time	Memory
254869		Lawliet	Bridges (APIO19_bridges)	C++17	16 / 100	135 ms	4344 KiB

bridges

#include <bits/stdc++.h>

using namespace std;
typedef pair<int,int> pii;

const int SQRT = 500;
const int MAXN = 50010;
const int MAXQ = 100010;

int n, m, q;
int raiz;

int indBucket[MAXN];
int endBucket[SQRT];
int startBucket[SQRT];
int v[MAXN], mn[SQRT];
int U[MAXN], V[MAXN], W[MAXN];

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

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

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

int bsRight(int i, int w)
{
	if( i >= n - 1 ) return n - 1;

	int bI = indBucket[i];

	for(int j = i ; j <= endBucket[bI] ; j++)
		if( v[j] < w ) return j;

	int first = -1;

	for(int j = bI + 1 ; j <= indBucket[n - 2] ; j++)
	{
		if( mn[j] < w )
		{
			first = j;
			break;
		}
	}

	if( first == -1 ) return n - 1;//Ver aqui

	for(int j = startBucket[first] ; j <= endBucket[first] ; j++)
		if( v[j] < w ) return j;
}

int bsLeft(int i, int w)
{
	if( i < 0 ) return -1;

	int bI = indBucket[i];

	for(int j = i ; j >= startBucket[bI] ; j--)
		if( v[j] < w ) return j;

	int first = -1;

	for(int j = bI - 1 ; j >= 0 ; j--)
	{
		if( mn[j] < w )
		{
			first = j;
			break;
		}
	}

	if( first == -1 ) return -1;//Ver aqui

	for(int j = endBucket[first] ; j >= startBucket[first] ; j--)
		if( v[j] < w ) return j;
}

int main()
{
	scanf("%d %d",&n,&m);

	raiz = sqrt(n - 1) + 1;

	for(int i = 0 ; i < n - 1 ; i++)
		indBucket[i] = i/raiz;

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

	for(int i = 1 ; i <= m ; i++)
	{
		scanf("%d %d %d",&U[i],&V[i],&W[i]);
		update( U[i] - 1 , W[i] );
	}

	scanf("%d",&q);
 
	for(int i = 1 ; i <= q ; i++)
	{
		int type;
		scanf("%d",&type);
 
		if( type == 1 )
		{
			int ind, newW;
			scanf("%d %d",&ind,&newW);

			update( U[ind] - 1 , newW );
		}
		if( type == 2 )
		{
			int s, maxW;
			scanf("%d %d",&s,&maxW);

			printf("%d\n",bsRight( s - 1 , maxW ) - bsLeft( s - 2 , maxW ));//Ver convenção
		}
	}
}

Compilation message (stderr)

bridges.cpp: In function 'int bsRight(int, int)':
bridges.cpp:54:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
bridges.cpp: In function 'int bsLeft(int, int)':
bridges.cpp:80:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
bridges.cpp: In function 'int main()':
bridges.cpp:84:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n,&m);
  ~~~~~^~~~~~~~~~~~~~~
bridges.cpp:99:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d",&U[i],&V[i],&W[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:103:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&q);
  ~~~~~^~~~~~~~~
bridges.cpp:108:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&type);
   ~~~~~^~~~~~~~~~~~
bridges.cpp:113:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d",&ind,&newW);
    ~~~~~^~~~~~~~~~~~~~~~~~~~
bridges.cpp:120:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d",&s,&maxW);
    ~~~~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 13
• Subtask 2: 16 / 16
• Subtask 3: 0 / 17
• Subtask 4: 0 / 14
• Subtask 5: 0 / 13
• Subtask 6: 0 / 27