oj.uz

Submission #474130

# Submission time Handle Problem Language Result Execution time Memory
474130 2021-09-17T01:50:00 Z CaroLinda Specijacija (COCI20_specijacija) C++14
50 / 110
 1889 ms 62612 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 )
		{
			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

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 459 ms 28460 KB Output is correct
2 Correct 26 ms 15564 KB Output is correct
3 Correct 435 ms 28576 KB Output is correct
4 Correct 192 ms 22064 KB Output is correct
5 Correct 406 ms 28392 KB Output is correct
6 Correct 98 ms 18908 KB Output is correct
7 Correct 260 ms 28476 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 459 ms 28460 KB Output is correct
2 Correct 26 ms 15564 KB Output is correct
3 Correct 435 ms 28576 KB Output is correct
4 Correct 192 ms 22064 KB Output is correct
5 Correct 406 ms 28392 KB Output is correct
6 Correct 98 ms 18908 KB Output is correct
7 Correct 260 ms 28476 KB Output is correct
8 Correct 353 ms 35764 KB Output is correct
9 Correct 320 ms 34212 KB Output is correct
10 Correct 347 ms 38596 KB Output is correct
11 Correct 315 ms 33524 KB Output is correct
12 Correct 349 ms 38484 KB Output is correct
13 Correct 303 ms 34572 KB Output is correct
14 Correct 294 ms 34188 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 459 ms 28460 KB Output is correct
2 Correct 26 ms 15564 KB Output is correct
3 Correct 435 ms 28576 KB Output is correct
4 Correct 192 ms 22064 KB Output is correct
5 Correct 406 ms 28392 KB Output is correct
6 Correct 98 ms 18908 KB Output is correct
7 Correct 260 ms 28476 KB Output is correct
8 Correct 353 ms 35764 KB Output is correct
9 Correct 320 ms 34212 KB Output is correct
10 Correct 347 ms 38596 KB Output is correct
11 Correct 315 ms 33524 KB Output is correct
12 Correct 349 ms 38484 KB Output is correct
13 Correct 303 ms 34572 KB Output is correct
14 Correct 294 ms 34188 KB Output is correct
15 Correct 1654 ms 62228 KB Output is correct
16 Correct 918 ms 47248 KB Output is correct
17 Correct 1889 ms 62168 KB Output is correct
18 Correct 928 ms 47524 KB Output is correct
19 Correct 1513 ms 62612 KB Output is correct
20 Correct 810 ms 47332 KB Output is correct
21 Correct 1090 ms 51996 KB Output is correct

Subtask #4
0 / 60.0

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