제출 #390729

#제출 시각아이디문제언어결과실행 시간메모리
390729alireza_kaviani고대 책들 (IOI17_books)C++11
100 / 100
489 ms92228 KiB
#include <bits/stdc++.h> #include "books.h" using namespace std; typedef long long ll; typedef pair<int, int> pii; #define sep ' ' #define X first #define Y second #define all(x) (x).begin() , (x).end() #define SZ(x) int(x.size()) const int MAXN = 1e6 + 10; int n , mark[MAXN] , mx[MAXN] , mn[MAXN] , par[MAXN] , sz[MAXN]; ll ans , ps[MAXN]; vector<int> comp[MAXN]; int Find(int v){ return (par[v] == -1 ? v : par[v] = Find(par[v])); } void Union(int v , int u){ v = Find(v); u = Find(u); if(v == u) return; if(sz[v] < sz[u]) swap(v , u); par[u] = v; sz[v] += sz[u]; mx[v] = max(mx[v] , mx[u]); mn[v] = min(mn[v] , mn[u]); } int count(int l , int r , int x){ int ans = 0; for(int i = l ; i < r ; i++){ ans += (ps[i] == x); } return ans; } ll minimum_walk(vector<int> p, int s) { fill(mx , mx + MAXN , -1); fill(mn , mn + MAXN , MAXN); fill(par , par + MAXN , -1); fill(sz , sz + MAXN , 1); n = p.size(); vector<pii> vec; for(int i = 0 ; i < n ; i++){ ans += abs(i - p[i]); if(mark[i]) continue; int x = i , flag = 0; vector<int> v; while(!mark[x]){ mark[x] = 1; mn[x] = mx[x] = x; v.push_back(x); x = p[x]; } sort(all(v)); for(int j = 0 ; j + 1 < SZ(v) ; j++){ Union(v[j] , v[j + 1]); vec.push_back({v[j] , v[j + 1]}); } } vector<int> stk; sort(all(vec)); for(int i = 0 ; i < SZ(vec) ; i++){ while(SZ(stk) > 0 && vec[i].Y > vec[stk.back()].Y){ if(vec[i].X < vec[stk.back()].Y) Union(vec[i].X , vec[stk.back()].X); stk.pop_back(); } stk.push_back(i); } vector<int> v; for(int i = 0 ; i < n ; i++){ comp[Find(i)].push_back(i); if(Find(i) == i){ ps[mn[i]]++; ps[mx[i]]--; if(mn[i] <= s && s <= mx[i]){ v.push_back(i); } } } partial_sum(ps , ps + MAXN , ps); int l = 0 , r = n; while(l < s && ps[l] == 0) l++; while(s <= r && ps[r] == 0) r--; ans += 2 * count(l , r + 1 , 0); for(int i = 0 ; i + 1 < SZ(v) ; i++){ int l2 = mn[v[i + 1]] , r2 = mx[v[i + 1]]; int l1 = (*prev(lower_bound(all(comp[v[i]]) , l2))); int r1 = (*lower_bound(all(comp[v[i]]) , r2)); // cout << l1 << sep << l2 << sep << r1 << sep << r2 << endl; ans += min(count(l1 , l2 , i + 1) , count(r2 , r1 , i + 1)) * 2; } return ans; }

컴파일 시 표준 에러 (stderr) 메시지

books.cpp: In function 'll minimum_walk(std::vector<int>, int)':
books.cpp:52:15: warning: unused variable 'flag' [-Wunused-variable]
   52 |   int x = i , flag = 0;
      |               ^~~~
#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...