Submission #282509

#	Time	Username	Problem	Language	Result	Execution time	Memory
282509		Nucleist	Jousting tournament (IOI12_tournament)	C++14	49 / 100	1089 ms	1596 KiB

tournament

//Self-control leads to consistency.
#include <bits/stdc++.h> 
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
using namespace __gnu_pbds;
using namespace std; 
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define flash ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define debug(x) cerr << " - " << #x << ": " << x << endl;
#define debugs(x, y) cerr << " - " << #x << ": " << x << " " << #y << ": " << y << endl;
#define all(x) (x).begin(),(x).end()
#define sz(x) (ll)x.size()
#define ll long long
#define INF 1000000000
#define MOD 1000000007
#define pb push_back
#define ve vector<ll>
#define dos pair<ll,ll>
#define vedos vector<dos>
#define rand mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define EPS 0.000001
struct greateri
{
    template<class T>
    bool operator()(T const &a, T const &b) const { return a > b; }
};
void setIO(string s) {
	ios_base::sync_with_stdio(0); cin.tie(0); 
	freopen((s+".in").c_str(),"r",stdin);
	freopen((s+".out").c_str(),"w",stdout);
}
typedef tree<
pair<int,dos>,
null_type,
less<pair<int,dos>>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
ordered_set X;
int p[100001];
int seg[1000001];
set<pair<dos,int>>ko,zo;
void update(int p,int l,int r,int index,int val){
	if(l==r && l==index){
		seg[p]=val;
		return;
	}
	ll med=(l+r)>>1;
	if(index<=med)
		update(p*2,l,med,index,val);
	else update(p*2+1,med+1,r,index,val);
	seg[p]=max(seg[p*2],seg[p*2+1]);
}
int query(int p,int l,int r,int l1,int r1){
	if(l>=l1 && r<=r1){
		return seg[p];
	}
	if(l>r || l>r1 || l1>r)return -INF;
	ll med=(l+r)>>1;
	return max(query(p*2,l,med,l1,r1),query(p*2+1,med+1,r,l1,r1));
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
  vedos prep;
  for (int i = 0; i < N; ++i)
  {
  	p[i]=i;
  }
  for (int i = 0; i < C; ++i)
  {
  	int l=S[i],r=E[i];
  	int yo=-1,zo=-1;
  	ll um=1;
  	for (int j = 0; j < N; ++j)
  	{
  		if(p[j]>=l && p[j]<=r){
  			p[j]=l;
  			if(yo==-1){
  				yo=j;
  			}
  			else zo=j;
  		}
  		else if(p[j]>r){
  			bool ka=0;
  			if(p[j]!=p[j+1]){
  				ka=1;
  			}
  			p[j]=l+um;
  			if(ka)um++;
  		}
  	}
  	if(yo!=-1)
  		prep.pb({yo,zo});
  }
  int ini=0;
  for(auto it:prep){
    ko.insert({{it.first,it.second},ini});
    zo.insert({{it.second,it.first},ini});
    ini++;
  }
  for (int i = 0; i < N-1; ++i)
  {
  	update(1,0,N*2-1,i*2,K[i]);
  	update(1,0,N*2-1,i*2+1,-INF);
  }
  ve cur;
  dos best={-INF,0};
  int index=0;
  for(auto it:prep){
  		if(0>=it.first && 0<=it.second){
  			cur.pb(index);
        auto f=ko.lower_bound({{it.first,it.second},-INF});
        X.insert({(*f).second,(*f).first});
  		}
  		index++;
   }
	int l=0,r=sz(cur)-1;
	ll ans=-1;
	while(l<=r){
		ll med=(l+r)>>1;
		auto u=prep[cur[med]];
		auto zel=0;
		if(u.first==0){
			zel=max(query(1,0,N*2-1,u.first*2,(u.second)*2-1),R);
		}
		if(zel==R){
			ans=med+1;
			l=med+1;
		}
		else r=med-1;
	}
	if(ans==-1)ans=0;
	if(best.first<ans)
		best=max(best,{ans,0});
  for (int i = 1; i < N; ++i)
  {
    auto v=ko.lower_bound({{i,-INF},-INF});
    while(v!=ko.end() && (*v).first.first==i){
      X.insert({(*v).second,(*v).first});
      v++;
    }
  	update(1,0,N*2-1,(i-1)*2+1,R);
  	if(i>1)update(1,0,N*2-1,(i-2)*2+1,-INF);
  	cur.clear();
  	index=0;
  	for(auto it:prep){
  		if(i>=it.first && i<=it.second){
  			cur.pb(index);
  		}
  		index++;
  	}
  	l=0,r=sz(cur)-1;
  	ans=-1;
  	while(l<=r){
  		ll med=(l+r)>>1;
  		auto lo=X.find_by_order(med);
      auto u=(*lo).second;
      //u=prep[cur[med]];
  		auto zel=0;
  		if(i>u.first && i<=u.second){
  			zel=query(1,0,N*2-1,u.first*2,(u.second)*2-1);
  		}
  		else if(i==u.first){
  			zel=query(1,0,N*2-1,(u.first-1)*2+1,(u.second)*2-1);
  		}
  		if(zel==R){
  			ans=med+1;
  			l=med+1;
  		}
  		else r=med-1;
  	}
  	if(ans==-1)ans=0;
  	if(best.first<ans)
  		best=max(best,{ans,i});
    auto l=zo.lower_bound({{i,-INF},-INF});
    while(l!=zo.end() && (*l).first.first==i){
      X.erase({(*l).second,{(*l).first.second,(*l).first.first}});
      l++;
    }
  }
  return best.second;
}

Compilation message (stderr)

tournament.cpp:8: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    8 | #pragma GCC optimization ("O3")
      | 
tournament.cpp:9: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    9 | #pragma GCC optimization ("unroll-loops")
      | 
tournament.cpp: In function 'void setIO(std::string)':
tournament.cpp:31:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   31 |  freopen((s+".in").c_str(),"r",stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
tournament.cpp:32:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   32 |  freopen((s+".out").c_str(),"w",stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 17 / 17
• Subtask 2: 32 / 32
• Subtask 3: 0 / 51