Submission #1201291

#TimeUsernameProblemLanguageResultExecution timeMemory
1201291Zbyszek99Ancient Books (IOI17_books)C++20
100 / 100
788 ms121552 KiB
#include "books.h" #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define ll long long #define ld long double #define ull unsigned long long #define ff first #define ss second #define pii pair<int,int> #define pll pair<long long, long long> #define vi vector<int> #define vl vector<long long> #define pb push_back #define rep(i, b) for(int i = 0; i < (b); ++i) #define rep2(i,a,b) for(int i = a; i <= (b); ++i) #define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c) #define count_bits(x) __builtin_popcountll((x)) #define all(x) (x).begin(),(x).end() #define siz(x) (int)(x).size() #define forall(it,x) for(auto& it:(x)) using namespace __gnu_pbds; using namespace std; typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set; mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());} ll los(ll a, ll b) {return a + (mt() % (b-a+1));} const int INF = 1e9+50; const ll INF_L = 1e18+40; const ll MOD = 1e9+7; bool odw[1'000'001]; int seg_ind[1'000'001]; vector<pii> segs; int used_poz[1'000'001]; int rep_[1'000'001]; int min_c[1'000'001]; int max_c[1'000'001]; bool top_seg[1'000'001]; int fint(int v) { if(rep_[v] == v) return v; rep_[v] = fint(rep_[v]); return rep_[v]; } void onion(int a, int b) { a = fint(a); b = fint(b); max_c[b] = max(max_c[a],max_c[b]); min_c[b] = min(min_c[a],min_c[b]); rep_[a] = b; } ll minimum_walk(vi p, int s) { int n = siz(p); ll ans = -2; rep(i,n) { if(odw[i] == 0) { int cur = i; vi ls; while(odw[cur] == 0) { ls.pb(cur); odw[cur] = 1; ans += abs(cur-p[cur]); cur = p[cur]; } int min_ = 1e9; int max_ = -1e9; forall(it,ls) { min_ = min(min_,it); max_ = max(max_,it); } segs.pb({min_,max_}); forall(it,ls) { seg_ind[it] = siz(segs)-1; } } } if(ans == -2) return 0; rep(i,siz(segs)) { rep_[i] = i; min_c[i] = segs[i].ff; max_c[i] = segs[i].ss; } vector<pii> sort_segs; rep(i,siz(segs)) { sort_segs.pb({segs[i].ss,i}); } sort(all(sort_segs)); set<pii> segs_set; forall(it,sort_segs) { int l = segs[it.ss].ff; int r = segs[it.ss].ss; while(true) { auto it2 = segs_set.lower_bound({l,-1e9}); if(it2 == segs_set.end()) break; onion(it.ss,(*it2).ss); segs_set.erase(it2); } segs_set.insert({max_c[fint(it.ss)],it.ss}); } vector<pair<int,pii>> se; rep(i,siz(segs)) { if(fint(i) == i) { se.pb({max_c[fint(i)] - min_c[fint(i)],{min_c[fint(i)],i}}); } } sort(all(se)); reverse(all(se)); forall(it,se) { if(used_poz[it.ss.ff] == 0) { top_seg[it.ss.ff] = 1; ans+=2; rep2(i,it.ss.ff,it.ss.ff+it.ff) { used_poz[i] = 1; } } } int pref = 0; int suf = 0; rep(i,n) { if(p[i] == i) pref++; else break; } for(int i = n-1; i >= 0; i--) { if(p[i] == i) suf++; else break; } if(s < pref) { return ans - suf*2 - pref*2 + (pref-s)*2; } if(s >= n-suf) { return ans - suf*2 - pref*2 + (n-suf-s+1)*2; } ans -= suf*2 + pref*2; int min_dist = 1e9; priority_queue<pii,vector<pii>,greater<pii>> pq; pq.push({0,s}); rep(i,n) odw[i] = 0; set<int> un_dist; rep(i,n) un_dist.insert(i); while(!pq.empty()) { pii t = pq.top(); pq.pop(); if(odw[t.ss]) continue; odw[t.ss] = 1; if(un_dist.find(t.ss) != un_dist.end()) { un_dist.erase(un_dist.find(t.ss)); } if(top_seg[t.ss]) min_dist = min(min_dist,t.ff); int l = segs[seg_ind[t.ss]].ff; int r = segs[seg_ind[t.ss]].ss; while(true) { auto it = un_dist.lower_bound(l); if(it == un_dist.end()) break; if((*it) > r) break; pq.push({t.ff,(*it)}); un_dist.erase(it); } if(t.ss != 0) pq.push({t.ff+1,t.ss-1}); if(t.ss != n-1) pq.push({t.ff+1,t.ss+1}); } return ans + min_dist*2; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...