oj.uz

Submission #135779

# Submission time Handle Problem Language Result Execution time Memory
135779 2019-07-24T11:05:13 Z Utaha Jousting tournament (IOI12_tournament) C++14
100 / 100
 491 ms 46968 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector")
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pdd;
#define IOS ios_base::sync_with_stdio(0); cin.tie(0)
#define ALL(a) a.begin(),a.end()
#define SZ(a) ((int)a.size())
#define F first
#define S second
#define REP(i,n) for(int i=0;i<((int)n);i++)
#define pb emplace_back
#define MP(a,b) make_pair(a,b)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
template<typename T1,typename T2>
ostream& operator<<(ostream& out,pair<T1,T2> P){
	out<<'('<<P.F<<','<<P.S<<')';
	return out;
}
#define version 20190713
//}}}
const ll maxn=200005;
const ll maxlg=18;
const ll INF64=8000000000000000000LL;
const int INF=0x3f3f3f3f;
const ll MOD=ll(1e9+7);
const ld PI=acos(-1);
const ld eps=1e-9;

inline int low(int i){return i&(-i);}

int BIT[maxn];

void mdf(int u,int d){
	for(int i=u;i<maxn;i+=low(i+1)) BIT[i]+=d;
}
int query(int u){
	int ret=0;
	for(int i=u;i>=0;i-=low(i+1)) ret+=BIT[i];
	return ret;
}


map<pii,pii> mp;
map<pii,int> idx;
pii pos[maxn];
int anc[maxn][maxlg];

set<pii> st;

set<int> big;

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
	REP(i,N) st.insert(MP(i,i+1));

	REP(i,N) mdf(i,1);

	REP(i,C){
		int s,e;
		{
			int l=-1,r=N;
			while(l!=r-1){
				int mid=(l+r)/2;
				if(query(mid)<=S[i]) l=mid;
				else r=mid;
			}
			s=r;
		}
		{
			int l=-1,r=N;
			while(l!=r-1){
				int mid=(l+r)/2;
				if(query(mid)<=E[i]+1) l=mid;
				else r=mid;
			}
			e=r;
		}
		while(1){
			auto it=st.lower_bound(MP(s,s));
			if(it==st.end()||it->F==e) break;
			mp[*it]=MP(s,e);
			mdf(it->F,-1);
			st.erase(it);
		}
		mdf(s,1);
		st.insert(MP(s,e));
	}

	// for(auto i:mp) cout<<i<<'\n';

	int pt=0;
	for(auto i:mp){
		idx[i.F]=pt;
		pos[pt]=i.F;
		pt++;
	}
	idx[MP(0,N)]=pt;
	pos[pt]=MP(0,N);
	pt++;
	REP(i,pt){
		if(!mp.count(pos[i])){
			anc[i][0]=-1;
		}
		else anc[i][0]=idx[mp[pos[i]]];
	}
	for(int j=1;j<maxlg;j++) REP(i,pt){
		if(anc[i][j-1]==-1) anc[i][j]=-1;
		else anc[i][j]=anc[anc[i][j-1]][j-1];
	}

	// REP(i,pt){
		// cout<<pos[i]<<' '<<((anc[i][0]==-1)?MP(-1,-1):pos[anc[i][0]])<<'\n';
	// }

	REP(i,N-1) if(K[i]>R) big.insert(i);

	// for(int i:big) cout<<i<<' ';
	// cout<<'\n';

	int ret=N+1;
	int bst=-1;

	for(int place=0;place<N;place++){
		int A,B;
		{
			auto it=big.lower_bound(place);
			if(it==big.begin()) A=-1;
			else A=*prev(it);
		}
		{
			auto it=big.lower_bound(place);
			if(it==big.end()) B=N;
			else B=*it;
		}
		B++;
		// cout<<A<<' '<<B<<'\n';
		int cur_ans=0;
		int cur=idx[MP(place,place+1)];
		for(int i=maxlg-1;i>=0;i--){
			int nxt=anc[cur][i];
			// cout<<pos[cur]<<' '<<((nxt==-1)?MP(-1,-1):pos[nxt])<<' '<<i<<' '<<cur_ans<<'\n';
			if(nxt==-1);
			else{
				if(pos[nxt].F<=A||pos[nxt].S>B);
				else{
					cur=nxt;
					cur_ans^=(1<<i);
				}
			}
		}
		if(cur_ans==bst){
			ret=min(ret,place);
		}
		else if(cur_ans>bst){
			bst=cur_ans;
			ret=place;
		}
		// cout<<place<<' '<<cur_ans<<'\n';
	}
	return ret;
}

Subtask #1
17.0 / 17.0

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

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 888 KB Output is correct
2 Correct 18 ms 2680 KB Output is correct
3 Correct 9 ms 1656 KB Output is correct
4 Correct 20 ms 2680 KB Output is correct
5 Correct 16 ms 2424 KB Output is correct
6 Correct 16 ms 2168 KB Output is correct
7 Correct 18 ms 2552 KB Output is correct
8 Correct 18 ms 2680 KB Output is correct
9 Correct 9 ms 1656 KB Output is correct
10 Correct 22 ms 2572 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 215 ms 19168 KB Output is correct
2 Correct 472 ms 46968 KB Output is correct
3 Correct 204 ms 23704 KB Output is correct
4 Correct 449 ms 46392 KB Output is correct
5 Correct 438 ms 44408 KB Output is correct
6 Correct 453 ms 36408 KB Output is correct
7 Correct 491 ms 45900 KB Output is correct
8 Correct 468 ms 46584 KB Output is correct
9 Correct 224 ms 26316 KB Output is correct
10 Correct 237 ms 25336 KB Output is correct