| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 52181 |
2018-06-24T14:17:41 Z |
김세빈(#1331) |
Ancient Books (IOI17_books) |
C++11 |
|
22 ms |
24292 KB |
#include "books.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
vector <int> V[1010101], X;
vector <pii> P;
int T[3030303];
int L[1010101], R[1010101];
int chk[1010101], K[1010101];
int n,cnt,sz;
ll ans;
int abs(int x)
{
return x > 0? x : -x;
}
int find_min(int l,int r)
{
l += sz, r += sz;
int ret = 0;
for(;l<r;){
if((l & 1) && L[ret] > L[T[l]]) ret = T[l];
if((~r & 1) && L[ret] > L[T[r]]) ret = T[r];
l = ++l >> 1;
r = --r >> 1;
}
if(l == r && L[ret] > L[T[l]]) ret = T[l];
return ret;
}
void insert(int p,int v)
{
p += sz;
T[p] = v;
for(p>>=1;p;p>>=1){
if(L[T[p<<1]] < L[T[p<<1|1]]) T[p] = T[p<<1];
else T[p] = T[p<<1|1];
}
}
bool comp(int a,int b)
{
return L[a] < L[b];
}
ll minimum_walk(vector <int> p, int s)
{
int i,t,m,k,f;
n = p.size();
for(sz=1;sz<n;sz<<=1);
for(i=0;i<n;i++) if(!chk[i] && i != p[i]){
cnt ++;
chk[i] = cnt;
V[cnt].push_back(i);
L[cnt] = R[cnt] = i;
K[cnt] = cnt;
ans += abs(i - p[i]);
for(int j=p[i];j!=i;j=p[j]){
chk[j] = cnt;
V[cnt].push_back(j);
R[cnt] = max(R[cnt], j);
ans += abs(j - p[j]);
}
}
L[0] = n+1;
sort(K+1, K+cnt+1, comp);
for(i=1;i<=cnt;i++){
t = K[i];
f = find_min(L[t], R[t]);
if(f){
for(int j: V[t]){
V[f].push_back(j);
R[f] = max(R[f], j);
chk[j] = f;
insert(j, f);
}
V[t].clear();
}
else{
for(int j: V[t]){
insert(j, t);
}
}
}
for(i=1;i<=cnt;i++){
t = K[i];
if(V[t].empty()) continue;
f = find_min(L[t], R[t]);
if(L[f] < L[t]){
for(int j: V[t]){
V[f].push_back(j);
R[f] = max(R[f], j);
chk[j] = f;
insert(j, f);
}
V[t].clear();
}
}
for(i=1;i<=cnt;i++){
t = K[i];
if(!V[t].empty()){
P.push_back(pii(L[t], R[t]));
if(L[t] <= s && s <= R[t]){
sort(V[t].begin(), V[t].end());
X.push_back(t);
}
}
}
sort(P.begin(), P.end());
t = P[0].first;
for(i=k=0;i<P.size();i++){
if(P[i].second < t) continue;
ans += 2 * (P[i].first - t);
t = max(t, P[i].second);
}
if(!X.empty()){
for(i=0;i<X.size()-1;i++){
k += min(abs(*lower_bound(V[X[i]].begin(), V[X[i]].end(), L[X[i+1]]) - L[X[i+1]]), abs(*upper_bound(V[X[i]].begin(), V[X[i]].end(), R[X[i+1]]) - R[X[i+1]]));
}
k += min(abs(*lower_bound(V[X[i]].begin(), V[X[i]].end(), s) - s), abs(*upper_bound(V[X[i]].begin(), V[X[i]].end(), s) - s));
}
return ans + k * 2;
}
Compilation message
books.cpp: In function 'int find_min(int, int)':
books.cpp:31:5: warning: operation on 'l' may be undefined [-Wsequence-point]
l = ++l >> 1;
~~^~~~~~~~~~
books.cpp:32:5: warning: operation on 'r' may be undefined [-Wsequence-point]
r = --r >> 1;
~~^~~~~~~~~~
books.cpp: In function 'll minimum_walk(std::vector<int>, int)':
books.cpp:136:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=k=0;i<P.size();i++){
~^~~~~~~~~
books.cpp:143:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<X.size()-1;i++){
~^~~~~~~~~~~
books.cpp:57:10: warning: unused variable 'm' [-Wunused-variable]
int i,t,m,k,f;
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
24056 KB |
3rd lines differ - on the 1st token, expected: '6', found: '4' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
24056 KB |
3rd lines differ - on the 1st token, expected: '6', found: '4' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
24056 KB |
3rd lines differ - on the 1st token, expected: '6', found: '4' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
24292 KB |
3rd lines differ - on the 1st token, expected: '3304', found: '3884' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
24056 KB |
3rd lines differ - on the 1st token, expected: '6', found: '4' |
| 2 |
Halted |
0 ms |
0 KB |
- |
