제출 #390661

#제출 시각아이디문제언어결과실행 시간메모리
390661Keshi고대 책들 (IOI17_books)C++17
50 / 100
859 ms1048580 KiB
//In the name of God #include <bits/stdc++.h> #include "books.h" using namespace std; typedef int ll; typedef pair<ll, ll> pll; const ll maxn = 1e6 + 100; const ll mod = 1e9 + 7; const ll inf = 1e9; #define pb push_back #define Mp make_pair #define F first #define S second #define Sz(x) ll((x).size()) #define all(x) (x).begin(), (x).end() #define lc (id << 1) #define rc (lc | 1) ll a[maxn], t, tt, c[maxn], rr[maxn]; ll b[maxn]; ll mn[maxn], mx[maxn], mnp[maxn], mxp[maxn]; bool vis[maxn]; vector<ll> vec, g[maxn]; vector<pll> v2; ll seg[maxn << 2]; void bld(ll id, ll s, ll e){ if(e - s == 1){ seg[id] = b[s]; return; } ll mid = (s + e) >> 1; bld(lc, s, mid); bld(rc, mid, e); seg[id] = max(seg[lc], seg[rc]); } ll get(ll id, ll s, ll e, ll l, ll r){ if(r <= s || e <= l) return 0; if(l <= s && e <= r) return seg[id]; ll mid = (s + e) >> 1; return max(get(lc, s, mid, l, r), get(rc, mid, e, l, r)); } ll sz[maxn], cnt[maxn]; bool val[maxn]; ll solve(ll v, ll s){ ll x = -1; ll ans = 0; for(ll i = 0; i < Sz(g[v]); i++){ ll u = g[v][i]; if(mnp[u] <= s && s <= mxp[u]) x = i; if(mnp[v] == 0){ // cout << "$ " << u << " " << mnp[u] << " " << mxp[u] << "\n"; } ans += solve(u, s); sz[v] += sz[u]; } val[v] = (sz[v] == mxp[v] - mnp[v] + 1); if(x == -1 || mnp[v] > s || s > mxp[v]) return 0; // if(!val[g[v][x]]) cout << v << " [" << mnp[v] << ", " << mxp[v] << "] -----> " << ans << "\n"; if(!val[g[v][x]]) return ans; ll j = 0; ll y = inf; ll o = mnp[g[v][x]]; for(ll i = x; i--;){ ll u = g[v][i]; if(!val[u]) continue; j++; if(mxp[u] + 1 != o){ y = min(y, j); break; } o = mnp[u]; } y = min(y, j + 1); j = 0; o = mxp[g[v][x]]; for(ll i = x + 1; i < Sz(g[v]); i++){ ll u = g[v][i]; if(!val[u]) continue; j++; if(mnp[u] != o + 1){ y = min(y, j); break; } o = mxp[u]; } y = min(y, j + 1); // cout << "# " << v << " [" << mnp[v] << ", " << mxp[v] << "] -----> "; if(mnp[v] == -1){ // cout << ans + Sz(g[v]) - 1 << "\n"; return ans + Sz(g[v]) - 1; } // cout << ans + y << "\n"; return ans + y; } long long minimum_walk(vector<int> p, int s){ ll n = Sz(p); ll l = 0; while(l < n && p[l] == l) l++; ll r = n; while(r && p[r - 1] == r - 1) r--; l = min(l, s); r = max(r, s + 1); mn[0] = -1; mx[0] = n; t++; long long ans = 0; for(ll i = l; i < r; i++){ ans += abs(p[i] - i); if(!vis[i]){ ll v = i; mn[t] = inf; mx[t] = -inf; do{ vis[v] = 1; mx[t] = max(mx[t], v); mn[t] = min(mn[t], v); cnt[t]++; v = p[v]; }while(v != i); rr[mx[t]] = t; b[mn[t]] = mx[t]; t++; } } bld(1, 0, n); for(ll i = 0; i < t; i++){ v2.pb(Mp(mn[i], i)); } for(pll i : v2){ if(!vis[i.S]) continue; mnp[tt] = i.F; mxp[tt] = mx[i.S]; sz[tt] = cnt[i.S]; vis[i.S] = 0; while(true){ ll x = get(1, 0, n, mnp[tt], mxp[tt] + 1); if(!vis[rr[x]] || x <= mxp[tt]) break; mxp[tt] = x; sz[tt] += cnt[rr[x]]; vis[rr[x]] = 0; } tt++; } vec.clear(); v2.clear(); ll root = -1; for(ll i = 0; i < tt; i++){ if(mnp[i] == -1) root = i; v2.pb(Mp(mnp[i], i)); } sort(all(v2)); for(pll i : v2){ if(vec.empty()){ vec.pb(i.S); continue; } while(mxp[vec.back()] < i.F) vec.pop_back(); g[vec.back()].pb(i.S); vec.pb(i.S); } ll xx = solve(root, s); ans += 2 * xx; return ans; }
#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...