oj.uz

Submission #70001

# Submission time Handle Problem Language Result Execution time Memory
70001 2018-08-22T08:35:57 Z WA_TLE Jousting tournament (IOI12_tournament) C++14
100 / 100
 154 ms 29028 KB 
#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<array>
#include<map>
#include<iomanip>
#include<assert.h>
#include<bitset>
#include<stack>
#include<memory>
using namespace std;
typedef long long int llint;
typedef long double lldo;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase
/*
cout<<setprecision(20);
cin.tie(0);
ios::sync_with_stdio(false);
*/
const llint mod=1000000000;
const llint big=2.19e15+1;
const long double pai=3.141592653589793238462643383279502884197;
const long double eps=1e-15;
template <class T,class U>bool mineq(T& a,U b){if(a>b){a=b;return true;}return false;}
template <class T,class U>bool maxeq(T& a,U b){if(a<b){a=b;return true;}return false;}
llint gcd(llint a,llint b){if(a%b==0){return b;}else return gcd(b,a%b);}
llint lcm(llint a,llint b){if(a==0){return b;}return a/gcd(a,b)*b;}
template<class T> void SO(T& ve){sort(ve.begin(),ve.end());}
template<class T> void REV(T& ve){reverse(ve.begin(),ve.end());}
template<class T>llint LBI(vector<T>&ar,T in){return lower_bound(ar.begin(),ar.end(),in)-ar.begin();}
template<class T>llint UBI(vector<T>&ar,T in){return upper_bound(ar.begin(),ar.end(),in)-ar.begin();}
/*
各ラウンドについて木を作る
nラウンド上 をダブリング 自分より強い騎士に当たらなければよい
それで求める

左から何番目か を探すのに結局セグ木がいる
*/
int GetBestPosition(int N,int C,int RR,int K[],int S[],int E[]){
	//SとEがもともとどこからどこだったのですか?
	if(RR+1==N){return 0;}//tourist
	vector<int>mtS(C);
	vector<int>mtE(C);
	int h,i,j;
	static int seg[262144]={0};//1,1
	seg[1]=131072;
	for(i=2;i<262144;i++){seg[i]=seg[i/2]/2;}
	vector<array<int,18>>dab(C+N);
	vector<int>dare(N);
	for(i=0;i<N;i++){dare[i]=i+C;}
	for(i=0;i<C;i++){
		int s=S[i],e=E[i]+1;
		int bas=1;
		while(bas<131072){
			bas*=2;
			if(seg[bas]<=s){s-=seg[bas];bas++;}
		}
		dab[dare[bas-131072]][0]=i;
		mtS[i]=bas-131072;
		dare[mtS[i]]=i;
		bas=1;
		while(bas<131072){
			bas*=2;
			if(seg[bas]<=e){e-=seg[bas];bas++;}
		}
		mtE[i]=bas-131072;
		//cerr<<"e="<<e<<endl;
		for(j=S[i]+1;j<=E[i];j++){
			bas=1;int ge=S[i]+1;
			while(bas<131072){
				bas*=2;
				if(seg[bas]<=ge){ge-=seg[bas];bas++;}
			}
			dab[dare[bas-131072]][0]=i;
			while(bas>0){seg[bas]--;bas/=2;}
		}
		//cerr<<mtS[i]<<" "<<mtE[i]<<endl;
	}
	//これで木を作ることができた
	//ダブリングをおこなう
	dab[C-1][0]=C-1;
	for(h=1;h<18;h++){
		for(i=0;i<N+C;i++){dab[i][h]=dab[dab[i][h-1]][h-1];}
		
	}
	//次に誰が勝つかを行う
	vector<bool>tuyo(N);
	for(i=0;i<N-1;i++){tuyo[i]=(RR<K[i]);}
	tuyo[N-1]=1;
	for(j=0;j<N;j++){if(tuyo[j]){break;}}
	int L=0,R=j+1;
	int sai=-1,ans=-1;
	for(i=0;i<N;i++){
		//cerr<<L<<" "<<R<<endl;
		int win=0,rod=C+i;
		for(h=17;h>=0;h--){
			int nex=dab[rod][h];
			if(L<=mtS[nex]&&mtE[nex]<=R){rod=dab[rod][h];win+=(1<<h);}
		}
		//cerr<<win<<endl;
		if(sai<win){sai=win;ans=i;}
		if(tuyo[i]){
			for(j=i+1;j<N;j++){if(tuyo[j]){break;}}
			L=i+1;R=j+1;
		}
	}
	return ans;
}

Subtask #1
17.0 / 17.0

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

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1768 KB Output is correct
2 Correct 8 ms 2552 KB Output is correct
3 Correct 8 ms 2552 KB Output is correct
4 Correct 8 ms 2552 KB Output is correct
5 Correct 8 ms 2612 KB Output is correct
6 Correct 8 ms 2612 KB Output is correct
7 Correct 10 ms 2836 KB Output is correct
8 Correct 11 ms 2836 KB Output is correct
9 Correct 6 ms 2836 KB Output is correct
10 Correct 10 ms 2888 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 9348 KB Output is correct
2 Correct 154 ms 20444 KB Output is correct
3 Correct 56 ms 20444 KB Output is correct
4 Correct 133 ms 22840 KB Output is correct
5 Correct 130 ms 23752 KB Output is correct
6 Correct 136 ms 23752 KB Output is correct
7 Correct 144 ms 27380 KB Output is correct
8 Correct 138 ms 29028 KB Output is correct
9 Correct 67 ms 29028 KB Output is correct
10 Correct 81 ms 29028 KB Output is correct