oj.uz

Submission #274691

# Submission time Handle Problem Language Result Execution time Memory
274691 2020-08-19T14:16:53 Z shayan_p Jousting tournament (IOI12_tournament) C++14
100 / 100
 82 ms 25464 KB 
// And you curse yourself for things you never done

#include<bits/stdc++.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 = 2e5 + 10, mod = 1e9 + 7, inf = 1e9 + 10;

int fn[maxn];
void add(int pos, int x){
    for(pos+=3; pos < maxn; pos+= (pos & -pos))
	fn[pos]+= x;   
}
int fnd(int k){
    int ans = 0;
    for(int i = 19; i >= 0; i--){
	if(ans + (1<<i) >= maxn)
	    continue;
	if(fn[ans+(1<<i)] <= k)
	    ans+= 1<<i, k-= fn[ans];
    }
    return ans+1-3;
}
int vert[maxn];
int dp1[maxn], dp3[maxn];
pii ans[maxn], dp2[maxn];

vector<int> v[maxn];
int a[maxn], n;

void dfs(int u){
    if(u < n){
	if(u == 0)
	    dp1[u] = 0;
	else
	    dp1[u] = a[u-1];
	if(u == n-1)
	    dp3[u] = 0;
	else
	    dp3[u] = a[u];
	ans[u] = dp2[u] = {0, -u};
	return;
    }
    dp1[u] = dp3[u] = 0;
    dp2[u] = ans[u] = {-1, -1};
    
    int L = -1, R = -1;
    for(int y : v[u]){// are sorted
	dfs(y);
	dp1[u]|= dp1[y];
	dp3[u]|= dp3[y];
	ans[u] = max(ans[u], ans[y]);

	if(dp3[y] && R == -1)
	    R = y;
	if(dp1[y])
	    L = y;
    }    
    bool start = (L == -1);
    for(int y : v[u]){
	start|= L == y;
	if(start && dp2[y].F != -1)
	    dp2[u] = max(dp2[u], (pii){dp2[y].F + 1, dp2[y].S} );
	if(R == y)
	    break;
    }
    ans[u] = max(ans[u], dp2[u]);
}

int ITER = 0;

int GetBestPosition(int n, int q, int r, int *a, int *L, int *R){
    assert(++ITER <= 1);
    
    memset(fn, 0, sizeof fn); // tl?
    
    ::n = n;
    for(int i = 0; i < n-1; i++){
	a[i] = r < a[i];
	::a[i] = a[i];
    }
    for(int i = 0; i < n; i++){
	vert[i] = i;
	add(i, 1);
    }
    for(int i = 0; i < n+q; i++){
	v[i].clear();
    }
    for(int i = 0; i < q; i++){
	int cnt = R[i] - L[i], l = fnd(L[i]);
	v[i+n].PB(vert[l]);
	vert[l] = i+n;
	for(int w = 0; w < cnt; w++){
	    int pos = fnd(L[i]+1);
	    v[i+n].PB(vert[pos]);
	    add(pos, -1);
	}
    }
    dfs(n+q-1);
    return -ans[n+q-1].S;
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5888 KB Output is correct
2 Correct 5 ms 5888 KB Output is correct
3 Correct 5 ms 5888 KB Output is correct
4 Correct 4 ms 6016 KB Output is correct
5 Correct 4 ms 5920 KB Output is correct
6 Correct 4 ms 5888 KB Output is correct
7 Correct 5 ms 5888 KB Output is correct
8 Correct 5 ms 5888 KB Output is correct
9 Correct 5 ms 5888 KB Output is correct
10 Correct 4 ms 5888 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5888 KB Output is correct
2 Correct 8 ms 6784 KB Output is correct
3 Correct 6 ms 6144 KB Output is correct
4 Correct 8 ms 6528 KB Output is correct
5 Correct 7 ms 6528 KB Output is correct
6 Correct 7 ms 6304 KB Output is correct
7 Correct 8 ms 6656 KB Output is correct
8 Correct 8 ms 6528 KB Output is correct
9 Correct 5 ms 6016 KB Output is correct
10 Correct 8 ms 6400 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 9592 KB Output is correct
2 Correct 80 ms 25464 KB Output is correct
3 Correct 36 ms 11004 KB Output is correct
4 Correct 75 ms 20344 KB Output is correct
5 Correct 76 ms 21908 KB Output is correct
6 Correct 77 ms 14584 KB Output is correct
7 Correct 82 ms 22056 KB Output is correct
8 Correct 78 ms 22092 KB Output is correct
9 Correct 32 ms 10352 KB Output is correct
10 Correct 39 ms 10872 KB Output is correct