oj.uz

Submission #293772

# Submission time Handle Problem Language Result Execution time Memory
293772 2020-09-08T11:54:03 Z shayan_p Ancient Books (IOI17_books) C++17
12 / 100
 26 ms 24320 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 cnt[maxn];

int pr[maxn], L[maxn], R[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;	    
}

int par[maxn];

ll minimum_walk(vector<int> p, int s){
    memset(pr, -1, sizeof pr);
    iota(L, L + maxn, 0);
    iota(R, R + maxn, 0);
    
    int n = sz(p);
    ll ans = 0;
    vector<pii> vec;
    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);
	vec.PB({l, r});
    }
    for(pii p : vec){
	for(pii p2 : vec){
	    if(p.F > p2.F)
		swap(p, p2);
	    if(p.S < p2.S && p2.F < p.S)
		mrg(p.F, p2.F);
	}
    }

    vector<int> seg;
    for(int i = 0; i < n; i++){
	if(i == fnd(i)){
	    seg.PB(i);
	}
    }

    sort(seg.begin(), seg.end(), [&](int i, int j){ return L[i] > L[j]; });

    vector<int> st;
    for(int id : seg){
	while(sz(st) && R[st.back()] <= R[id]){
	    par[st.back()] = id;
	    st.pop_back();
	}
	st.PB(id);
    }

    for(int id : st){
	par[id] = -1;
    }

    int ptl = 0, ptr = sz(st) - 1;
    while(ptl < sz(st) && L[st[ptl]] == R[st[ptl]] && L[st[ptl]] != s)
	ptl++;
    while(ptr >= 0 && L[st[ptr]] == R[st[ptr]] && L[st[ptr]] != s)
	ptr--;
    for(int i = ptl; i < ptr; i++){
	ans+= 2 * (L[st[i]] - R[st[i+1]]);
    }

    int tmp = fnd(s);
    assert(par[tmp] == -1);
    while(par[tmp] != -1){
	int PTL = L[tmp], PTR = R[tmp];
	int _PTL = L[par[tmp]], _PTR = R[par[tmp]];
	int d1 = 0, d2 = 0;
	while(PTL > _PTL){
	    PTL = L[fnd(PTL)];
	    d1++;
	    PTL--;
	}
	while(PTR < _PTR){
	    PTR = R[fnd(PTR)];
	    d2++;
	    PTR++;
	}
	ans+= 2 * min(d1, d2);

	tmp = par[tmp];
    }
    return ans;
}

Subtask #1
12.0 / 12.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12032 KB Output is correct
2 Correct 9 ms 12032 KB Output is correct
3 Correct 10 ms 12032 KB Output is correct
4 Correct 9 ms 12032 KB Output is correct
5 Correct 8 ms 12032 KB Output is correct
6 Correct 10 ms 12032 KB Output is correct
7 Correct 8 ms 12032 KB Output is correct
8 Correct 8 ms 12032 KB Output is correct
9 Correct 8 ms 12032 KB Output is correct
10 Correct 8 ms 12032 KB Output is correct
11 Correct 8 ms 12032 KB Output is correct
12 Correct 9 ms 12032 KB Output is correct
13 Correct 8 ms 12032 KB Output is correct
14 Correct 9 ms 12032 KB Output is correct
15 Correct 8 ms 12032 KB Output is correct
16 Correct 8 ms 12032 KB Output is correct
17 Correct 8 ms 12032 KB Output is correct
18 Correct 8 ms 12032 KB Output is correct
19 Correct 14 ms 12160 KB Output is correct
20 Correct 17 ms 12032 KB Output is correct
21 Correct 9 ms 12160 KB Output is correct
22 Incorrect 9 ms 12160 KB 3rd lines differ - on the 1st token, expected: '2082', found: '2044'
23 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12032 KB Output is correct
2 Correct 9 ms 12032 KB Output is correct
3 Correct 10 ms 12032 KB Output is correct
4 Correct 9 ms 12032 KB Output is correct
5 Correct 8 ms 12032 KB Output is correct
6 Correct 10 ms 12032 KB Output is correct
7 Correct 8 ms 12032 KB Output is correct
8 Correct 8 ms 12032 KB Output is correct
9 Correct 8 ms 12032 KB Output is correct
10 Correct 8 ms 12032 KB Output is correct
11 Correct 8 ms 12032 KB Output is correct
12 Correct 9 ms 12032 KB Output is correct
13 Correct 8 ms 12032 KB Output is correct
14 Correct 9 ms 12032 KB Output is correct
15 Correct 8 ms 12032 KB Output is correct
16 Correct 8 ms 12032 KB Output is correct
17 Correct 8 ms 12032 KB Output is correct
18 Correct 8 ms 12032 KB Output is correct
19 Correct 14 ms 12160 KB Output is correct
20 Correct 17 ms 12032 KB Output is correct
21 Correct 9 ms 12160 KB Output is correct
22 Incorrect 9 ms 12160 KB 3rd lines differ - on the 1st token, expected: '2082', found: '2044'
23 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 26 ms 24320 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12032 KB Output is correct
2 Correct 9 ms 12032 KB Output is correct
3 Correct 10 ms 12032 KB Output is correct
4 Correct 9 ms 12032 KB Output is correct
5 Correct 8 ms 12032 KB Output is correct
6 Correct 10 ms 12032 KB Output is correct
7 Correct 8 ms 12032 KB Output is correct
8 Correct 8 ms 12032 KB Output is correct
9 Correct 8 ms 12032 KB Output is correct
10 Correct 8 ms 12032 KB Output is correct
11 Correct 8 ms 12032 KB Output is correct
12 Correct 9 ms 12032 KB Output is correct
13 Correct 8 ms 12032 KB Output is correct
14 Correct 9 ms 12032 KB Output is correct
15 Correct 8 ms 12032 KB Output is correct
16 Correct 8 ms 12032 KB Output is correct
17 Correct 8 ms 12032 KB Output is correct
18 Correct 8 ms 12032 KB Output is correct
19 Correct 14 ms 12160 KB Output is correct
20 Correct 17 ms 12032 KB Output is correct
21 Correct 9 ms 12160 KB Output is correct
22 Incorrect 9 ms 12160 KB 3rd lines differ - on the 1st token, expected: '2082', found: '2044'
23 Halted 0 ms 0 KB -