Submission #387796

#	Time	Username	Problem	Language	Result	Execution time	Memory
387796		RohamIzadidoost	Fun Tour (APIO20_fun)	C++14	0 / 100	12 ms	19020 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 = 1000*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; 
vec<int> ans ;
set<pii> seg[4 * maxn] ; 
void build(int x = 0 , int lx = 0 , int rx = n , int h = 0 ){
	if(rx - lx == 1){
		seg[x].insert({-1 * h , x}) ;
		H[x] = h ; 
		val[x] = lx  ;
		return ; 
	}
	int mid = lx + rx >> 1 ; 
	build(x * 2 + 1, lx , mid , h + 1) ; 
	build(x * 2 + 2 , mid , rx , h + 1) ;
	seg[x] = seg[x * 2 + 1]  ; for(auto u : seg[x * 2 + 2]) seg[x].insert(u) ; 
//	sort(all(seg[x])) ; 
}
void del(int x){
//	cout<<"DELTING " << x << " : " ; 
	seg[x].erase({-H[X] , X}) ;
	for(auto u : seg[x]) cout<<u.X <<","<<u.Y <<"  " ; cout<<endl ; 
	if(x == 0) return ;
	x = (x - 1) / 2 ; 
	del(x) ;
}
pii dfs(int v){
	int x  , V = v ;; 
	p = {0 , 0} ;
	while(v != 0){
		x = v ; 
		v = (v - 1) / 2 ;
		if(x & 1) x = v << 1 ; 
		else x = v << 1 | 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> createFunTour(int N , int Q){
	n = N ; 
	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 ; 
	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:36:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   36 |  int mid = lx + rx >> 1 ;
      |            ~~~^~~~
fun.cpp: In function 'void del(int)':
fun.cpp:45:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   45 |  for(auto u : seg[x]) cout<<u.X <<","<<u.Y <<"  " ; cout<<endl ;
      |  ^~~
fun.cpp:45:53: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   45 |  for(auto u : seg[x]) cout<<u.X <<","<<u.Y <<"  " ; cout<<endl ;
      |                                                     ^~~~

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