oj.uz

Submission #274682

# Submission time Handle Problem Language Result Execution time Memory
274682 2020-08-19T14:06:22 Z shayan_p Jousting tournament (IOI12_tournament) C++14
0 / 100
 51 ms 9180 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], dp2[maxn], dp3[maxn], ans[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];
	dp2[u] = 0;
	dp3[u] = a[u];
	ans[u] = 0;
	return;
    }
    ans[u] = dp1[u] = dp3[u] = 0;
    dp2[u] = -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] != -1)
	    dp2[u] = max(dp2[u], 1 + dp2[y]);
	if(R == y)
	    break;
    }
    ans[u] = max(ans[u], dp2[u]);
}

int GetBestPosition(int n, int q, int r, int *a, int *L, int *R){
    ::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];
}

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5120 KB Output is correct
2 Incorrect 4 ms 5120 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 5120 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Incorrect 51 ms 9180 KB Output isn't correct
2 Halted 0 ms 0 KB -