oj.uz

Submission #475546

# Submission time Handle Problem Language Result Execution time Memory
475546 2021-09-22T20:13:29 Z CaroLinda Specijacija (COCI20_specijacija) C++14
10 / 110
 2560 ms 245944 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-- ) 
		for(auto e : adj[i])
			if(lvl[e] >0 ) lvl[i] = lvl[e]+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 ;
		
		int idx = getComponent(x) ;
		int idy = getComponent(y) ;
				
		if(idx == idy ) z = min(x,y) ;
		else z = resp[getLca( idx , idy ) ] ;
		
		printf("%lld\n" , z ) ;
		
	}
	
}

Compilation message

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1041 ms 243688 KB Output is correct
2 Correct 56 ms 19792 KB Output is correct
3 Correct 1042 ms 245888 KB Output is correct
4 Correct 501 ms 128416 KB Output is correct
5 Correct 1107 ms 245880 KB Output is correct
6 Correct 261 ms 72292 KB Output is correct
7 Correct 678 ms 245944 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1041 ms 243688 KB Output is correct
2 Correct 56 ms 19792 KB Output is correct
3 Correct 1042 ms 245888 KB Output is correct
4 Correct 501 ms 128416 KB Output is correct
5 Correct 1107 ms 245880 KB Output is correct
6 Correct 261 ms 72292 KB Output is correct
7 Correct 678 ms 245944 KB Output is correct
8 Incorrect 199 ms 4432 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1041 ms 243688 KB Output is correct
2 Correct 56 ms 19792 KB Output is correct
3 Correct 1042 ms 245888 KB Output is correct
4 Correct 501 ms 128416 KB Output is correct
5 Correct 1107 ms 245880 KB Output is correct
6 Correct 261 ms 72292 KB Output is correct
7 Correct 678 ms 245944 KB Output is correct
8 Incorrect 199 ms 4432 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Incorrect 2560 ms 244248 KB Output isn't correct
2 Halted 0 ms 0 KB -