답안 #474120

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
474120 2021-09-17T01:20:20 Z CaroLinda Specijacija (COCI20_specijacija) C++14
0 / 110
4000 ms 50072 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 ;
int 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(int 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-- )
	{
		for(auto e : o_set ) 
			{
				cout << e <<": " ;
				for(auto ee : freq[e] ) cout << ee <<", " ;
				cout << endl ;
			}
		cout << endl ;
		
		//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])
		{
			locs[e.second].pb(N+2) ;
			freq[N+2].push_back( e.second )	;
			int k = *o_set.find_by_order(e.first) ;
			join(L[i]+e.first , N+2, k ) ;
		}
		
	}

	for(int i = 0 ; i < Q ; i++ ) printf("%d\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 ) ;
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4069 ms 50072 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4069 ms 50072 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4069 ms 50072 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Runtime error 26 ms 28956 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -