oj.uz

Submission #518805

# Submission time Handle Problem Language Result Execution time Memory
518805 2022-01-24T17:28:35 Z AdamGS Jousting tournament (IOI12_tournament) C++17
100 / 100
 83 ms 6888 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=1e5+7;
int tr[4*LIM], lazy[4*LIM], ma[4*LIM], sum[4*LIM], N=1, n, m, k;
void spl(int v) {
	tr[2*v]=0;
	tr[2*v+1]=0;
	lazy[2*v]=1;
	lazy[2*v+1]=1;
	lazy[v]=0;
}
void upd(int v, int l, int r, int a, int b) {
	if(l>b || r<a) return;
	if(a<=l && r<=b) {
		tr[v]=0;
		lazy[v]=1;
		return;
	}
	if(lazy[v]) spl(v);
	int mid=(l+r)/2;
	upd(2*v, l, mid, a, b);
	upd(2*v+1, mid+1, r, a, b);
	tr[v]=tr[2*v]+tr[2*v+1];
}
int znajdz(int v, int k) {
	if(v>=N) return v-N;
	if(lazy[v]) spl(v);
	if(tr[2*v]>=k) return znajdz(2*v, k);
	return znajdz(2*v+1, k-tr[2*v]);
}
int cnt(int l, int r) {
	l+=N; r+=N;
	int ans=max(ma[l], ma[r]);
	while(l/2!=r/2) {
		if(l%2==0) ans=max(ans, ma[l+1]);
		if(r%2==1) ans=max(ans, ma[r-1]);
		l/=2; r/=2;
	}
	return ans;
}
void dodaj(int l, int r) {
	l+=N; r+=N;
	++sum[l];
	if(l!=r) ++sum[r];
	while(l/2!=r/2) {
		if(l%2==0) ++sum[l+1];
		if(r%2==1) ++sum[r-1];
		l/=2; r/=2;
	}
}
int GetBestPosition(int D, int C, int R, int *K, int *S, int *E) {
	n=D; m=C; k=R;
	while(N<n) N*=2;
	rep(i, N) tr[N+i]=1;
	rep(i, n-1) ma[N+i]=K[i];
	for(int i=N-1; i; --i) {
		tr[i]=tr[2*i]+tr[2*i+1];
		ma[i]=max(ma[2*i], ma[2*i+1]);
	}
	rep(i, m) {
		int l, r=znajdz(1, E[i]+1);
		if(S[i]==0) l=0;
		else l=znajdz(1, S[i])+1;
		if(cnt(l, r-1)<k) dodaj(l, r);
		upd(1, 0, N-1, l, r-1);
	}
	for(int i=1; i<N; ++i) {
		sum[2*i]+=sum[i];
		sum[2*i+1]+=sum[i];
	}
	pair<int,int>ans={-1, -1};
	rep(i, n) ans=max(ans, {sum[N+i], -i});
	return -ans.nd;
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 328 KB Output is correct
7 Correct 1 ms 300 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 0 ms 312 KB Output is correct
10 Correct 1 ms 312 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 316 KB Output is correct
2 Correct 4 ms 576 KB Output is correct
3 Correct 1 ms 572 KB Output is correct
4 Correct 3 ms 632 KB Output is correct
5 Correct 3 ms 592 KB Output is correct
6 Correct 4 ms 592 KB Output is correct
7 Correct 4 ms 572 KB Output is correct
8 Correct 5 ms 720 KB Output is correct
9 Correct 1 ms 464 KB Output is correct
10 Correct 5 ms 568 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 3140 KB Output is correct
2 Correct 71 ms 6840 KB Output is correct
3 Correct 13 ms 4432 KB Output is correct
4 Correct 83 ms 6888 KB Output is correct
5 Correct 78 ms 6664 KB Output is correct
6 Correct 46 ms 6168 KB Output is correct
7 Correct 73 ms 6816 KB Output is correct
8 Correct 72 ms 6836 KB Output is correct
9 Correct 13 ms 4236 KB Output is correct
10 Correct 16 ms 5072 KB Output is correct