oj.uz

Submission #475547

# Submission time Handle Problem Language Result Execution time Memory
475547 2021-09-22T20:20:38 Z CaroLinda Specijacija (COCI20_specijacija) C++14
110 / 110
 2573 ms 252224 KB 
#include <bits/stdc++.h>

#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 ;
const int LOG =20 ;

using namespace std ;

struct Seg
{
	
	vector<int> e , d , val , sub ;
	
	Seg() 
	{
		e.pb(0) ;
		d.pb(0) ;
		val.pb(0) ;
		sub.pb(0) ;
	}
	
	int m(int l, int r) { return (l+r)>>1 ; }
	int create_and_copy(int pos)
	{
		e.push_back(e[pos]) ;
		d.pb(d[pos]) ;
		val.pb(val[pos]) ;
		sub.pb(sub[pos]) ;
		
		return sz(e)-1 ;
	}
	
	int upd(int pos, int l, int r, int x, int _val , int _sub )
	{
		int newPos = create_and_copy(pos) ;	
		
		if(l == r )
		{
			sub[newPos] = _sub ;
			val[newPos] = _val ;
			return newPos ;
		}
		
		int aux ;
		if(x <= m(l,r))
		{
			aux = upd(e[newPos],l,m(l,r) , x, _val, _sub ) ;
			e[newPos] = aux ;
		}
		else
		{
			aux = upd(d[newPos] , m(l,r)+1, r, x, _val, _sub ) ;
			d[newPos] = aux ;
		}
		
		sub[newPos] = sub[e[newPos]]+sub[d[newPos]] ;
		return newPos ;
	}
	
	pair<int,int> bb(int pos, int l, int r, int x )
	{
		
		if( l == r ) return make_pair( l , val[pos] ) ;
		if( sub[e[pos]] < x ) return bb(d[pos], m(l,r)+1, r, x-sub[e[pos]]) ;
		
		return bb(e[pos] , l , m(l,r) , x ) ;
	}
		
} seg ;

int N , Q , T ;
int rt[MAXN] ;
vector<int> dp[LOG] ;
vector<int> lvl(1,0) ;
ll A[MAXN] , L[MAXN] ;
vector< vector<int> > adj(1, vector<int>() ) ;
vector<ll> resp(1, 0) ;

int create(ll k)
{
	adj.push_back( vector<int>() )	;
	resp.push_back(k) ;

	for(int i = 0 ; i < LOG ; i++ )
		while( sz(dp[i]) != sz(adj) ) dp[i].push_back(-1) ;
		
	lvl.pb(0) ;
	
	return sz(adj)-1 ;
}

ll getRow(ll x) { return upper_bound( L+1, L+2+N , x ) - L - 1 ; }
ll getColumn(ll x) 
{
	int idx = getRow(x) ;
	return x-L[idx]+1 ;
}
void createEdge(int a, int b)
{
	adj[a].pb(b) ;
	adj[b].pb(a) ;
}

int getComponent(ll x )
{
	int r = getRow(x) ;
	int c = getColumn(x) ;
	
	return seg.bb(rt[r],1,N+1, c).second ;
	
}

int getLca(int x, int y)
{
	if(lvl[x] < lvl[y]) swap(x,y) ;
	
	for(int i= LOG-1 ; i >= 0 ; i-- )
		if( dp[i][x] != -1 && lvl[ dp[i][x] ] >= lvl[y] )
			x = dp[i][x] ;
			
	if(x == y ) return y ;
	
	for(int i = LOG-1 ; i >= 0 ; i-- )
		if(dp[i][x] != -1 && dp[i][x] != dp[i][y])
		{
			x= dp[i][x] ;
			y = dp[i][y] ;
		}
		
	return dp[0][x] ;
}

