Submission #387832

#	Time	Username	Problem	Language	Result	Execution time	Memory
387832		RohamIzadidoost	Fun Tour (APIO20_fun)	C++14	21 / 100	638 ms	126380 KiB

fun

#pragma GCC optimize("Ofast,unroll-loops,fast-math")
//#include "fun.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll ;
#define pll pair<ll , ll >
#define all(x) (x).begin(),(x).end()
#define SZ(x) (ll)(x).size()
#define X   first
#define Y   second
#define mp  make_pair
#define pii pair<int , int>
#define vec vector
#define file_io freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
#define migmig ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pb push_back
// BIG p : 1000000000000037 , 100000000003
ll poww(ll a, ll b, ll md) {
    return (!b ? 1 : (b & 1 ? a * poww(a * a % md, b / 2, md) % md : poww(a * a % md, b / 2, md) % md));
}
const int maxn = 2000*100+5 ;
const ll inf = 9223372036854775807 ;
const ll mod = 1e9 + 7 ;
const int lg = 20 ;
pii p ;
int cur , mark[maxn] , n , H[4 * maxn] , val[4 * maxn] , X , pt; 
set<pii> seg[4 * maxn] ; 
void build(int x = 0 , int lx = 0 , int rx = pt , int h = 1 ){
	H[x] = h ; 
	seg[x].insert({-h , x}) ;
	//cout<<x <<" : " << H[x] <<" boom " << endl ; 
	int mid = lx + rx >> 1 ; 
	if(2 * x + 1 < n){
		build( 2 * x + 1 , lx , mid , h + 1) ;
		for(auto u : seg[x * 2 + 1]) seg[x].insert(u) ; 
	}
	if(2 * x + 2 < n){
		build(2 * x + 2 , mid , rx , h + 1) ;
		for(auto u : seg[x * 2 + 2]) seg[x].insert(u) ;
	}
//	cout<<x <<" : " ; for(auto u : seg[x]) cout<<u.X <<"," << u.Y <<"  " ; cout<<endl ; 
//	sort(all(seg[x])) ; 
}
void del(int x){
	seg[x].erase({-H[X] , X}) ;
	if(x == 0) return ;
	x = (x - 1) / 2 ; 
	del(x) ;
}
pii dfs(int v){
	int x  , V = v ;; 
	p = {0 , 0} ;
	if(v == 0 ){
		p = {seg[0].begin() -> X - 1 , seg[0].begin() -> Y} ;
		return p ; 
	}
	while(v != 0){
	//	cout<<"DFS : " << v <<" , " << V << endl ;  
		x = v ; 
		v = (v - 1) / 2 ;
		if(x & 1) x = 2 * v + 2 ; 
		else x = 2 * v + 1 ; 
		if(SZ(seg[x])) p = max(p ,{ H[V] + (-1 * (seg[x].begin() -> X) ) - 2 * H[v] , seg[x].begin() -> Y } ) ;  
	}
	return p ; 
}
	vec<int> ans ;
vec<int> createFunTour(int N , int Q){
	n = N ; 
	pt = 1 ; 
	while(pt < n ) pt *= 2 ; 
	build() ; 
	ans.pb(seg[1].begin() -> Y) ;
	while(SZ(ans) < n){
		//cout<<SZ(ans) <<" : " << ans.back() << " -> " << val[ans.back()] << endl   ; 
		X = ans.back() ; 
		del(ans.back()) ; 
		ans.pb(dfs(ans.back()).Y) ; 
	}
//	for(int i = 0 ;  i < n ; i ++ ) ans[i] = val[ans[i]] ;
	return ans ; 
}

/*int main()
{
	migmig ;
	cin>>n ; 
	pt = 1 ; 
	while(pt < n ) pt *= 2 ; 
	build() ; 
	ans.pb(seg[1].begin() -> Y) ;
	while(SZ(ans) < n){
	//	cout<<SZ(ans) <<" : " << ans.back() << " -> " << val[ans.back()] << endl   ; 
		X = ans.back() ; 
		del(ans.back()) ; 
		ans.pb(dfs(ans.back()).Y) ; 
	}
//	for(int i = 0 ;  i < n ; i ++ ) ans[i] = val[ans[i]] ;
	for(auto u : ans) cout<<u <<" " ; 
}*/

Compilation message (stderr)

fun.cpp: In function 'void build(int, int, int, int)':
fun.cpp:32:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   32 |  int mid = lx + rx >> 1 ;
      |            ~~~^~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 16
• Subtask 3: 21 / 21
• Subtask 4: 0 / 19
• Subtask 5: 0 / 34