oj.uz

Submission #474125

# Submission time Handle Problem Language Result Execution time Memory
474125 2021-09-17T01:33:46 Z CaroLinda Specijacija (COCI20_specijacija) C++14
10 / 110
 395 ms 38336 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define sz(x) (int)(x.size())
#define debug printf
#define lp(i,a,b) for(int i = a ; i < b; i++)
#define pb push_back
#define ff first
#define ss second
#define mk make_pair
#define pii pair<int,int>
#define ll long long 
#define all(x) x.begin(),x.end()

const int MAXN = 2e5+10 ;

using namespace std ;
using namespace __gnu_pbds;

#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>

int N , Q , T ;
ll ans[MAXN] ;
ll L[MAXN] , R[MAXN] ;
ll A[MAXN] ;
vector< pair<int,int> > levels[MAXN] ;
vector<int> freq[MAXN] ;
ordered_set o_set ;
vector<int> locs[MAXN] ;

pair<int,int> getCoords(ll x)
{
	int a = upper_bound(L+1, L+3+N , x ) - L- 1; 
	int b = x-L[a]+1 ;
	return make_pair(a,b) ;
}

int join(ll guy, int x, int y ) //se tiver empate, eu coloco o v1 no v2
{

	if(sz(freq[x]) > sz(freq[y])) swap(x,y) ;
		
	for(auto e : freq[x] )
	{
		if(ans[e]) continue ;

		if( sz(locs[e]) > 1 && locs[e][0] != x)
			swap(locs[e][0] , locs[e][1]) ;

		locs[e][0] = y ;
		if( sz(locs[e]) > 1 && locs[e][0] == locs[e][1] )
		{
			ans[e] = guy ;
			continue ;
		}

		freq[y].push_back(e) ;
		
	}

	freq[x].clear() ;
	
	return y ;
}

int main()
{
	scanf("%d %d %d", &N, &Q, &T ) ;
	
	assert(T == 0 ) ;
	
	L[1] = R[1] = 1 ;
	for(int i = 2 ; i <= N+2 ; i++ )
	{
		L[i] = R[i-1]+1 ;
		R[i] = L[i]+i-1 ;
	}
	
	for(int i = 1 ; i <= N ; i++ ) scanf("%lld", &A[i] ) ;
	for(int i = 0; i < Q ; i++ )
	{
		ll a , b ;
		scanf("%lld %lld", &a, &b ) ;

		if(a == b )
		{
			printf("%lld\n" , a ) ;
			continue ;
		}
		
		pair<int,int> ca = getCoords(a) ;
		pair<int,int> cb = getCoords(b) ;
		
		levels[ca.first].pb( make_pair(ca.second-1, i) );
		levels[cb.first].pb(make_pair(cb.second-1, i)) ;	
	}
	
	for(int i = 0 ; i < N+1 ; i++ ) o_set.insert(i) ;
	for(auto e : levels[N+1]) 
	{
		freq[e.first].push_back(e.second) ;
		locs[e.second].push_back(e.first) ;
	}


	for(int i = N ; i > 0 ; i-- )
	{

		
		//tenho que juntar com o vermelho de agora
		int y = getCoords(A[i]).second ;

		auto it = o_set.find_by_order(y-1) ;
		int a = *it ;
		it++ ;
		int b = *it ;
		
		if( join( A[i] , a , b) == a ) swap(a,b) ;

		o_set.erase( o_set.find(a) ) ;
		
		for(auto e : levels[i])
		{

			int k = *o_set.find_by_order(e.first) ;

			if( sz(freq[k]) == 0 )
			{
				freq[k] = {e.second} ;
				locs[e.second].pb(k) ;
				continue ;
			}
			
			locs[e.second].pb(N+2) ;
			freq[N+2] = {e.second } ;
			join(L[i]+e.first , N+2, k ) ;
		}
		
	}

	for(int i = 0 ; i < Q ; i++ ) printf("%lld\n" , ans[i]) ;
	
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:69:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |  scanf("%d %d %d", &N, &Q, &T ) ;
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:80:38: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |  for(int i = 1 ; i <= N ; i++ ) scanf("%lld", &A[i] ) ;
      |                                 ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:84:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |   scanf("%lld %lld", &a, &b ) ;
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 385 ms 28460 KB Output is correct
2 Correct 25 ms 15564 KB Output is correct
3 Correct 395 ms 28460 KB Output is correct
4 Correct 169 ms 22156 KB Output is correct
5 Correct 394 ms 28468 KB Output is correct
6 Correct 94 ms 18884 KB Output is correct
7 Correct 252 ms 28416 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 385 ms 28460 KB Output is correct
2 Correct 25 ms 15564 KB Output is correct
3 Correct 395 ms 28460 KB Output is correct
4 Correct 169 ms 22156 KB Output is correct
5 Correct 394 ms 28468 KB Output is correct
6 Correct 94 ms 18884 KB Output is correct
7 Correct 252 ms 28416 KB Output is correct
8 Correct 364 ms 38336 KB Output is correct
9 Incorrect 332 ms 36492 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 385 ms 28460 KB Output is correct
2 Correct 25 ms 15564 KB Output is correct
3 Correct 395 ms 28460 KB Output is correct
4 Correct 169 ms 22156 KB Output is correct
5 Correct 394 ms 28468 KB Output is correct
6 Correct 94 ms 18884 KB Output is correct
7 Correct 252 ms 28416 KB Output is correct
8 Correct 364 ms 38336 KB Output is correct
9 Incorrect 332 ms 36492 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Runtime error 21 ms 29004 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -