#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
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 ;
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Failed |
12 ms |
19020 KB |
DO NOT PRINT ANYTHING TO STDOUT |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Failed |
12 ms |
19020 KB |
DO NOT PRINT ANYTHING TO STDOUT |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Failed |
11 ms |
19020 KB |
DO NOT PRINT ANYTHING TO STDOUT |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Failed |
11 ms |
19020 KB |
DO NOT PRINT ANYTHING TO STDOUT |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Failed |
12 ms |
19020 KB |
DO NOT PRINT ANYTHING TO STDOUT |
