oj.uz

Submission #382789

# Submission time Handle Problem Language Result Execution time Memory
382789 2021-03-28T08:07:38 Z Keshi Jousting tournament (IOI12_tournament) C++17
100 / 100
 181 ms 26988 KB 
//In the name of God
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;

const ll maxn = 3e5 + 100;
const ll mod = 1e9 + 7;
const ll inf = 1e18;

#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io freopen("input.txt", "r+", stdin);freopen("output.txt", "w+", stdout);
#define pb push_back
#define Mp make_pair
#define F first
#define S second
#define Sz(x) ll((x).size())
#define all(x) (x).begin(), (x).end()
#define lc (id << 1)
#define rc (lc | 1)

ll seg[maxn << 2];

void bld(ll id, ll s, ll e){
	seg[id] = e - s;
	if(e - s == 1) return;
	ll mid = (s + e) >> 1;
	bld(lc, s, mid);
	bld(rc, mid, e);
	return;
}
void upd(ll id, ll s, ll e, ll l, ll r){
	if(seg[id] == 0 || r <= s || e <= l) return;
	if(l <= s && e <= r){
		seg[id] = 0;
		return;
	}
	ll mid = (s + e) >> 1;
	upd(lc, s, mid, l, r);
	upd(rc, mid, e, l, r);
	seg[id] = seg[lc] + seg[rc];
	return;
}
ll get(ll id, ll s, ll e, ll x){
	if(seg[id] < x) return e;
	if(e - s == 1) return s;
	ll mid = (s + e) >> 1;
	if(seg[lc] < x) return get(rc, mid, e, x - seg[lc]);
	return get(lc, s, mid, x);
}
ll dp[maxn], ok[maxn], l[maxn], r[maxn], b[maxn];
vector<ll> g[maxn];
void dfs(ll v){
	dp[v] += ok[v];
	for(ll u : g[v]){
		dp[u] += dp[v];
		dfs(u);
	}
	return;
}

int GetBestPosition(int n, int c, int x, int *a, int *s, int *e){
	bld(1, 0, n);
	set<ll> st, ss;
	for(ll i = 0; i < n; i++){
		st.insert(i);
		b[i] = i;
	}
	for(ll i = 0; i < n - 1; i++){
		if(a[i] > x) ss.insert(i);
	}
	ss.insert(n);
	for(ll i = 0; i < c; i++){
		l[n + i] = get(1, 0, n, s[i] + 1);
		r[n + i] = get(1, 0, n, e[i] + 2);
		upd(1, 0, n, l[n + i] + 1, r[n + i]);
		auto it = st.lower_bound(l[n + i]);
		while(it != st.end() && *it < r[n + i]){
			g[n + i].pb(b[*it]);
			it = st.erase(it);
		}
		b[l[n + i]] = n + i;
		st.insert(l[n + i]);
		if(*ss.lower_bound(l[n + i]) >= r[n + i] - 1) ok[n + i] = 1;
	}
	dfs(n + c - 1);
	ll ans = 0;
	for(ll i = 0; i < n; i++){
		if(dp[i] > dp[ans]) ans = i;
	}
	return ans;
}

/*int main(){
    fast_io;
    
    int n, c, x, a[100], s[100], e[100];
    cin >> n >> c >> x;
    for(ll i = 0; i < n - 1; i++){
    	cin >> a[i];
	}
	for(ll i = 0; i < c; i++){
		cin >> s[i] >> e[i];
	}
	cout << GetBestPosition(n, c, x, a, s, e);
 
    return 0;
}*/

Subtask #1
17.0 / 17.0

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

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7532 KB Output is correct
2 Correct 13 ms 8556 KB Output is correct
3 Correct 8 ms 7916 KB Output is correct
4 Correct 12 ms 8300 KB Output is correct
5 Correct 13 ms 8300 KB Output is correct
6 Correct 11 ms 8044 KB Output is correct
7 Correct 13 ms 8300 KB Output is correct
8 Correct 13 ms 8300 KB Output is correct
9 Correct 8 ms 8044 KB Output is correct
10 Correct 14 ms 8172 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 13676 KB Output is correct
2 Correct 181 ms 26988 KB Output is correct
3 Correct 54 ms 16620 KB Output is correct
4 Correct 170 ms 24044 KB Output is correct
5 Correct 167 ms 24312 KB Output is correct
6 Correct 161 ms 18736 KB Output is correct
7 Correct 170 ms 24700 KB Output is correct
8 Correct 177 ms 25068 KB Output is correct
9 Correct 65 ms 20332 KB Output is correct
10 Correct 72 ms 18668 KB Output is correct