#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define debug printf
#define ff first
#define ss second
#define mk make_pair
#define lp(i,a,b) for(int i = a ; i < b ; i++)
#define pii pair<int,int>
#define pb push_back
#define all(x) x.begin(),x.end()
const int MAXN = 1e5+10 ;
const int INF = 1e9+10 ;
using namespace std ;
using namespace __gnu_pbds ;
#define ordered_set tree<pii, null_type,less<pii>, rb_tree_tag,tree_order_statistics_node_update>
// -------------------------------------------_
int mn_global[MAXN] ;
struct Vez
{
int falta , N ;
int maior[MAXN] ;
vector<int> seq ;
vector< pair<int,int> > queries ;
int mn[MAXN*4] , resp[MAXN] , bit[MAXN] ;
void print_info()
{
debug("Falta eh %d\n" , falta ) ;
debug("Seq: ") ;
for(auto p : seq ) debug("%d " , p) ;
debug("\nQueries:\n") ;
for(auto p : queries ) debug("%d %d\n" , p.ff, p.ss ) ;
debug("Maior: ") ;
lp(i,0,N) debug("%d ", maior[i] );
debug("\n") ;
debug("Resp: ") ;
lp(i,0,N) debug("%d " , resp[i] ) ;
debug("\n\n") ;
}
void bit_upd(int pos, int val) { for(int i = pos ; i < MAXN ; i+= (i&-i)) bit[i] += val ; }
int qry(int pos)
{
int tot = 0 ;
for(int i = pos ; i > 0 ; i -= (i&-i))
tot += bit[i] ;
return tot ;
}
void acha_primeiro_direita()
{
maior[N-1] = INF ;
for(int i = N-2 ; i >= 0 ; i-- )
{
maior[i] = maior[i+1] ;
if( seq[i] > falta )
maior[i] = i+1 ;
}
}
int m(int l, int r) { return (l+r)>>1 ; }
void build(int pos, int l, int r)
{
if( l == r )
return (void)( mn[pos] = maior[l] ) ;
build(pos<<1 , l , m(l,r) ) ;
build((pos<<1)|1 , m(l,r)+1, r) ;
mn[pos] = min( mn[ pos<<1 ] , mn[(pos<<1)|1] ) ;
}
void upd( int pos, int l, int r, int beg , int k , int idx )
{
if( r < beg || mn[pos] > k ) return ;
if( l == r )
{
resp[l] = idx ;
mn[pos] = INF ;
return ;
}
upd( pos<<1 , l , m(l,r) , beg, k, idx ) ;
upd( (pos<<1)|1 , m(l,r)+1, r ,beg, k , idx ) ;
mn[pos] = min( mn[ pos<<1 ] , mn[(pos<<1)|1] ) ;
}
void make_upd()
{
acha_primeiro_direita() ;
build(1, 0 , N-1 ) ;
vector<pii> aux ;
int idx = 1 , ptr = 0 ;
for(auto p : queries )
upd( 1 , 0 , N-1 , p.ff , p.ss , idx++ ) ;
lp(i,0,N)
{
if(resp[i] == 0) resp[i] = INF ;
aux.pb( mk( resp[i] , i ) ) ;
}
sort(all(aux)) ;
idx = 1 ;
for(auto p : queries )
{
while( ptr < N && aux[ptr].ff <= idx )
{
resp[aux[ptr].ss]= qry( aux[ptr].ss+1 ) ;
ptr ++ ;
}
bit_upd( p.ff+1 , 1 ) ;
bit_upd( p.ss + 2 , -1 ) ;
idx ++ ;
}
while( ptr < N )
resp[aux[ptr].ss]= qry( aux[ptr].ss+1 ) , ptr ++ ;
}
} v[2];
int sou[MAXN] ;
ordered_set o_set ;
int GetBestPosition(int N, int C, int R, int *K, int *s, int *e)
{
for(int i = 0; i < 2 ; i++ ) v[i].falta = R , v[i].N = N ;
for(int i = 0 ; i < N-1 ; i++ ) v[0].seq.pb( K[i] ) ;
for(int i = N-2 ; i >= 0 ; i-- ) v[1].seq.pb( K[i] ) ;
for(int i = N-1 , j = 0 ; i >= 0 ; i-- , j++ ) sou[i] = j ;
lp(i,0,N) o_set.insert( mk(i,i) ) ;
for(int i = 0 ; i < C ; i++ )
{
int ord = s[i] ;
ordered_set::iterator it1 = o_set.find_by_order( s[i] ) ;
ordered_set::iterator it2 = o_set.find_by_order( e[i] ) ;
s[i] = it1->ff ;
e[i] = it2->ss ;
pii par = *it2 ;
while( true )
{
o_set.erase( it1 ) ;
if( it1->ff == par.ff && it2->ss == par.ss ) break ;
it1 = o_set.find_by_order( ord ) ;
}
o_set.insert( mk( s[i] , e[i] ) ) ;
}
lp(i,0,C)
{
v[0].queries.pb( mk( s[i] ,e[i] ) ) ;
v[1].queries.pb( mk( sou[ e[i] ], sou[ s[i] ] ) ) ;
}
lp(i,0,N) mn_global[i] = INF ;
lp(i,0,2)
v[i].make_upd() ;
//lp(i,0,2) v[i].print_info() ;
for(int i = 0 ; i < N ; i++ )
mn_global[i] = min( v[0].resp[i] , v[1].resp[ sou[i] ] ) ;
//lp(i,0,N) debug("%d " , mn_global[i] ) ;
//debug("\n") ;
int h = *max_element( mn_global, mn_global+N ) ;
lp(i,0,N)
if( mn_global[i] == h ) return i ;
}
Compilation message
tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:213:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
384 KB |
Output is correct |
| 3 |
Correct |
5 ms |
512 KB |
Output is correct |
| 4 |
Correct |
5 ms |
512 KB |
Output is correct |
| 5 |
Correct |
5 ms |
512 KB |
Output is correct |
| 6 |
Correct |
5 ms |
512 KB |
Output is correct |
| 7 |
Correct |
5 ms |
512 KB |
Output is correct |
| 8 |
Correct |
6 ms |
512 KB |
Output is correct |
| 9 |
Correct |
5 ms |
512 KB |
Output is correct |
| 10 |
Correct |
5 ms |
512 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
512 KB |
Output is correct |
| 2 |
Correct |
13 ms |
1152 KB |
Output is correct |
| 3 |
Correct |
9 ms |
1024 KB |
Output is correct |
| 4 |
Correct |
13 ms |
1152 KB |
Output is correct |
| 5 |
Correct |
12 ms |
1152 KB |
Output is correct |
| 6 |
Correct |
13 ms |
1280 KB |
Output is correct |
| 7 |
Correct |
14 ms |
1152 KB |
Output is correct |
| 8 |
Correct |
18 ms |
1152 KB |
Output is correct |
| 9 |
Correct |
9 ms |
1024 KB |
Output is correct |
| 10 |
Correct |
15 ms |
1152 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
104 ms |
7028 KB |
Output is correct |
| 2 |
Correct |
245 ms |
15404 KB |
Output is correct |
| 3 |
Correct |
148 ms |
13108 KB |
Output is correct |
| 4 |
Correct |
257 ms |
15344 KB |
Output is correct |
| 5 |
Correct |
215 ms |
14960 KB |
Output is correct |
| 6 |
Correct |
212 ms |
14880 KB |
Output is correct |
| 7 |
Correct |
231 ms |
15472 KB |
Output is correct |
| 8 |
Correct |
257 ms |
15344 KB |
Output is correct |
| 9 |
Correct |
126 ms |
12912 KB |
Output is correct |
| 10 |
Correct |
139 ms |
13676 KB |
Output is correct |
