#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-- )
{
//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 ) ;
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
381 ms |
28456 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
381 ms |
28456 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
381 ms |
28456 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
20 ms |
29004 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
