oj.uz

Submission #293726

# Submission time Handle Problem Language Result Execution time Memory
293726 2020-09-08T10:49:35 Z shayan_p Ancient Books (IOI17_books) C++17
0 / 100
 14 ms 12032 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)
		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();
	}
    }

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

    int tmp = fnd(s);
    assert(par[tmp] == -1);
    while(tmp != -1){
	int PTL = L[tmp], PTR = R[tmp];
	int _PTL = (par[tmp] == -1 ? -1 : L[par[tmp]]), _PTR = (par[tmp] == -1 ? n : 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
0 / 12.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 28.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 30.0

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