oj.uz

Submission #354732

# Submission time Handle Problem Language Result Execution time Memory
354732 2021-01-22T05:11:50 Z amunduzbaev Ancient Books (IOI17_books) C++14
0 / 100
 2000 ms 364 KB 
#include "books.h"

#include "bits/stdc++.h"
using namespace std;
#ifndef EVAL
#include "grader.cpp"
#endif

#define ll long long
#define sz(x) (int)x.size();
#define pb push_back

const int N = 1e6+5;
const int mod = 1e9+7;

int n, sz;
int used[N*4][2];
int val[N*4];
int par[N];

void build(int lx, int rx, int x){
	//cout<<lx<<" "<<rx<<"\n";
	if(lx == rx){
		used[x][0] = lx, used[x][1] = lx;
		val[x] = 0;
		return;
	}
	int m = (lx + rx)>>1;
	
	build(lx, m, x*2);
	build(m+1, rx, x*2+1);
	
	if(val[x*2] <= val[x*2+1]){
		val[x] = val[x*2];
		used[x][0] = used[x*2][0];
	}
	else {
		val[x] = val[x*2+1];
		used[x][0] = used[x*2+1][0];
	}
	
	if(val[x*2] >= val[x*2+1]){
		val[x] = val[x*2+1];
		used[x][1] = used[x*2+1][1];
	}
	else {
		val[x] = val[x*2];
		used[x][1] = used[x*2][1];
	}
}

int findl(int l, int r, int lx, int rx, int x){
	if(lx > r || rx < l) return mod;
	if(lx >= l && rx <= r) return (!val[x] ? used[x][0] : mod);
	int m = (lx + rx)>>1;
	int res1 = findl(l, r, lx, m, x*2);
	int res2 = findl(l, r, m+1, rx, x*2+1);
	return min(res1, res2);
}

int findr(int l, int r, int lx, int rx, int x){
	//cout<<lx<<" "<<rx<<" "<<l<<" "<<r<<"\n";
	if(lx > r || rx < l) return 0;
	if(lx >= l && rx <= r) return (!val[x] ? used[x][1] : 0);
	int m = (lx + rx)>>1;
	int res1 = findr(l, r, lx, m, x*2);
	int res2 = findr(l, r, m+1, rx, x*2+1);
	return max(res1, res2);
}

void sett(int i, int v, int lx, int rx, int x){
	//cout<<lx<<" "<<rx<<" "<<i<<" "<<v<<"\n";
	if(lx == rx){
		val[x] = 1;
		return;
	}int m = (lx + rx)>>1;
	if(i <= m) sett(i, v, lx, m, x*2);
	else sett(i, v, m+1, rx, x*2+1);
	
	if(val[x*2] <= val[x*2+1]){
		val[x] = val[x*2];
		used[x][0] = used[x*2][0];
	}
	else {
		val[x] = val[x*2+1];
		used[x][0] = used[x*2+1][0];
	}
	
	if(val[x*2] >= val[x*2+1]){
		val[x] = val[x*2+1];
		used[x][1] = used[x*2+1][1];
	}
	else {
		val[x] = val[x*2];
		used[x][1] = used[x*2][1];
	}
}

bool check(int x){
	return val[x+sz-1];
}

ll dfs(int u, ll sum){
	//cout<<u<<" ";
	if(check(u)) return sum;
	sett(u, 1, 1, sz, 1);
	return dfs(par[u], sum+abs(par[u] - u));
}

/*

4 0
0 2 3 1

*/

ll minimum_walk(vector<int> p, int s) {
	s++, n = sz(p);
	
	sz = 1;
	while(sz < n) sz <<= 1;
	build(1, sz, 1);
	
	for(int i=0;i<n;i++){
		if(i == p[i]){
			//cout<<i+1<<"\n";
			sett(i+1, 1, 1, sz, 1);
			continue;
		}par[i+1] = p[i]+1;
	}
	
	//for(int i=1;i<2*sz;i++) cout<<val[i]<<" ";
	//cout<<"\n";
	
	//cout<<"here";
	int l = findl(s, sz, 1, sz, 1);
	//cout<<"here";
	int r = findr(1, s, 1, sz, 1);
	//cout<<"here";
	
	int cur = s;
	ll sum = 0;
	
	while(l != mod || r){
		
		//cout<<l<<" "<<r<<endl;
		
		if(l == mod){
			sum += abs(cur - r);
			ll res = dfs(r, 0);
			cur = r, sum += res;
			
		}
		else if(r == 0){
			sum += abs(cur - l);
			ll res = dfs(l, 0);
			cur = l, sum += res;
		}
		else{
			if(l - cur <= r - cur){
				sum += abs(cur - l);
				ll res = dfs(l, 0);
				cur = l, sum += res; 
			}else{
				sum += abs(cur - r);
				ll res = dfs(r, 0);
				cur = r, sum += res;				
			}
		}
		l = findl(cur, sz, 1, sz, 1);
		r = findr(1, cur, 1, sz, 1);
	}
	sum += abs(cur - s);
	return sum;
}

Subtask #1
0 / 12.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 28.0

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

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2073 ms 364 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

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