int main()
{
	scanf("%d %d %d", &N, &Q, &T ) ;
	
	for(int i = 1 ; i <= N ; i++ ) scanf("%lld", &A[i]) ;
	
	L[0] = 1 ;
	for(int i = 1 ; i  <= N+1 ; i++ ) L[i] = L[i-1]+i-1 ;
	
	for(int i = 1 ; i <= N+1 ; i++ ) 
	{
		rt[N+1] = seg.upd( rt[N+1] , 1 , N+1, i, i, 1 ) ;
		create( L[N+1]+i-1 ) ;
	}
		
	for(int i = N ; i > 0 ; i-- )
	{
		ll y = getColumn(A[i]) ;
		
		int newId = create(A[i]) ;
		
		rt[i] = rt[i+1] ;
		
		pair<int,int> a = seg.bb( rt[i] , 1 , N+1, y ) ;
		pair<int,int> b = seg.bb(rt[i] , 1 , N+1, y+1 ) ;
				
		rt[i] = seg.upd( rt[i] , 1 , N+1 , b.first, 0, 0 ) ;
		rt[i] = seg.upd( rt[i] , 1 , N+1 , a.first , newId, 1 ) ;
		
		dp[0][a.second] = dp[0][b.second] = newId ;
		
		createEdge(newId, a.second) ;
		createEdge(newId, b.second ) ;
		
	}
	
	for(int j = 1 ; j < LOG ; j++ )
		for(int i = 1 ; i < sz(adj)  ; i++ )
			if( dp[j-1][i] != -1 )
				dp[j][i] = dp[j-1][ dp[j-1][i] ] ;
	
	lvl[sz(adj)-1] = 1 ;
	for(int i = sz(adj)-2 ; i > 0 ; i-- ) 
		lvl[i] = lvl[ dp[0][i] ]+1 ;
	
	ll z = 0 ;
	ll m = (ll)(N+1) ; m *= (ll)(N+2) ; m >>= 1LL ;
	
	while(Q--)
	{
		ll x , y ;
		scanf("%lld %lld", &x, &y ) ;
		
		x = ( (x-1+z*T)%m ) + 1 ;
		y = ( (y-1+z*T)%m ) + 1 ;
		
		if(x < y ) swap(x,y) ;
		
		int idx = getComponent(x) ;
		int idy = getComponent(y) ;
				
		int aux = getLca( idx , idy ) ;
		
		if( aux ==  idy ) z = y ;
		else z = resp[aux] ;
		
		printf("%lld\n" , z ) ;
		
	}
	
}

/*
4 1 0
1 2 5 7
11 4
*/

Compilation message

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1173 ms 243684 KB Output is correct
2 Correct 68 ms 19900 KB Output is correct
3 Correct 1131 ms 243664 KB Output is correct
4 Correct 652 ms 127360 KB Output is correct
5 Correct 1136 ms 243728 KB Output is correct
6 Correct 316 ms 71612 KB Output is correct
7 Correct 754 ms 243596 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1173 ms 243684 KB Output is correct
2 Correct 68 ms 19900 KB Output is correct
3 Correct 1131 ms 243664 KB Output is correct
4 Correct 652 ms 127360 KB Output is correct
5 Correct 1136 ms 243728 KB Output is correct
6 Correct 316 ms 71612 KB Output is correct
7 Correct 754 ms 243596 KB Output is correct
8 Correct 212 ms 1752 KB Output is correct
9 Correct 180 ms 3788 KB Output is correct
10 Correct 212 ms 4556 KB Output is correct
11 Correct 131 ms 2640 KB Output is correct
12 Correct 219 ms 4532 KB Output is correct
13 Correct 151 ms 3268 KB Output is correct
14 Correct 222 ms 5048 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1173 ms 243684 KB Output is correct
2 Correct 68 ms 19900 KB Output is correct
3 Correct 1131 ms 243664 KB Output is correct
4 Correct 652 ms 127360 KB Output is correct
5 Correct 1136 ms 243728 KB Output is correct
6 Correct 316 ms 71612 KB Output is correct
7 Correct 754 ms 243596 KB Output is correct
8 Correct 212 ms 1752 KB Output is correct
9 Correct 180 ms 3788 KB Output is correct
10 Correct 212 ms 4556 KB Output is correct
11 Correct 131 ms 2640 KB Output is correct
12 Correct 219 ms 4532 KB Output is correct
13 Correct 151 ms 3268 KB Output is correct
14 Correct 222 ms 5048 KB Output is correct
15 Correct 2486 ms 250868 KB Output is correct
16 Correct 1170 ms 57784 KB Output is correct
17 Correct 2522 ms 250828 KB Output is correct
18 Correct 1255 ms 57824 KB Output is correct
19 Correct 2573 ms 250736 KB Output is correct
20 Correct 1144 ms 49836 KB Output is correct
21 Correct 2347 ms 252224 KB Output is correct

Subtask #4
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 2509 ms 244084 KB Output is correct
2 Correct 1776 ms 121024 KB Output is correct
3 Correct 2572 ms 250764 KB Output is correct
4 Correct 1650 ms 117524 KB Output is correct
5 Correct 2473 ms 250776 KB Output is correct
6 Correct 1816 ms 130344 KB Output is correct
7 Correct 2294 ms 252212 KB Output is correct