oj.uz

Submission #52176

# Submission time Handle Problem Language Result Execution time Memory
52176 2018-06-24T13:56:20 Z 김세빈(#1331) Ancient Books (IOI17_books) C++11
0 / 100
 23 ms 24436 KB 
#include "books.h"

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

vector <int> V[1010101];
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]){
		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++){
		if(!V[i].empty()){
			P.push_back(pii(L[i], R[i]));
		}
	}
	
	sort(P.begin(), P.end());
	
	m = n+1;
	
	for(i=t=0;i<P.size();i++){
		if(P[i].second < t) continue;
		ans += 2 * (P[i].first - t);
		t = max(t, P[i].second);
		
		if(P[i].first <= s && s <= P[i].second) m = min(m, P[i].first);
	}
	
	k = n+1;
	
	for(i=0;i<n;i++){
		if(L[chk[i]] == m) k = min(k, abs(s-i));
	}
	
	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:131:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=t=0;i<P.size();i++){
            ~^~~~~~~~~

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 24056 KB Output is correct
2 Correct 22 ms 24056 KB Output is correct
3 Correct 22 ms 24208 KB Output is correct
4 Correct 22 ms 24324 KB Output is correct
5 Incorrect 22 ms 24324 KB 3rd lines differ - on the 1st token, expected: '4', found: '6'
6 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 24056 KB Output is correct
2 Correct 22 ms 24056 KB Output is correct
3 Correct 22 ms 24208 KB Output is correct
4 Correct 22 ms 24324 KB Output is correct
5 Incorrect 22 ms 24324 KB 3rd lines differ - on the 1st token, expected: '4', found: '6'
6 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 24056 KB Output is correct
2 Correct 22 ms 24056 KB Output is correct
3 Correct 22 ms 24208 KB Output is correct
4 Correct 22 ms 24324 KB Output is correct
5 Incorrect 22 ms 24324 KB 3rd lines differ - on the 1st token, expected: '4', found: '6'
6 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 24436 KB 3rd lines differ - on the 1st token, expected: '3304', found: '3590'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 24056 KB Output is correct
2 Correct 22 ms 24056 KB Output is correct
3 Correct 22 ms 24208 KB Output is correct
4 Correct 22 ms 24324 KB Output is correct
5 Incorrect 22 ms 24324 KB 3rd lines differ - on the 1st token, expected: '4', found: '6'
6 Halted 0 ms 0 KB -