oj.uz

Submission #295721

# Submission time Handle Problem Language Result Execution time Memory
295721 2020-09-09T20:40:01 Z shayan_p Ancient Books (IOI17_books) C++17
12 / 100
 2000 ms 16128 KB 
// Oh damn! Suddenly you're free to fly...
 
#include<bits/stdc++.h>
#include "books.h"
 
#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)
 
using namespace std;
 
typedef long long ll;
typedef pair<int,int> pii;
 
const int maxn = 1e6 + 10, mod = 1e9 + 7, inf = 1e9 + 10;
 
int pr[maxn], L[maxn], R[maxn];
int pr2[maxn];

int fnd(int u){
    return pr[u] < 0 ? u : pr[u] = fnd(pr[u]);
}
void mrg(int a, int b){
    if( (a = fnd(a)) == (b = fnd(b)) )
	return;
    if(pr[a] > pr[b])
	swap(a, b);
    L[a] = min(L[a], L[b]);
    R[a] = max(R[a], R[b]);
    pr[a]+= pr[b];
    pr[b] = a;	    
}
 
ll minimum_walk(vector<int> p, int s){
    memset(pr, -1, sizeof pr);
    memset(pr2, -1, sizeof pr2);

    iota(L, L + maxn, 0);
    iota(R, R + maxn, 0);
    
    int n = sz(p);
    ll ans = 0;
 
    for(int i = 0; i < n; i++){
	int l = i, r = p[i];
	if(l > r)
	    swap(l, r);
	ans+= r-l;
	mrg(l, r);
    }
    vector<int> vec;
    for(int i = 0; i < n; i++){
	if(fnd(i) == i)
	    vec.PB(i);
    }
    sort(vec.begin(), vec.end(), [&](int i, int j){ return L[fnd(i)] > L[fnd(j)]; });
    int LST = n-1;
    for(int id : vec){
	int tmp = R[fnd(id)];
	while(LST >= L[fnd(id)]){
	    if(LST != id)
		pr2[LST] = id;
	    LST--;
	}
	while(tmp != -1){
	    mrg(id, tmp);
	    int nx = pr2[tmp];
	    pr2[tmp] = id;
	    tmp = nx;
	}
    }
    
    int l = s, r = s;
    while(true){
	while(true){
	    bool is = 0;
	    while(r < R[fnd(s)])
		mrg(s, ++r), is = 1;
	    while(l > L[fnd(s)])
		mrg(s, --l), is = 1;
	    if(!is)
		break;
	}
	int d1 = 0, d2 = 0;
	while(r < n && L[fnd(s)] <= L[fnd(r)]){
	    d2+= R[fnd(s)] < r;
	    mrg(s, r);
	    r++;
	}
	while(l >= 0 && R[fnd(l)] <= R[fnd(s)]){
	    d1+= L[fnd(s)] > l;
	    mrg(s, l);
	    l--;
	}
	if(l == -1 || r == n){
	    assert(l == -1 && r == n);
	    ans+= 2 * (d1 + d2);
	    break;
	}
	else{
	    ans+= 2 * min(d1 + 1, d2 + 1);
	    //	    assert(fnd(l) == fnd(r));
	    mrg(s, l);
	    mrg(s, r);
	}	    
    }
    for(int i = 0; i < s && p[i] == i; i++){
	ans-= 2;
    }
    for(int i = n-1; i > s && p[i] == i; i--){
	ans-= 2;
    }
    return ans;
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 16000 KB Output is correct
2 Correct 10 ms 16000 KB Output is correct
3 Correct 10 ms 16000 KB Output is correct
4 Correct 11 ms 16000 KB Output is correct
5 Correct 11 ms 16000 KB Output is correct
6 Correct 10 ms 16000 KB Output is correct
7 Correct 10 ms 16000 KB Output is correct
8 Correct 10 ms 16128 KB Output is correct
9 Correct 10 ms 16000 KB Output is correct
10 Correct 10 ms 16000 KB Output is correct
11 Correct 10 ms 16000 KB Output is correct
12 Correct 11 ms 15956 KB Output is correct
13 Correct 10 ms 16000 KB Output is correct
14 Correct 10 ms 16000 KB Output is correct
15 Correct 10 ms 16000 KB Output is correct
16 Correct 10 ms 16000 KB Output is correct
17 Correct 11 ms 16000 KB Output is correct
18 Correct 11 ms 16000 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 16000 KB Output is correct
2 Correct 10 ms 16000 KB Output is correct
3 Correct 10 ms 16000 KB Output is correct
4 Correct 11 ms 16000 KB Output is correct
5 Correct 11 ms 16000 KB Output is correct
6 Correct 10 ms 16000 KB Output is correct
7 Correct 10 ms 16000 KB Output is correct
8 Correct 10 ms 16128 KB Output is correct
9 Correct 10 ms 16000 KB Output is correct
10 Correct 10 ms 16000 KB Output is correct
11 Correct 10 ms 16000 KB Output is correct
12 Correct 11 ms 15956 KB Output is correct
13 Correct 10 ms 16000 KB Output is correct
14 Correct 10 ms 16000 KB Output is correct
15 Correct 10 ms 16000 KB Output is correct
16 Correct 10 ms 16000 KB Output is correct
17 Correct 11 ms 16000 KB Output is correct
18 Correct 11 ms 16000 KB Output is correct
19 Execution timed out 2091 ms 16000 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 16000 KB Output is correct
2 Correct 10 ms 16000 KB Output is correct
3 Correct 10 ms 16000 KB Output is correct
4 Correct 11 ms 16000 KB Output is correct
5 Correct 11 ms 16000 KB Output is correct
6 Correct 10 ms 16000 KB Output is correct
7 Correct 10 ms 16000 KB Output is correct
8 Correct 10 ms 16128 KB Output is correct
9 Correct 10 ms 16000 KB Output is correct
10 Correct 10 ms 16000 KB Output is correct
11 Correct 10 ms 16000 KB Output is correct
12 Correct 11 ms 15956 KB Output is correct
13 Correct 10 ms 16000 KB Output is correct
14 Correct 10 ms 16000 KB Output is correct
15 Correct 10 ms 16000 KB Output is correct
16 Correct 10 ms 16000 KB Output is correct
17 Correct 11 ms 16000 KB Output is correct
18 Correct 11 ms 16000 KB Output is correct
19 Execution timed out 2091 ms 16000 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 16000 KB Output is correct
2 Correct 10 ms 16000 KB Output is correct
3 Correct 10 ms 16000 KB Output is correct
4 Correct 11 ms 16000 KB Output is correct
5 Correct 11 ms 16000 KB Output is correct
6 Correct 10 ms 16000 KB Output is correct
7 Correct 10 ms 16000 KB Output is correct
8 Correct 10 ms 16128 KB Output is correct
9 Correct 10 ms 16000 KB Output is correct
10 Correct 10 ms 16000 KB Output is correct
11 Correct 10 ms 16000 KB Output is correct
12 Correct 11 ms 15956 KB Output is correct
13 Correct 10 ms 16000 KB Output is correct
14 Correct 10 ms 16000 KB Output is correct
15 Correct 10 ms 16000 KB Output is correct
16 Correct 10 ms 16000 KB Output is correct
17 Correct 11 ms 16000 KB Output is correct
18 Correct 11 ms 16000 KB Output is correct
19 Execution timed out 2091 ms 16000 KB Time limit exceeded
20 Halted 0 ms 0 KB -