Submission #474130

#	Time	Username	Problem	Language	Result	Execution time	Memory
474130		CaroLinda	Specijacija (COCI20_specijacija)	C++14	50 / 110	1889 ms	62612 KiB

Main

#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 )
		{
			ans[i] = 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 (stderr)

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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 30 / 30
• Subtask 4: 0 / 60