oj.uz

Submission #406328

# Submission time Handle Problem Language Result Execution time Memory
406328 2021-05-17T11:33:53 Z ritul_kr_singh Jousting tournament (IOI12_tournament) C++17
100 / 100
 123 ms 24428 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define sp << ' ' <<
#define nl << '\n'

struct FenwickTree{
	vector<int> a; int n, s;
	FenwickTree(int N){ a.resize((n=N)+1); }
	void add(int i, int v){
		for(++i; i<=n; i+=i&-i) a[i] += v;
	}
	int get(int i){
		for(s=0; i>=1; i-=i&-i) s += a[i];
		return s;
	}
	int get(int l, int r){ return get(r+1) - get(l); }
	int lower(int v){
		int i = 0;
		for(s=1<<20; s; s/=2) if(i+s<=n && a[i+s]<v) v -= a[i+=s];
		return i;
	}
};

const int MAXN = 2e5;

struct SegmentTree{
	vector<int> a; int sz = 1;
	void init(vector<int> &v){
		while(sz < (int)v.size()) sz += sz;
		a.assign(2*sz, -1);
		build(v, 0, 0, sz);
	}
	void build(vector<int> &v, int x, int lx, int rx){
		if(rx-lx==1){
			if(lx < (int)v.size()) a[x] = v[lx];
			return;
		}
		int mx = (lx + rx) / 2;
		build(v, 2*x+1, lx, mx);
		build(v, 2*x+2, mx, rx);
		a[x] = max(a[2*x+1], a[2*x+2]);
	}
	int rangeMax(int l, int r, int x, int lx, int rx){
		if(r<=lx || rx<=l) return -1;
		if(l<=lx && rx<=r) return a[x];
		int mx = (lx + rx) / 2;
		return max(rangeMax(l, r, 2*x+1, lx, mx), rangeMax(l, r, 2*x+2, mx, rx));
	}
	int rangeMax(int l, int r){ return rangeMax(l, r+1, 0, 0, sz); }
};


vector<int> g[MAXN];
int low[MAXN], high[MAXN], lim;
array<int, 2> dist[MAXN];
array<int, 2> ans = {0, 0};

SegmentTree st;

void dfs(int u){
	if(g[u].empty()){
		low[u] = high[u] = u;
		dist[u] = {0, -u};
	}else low[u] = MAXN * 3, high[u] = -1;

	for(int v : g[u]){
		dfs(v);
		low[u] = min(low[u], low[v]);
		high[u] = max(high[u], high[v]);
		++dist[v][0];
		dist[u] = max(dist[u], dist[v]);
	}

	int m = st.rangeMax(low[u], high[u] - 1);
	if(m <= lim) ans = max(ans, dist[u]);
}

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E){
	FenwickTree f(N);
	lim = R;
	for(int i=0; i<N; ++i) f.add(i, 1);

	int a[N]; iota(a, a+N, 0LL);
	int curr = N - 1;

	for(int i=0; i<C; ++i){
		++curr;
		int l = f.lower(S[i] + 1), num = E[i] - S[i] + 1;
		g[curr].push_back(a[l]);
		a[l] = curr;
		for(int j=1; j<num; ++j){
			int k = f.lower(S[i] + 2);
			g[curr].push_back(a[k]);
			f.add(k, -1);
		}
	}

	vector<int> v(N-1);
	for(int i=0; i<N-1; ++i) v[i] = K[i];
	st.init(v);

	dfs(curr);

	return -ans[1];
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 4 ms 4940 KB Output is correct
3 Correct 4 ms 5004 KB Output is correct
4 Correct 4 ms 5076 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Correct 4 ms 5004 KB Output is correct
7 Correct 4 ms 5068 KB Output is correct
8 Correct 4 ms 5000 KB Output is correct
9 Correct 4 ms 4940 KB Output is correct
10 Correct 4 ms 4940 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5068 KB Output is correct
2 Correct 8 ms 6096 KB Output is correct
3 Correct 5 ms 5268 KB Output is correct
4 Correct 8 ms 5580 KB Output is correct
5 Correct 7 ms 5708 KB Output is correct
6 Correct 8 ms 5396 KB Output is correct
7 Correct 9 ms 5776 KB Output is correct
8 Correct 8 ms 5708 KB Output is correct
9 Correct 6 ms 5196 KB Output is correct
10 Correct 8 ms 5452 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 9376 KB Output is correct
2 Correct 103 ms 24428 KB Output is correct
3 Correct 45 ms 10528 KB Output is correct
4 Correct 100 ms 19356 KB Output is correct
5 Correct 123 ms 20812 KB Output is correct
6 Correct 93 ms 13892 KB Output is correct
7 Correct 100 ms 20988 KB Output is correct
8 Correct 110 ms 21044 KB Output is correct
9 Correct 38 ms 10148 KB Output is correct
10 Correct 46 ms 10460 KB Output is correct