oj.uz

답안 #295721

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
295721 2020-09-09T20:40:01 Z shayan_p 고대 책들 (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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2068 ms 16000 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 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 -