Submission #315853

#	Time	Username	Problem	Language	Result	Execution time	Memory
315853		amunduzbaev	Jousting tournament (IOI12_tournament)	C++14	0 / 100	30 ms	7796 KiB

tournament

//#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;


struct seg_tree{
	vector<int>tree;
	int s;
	void build(int n){
		s=1;
		while(s<n)s*=2;
		tree.assign(s*2, n);
		set(1,s,1);
	}
	void set(int l,int r,int x){
		if(l==r){
			tree[x]=1;
			return ;
		}
		int mid=(l+r)/2;
		set(l,mid,x*2);
		set(mid+1,r,x*2+1);
		tree[x]=tree[x*2]+tree[x*2+1];
	}
	int get(int l,int lx,int rx,int x){
		if(lx==rx) return lx;
		int m=(lx+rx)/2;
		if(l <= tree[x*2]) return get(l,lx,m,x*2);
		else return get(l,m+1,rx,x*2+1);
	}

	void update(int l,int r,int lx,int rx,int x){
		if(lx>=r||rx<=l) return;
		if(lx>=l&&rx<=r){
			tree[x]=0;
			return;
		}
		int mid=(lx+rx)/2;
		update(l,r,lx,mid,x*2);
		update(l,r,mid+1,rx,x*2+1);
		tree[x]=tree[x*2]+tree[x*2+1];

	}

};

int n, c, last, k[N], s[N], e[N];
vector<pair<int,int>> ranges;
vector<int> pref;
vector<vector<int>> edges;

bool cmp(pair<int,int> a,pair<int,int> b){
	if(a.first==b.first) return a.second>b.second;
	return a.first < b.first;
}

pair<int,int> dfs(int u,int p){
	int mx=0, ind=ranges[u].first;
	for(auto v:edges[u]){
		if(v==p) continue;
		auto it=dfs(v,u);
		if(it.first > mx){
			mx=it.first;
			ind=it.second;
		}
	}
	if(pref[ranges[u].second-1] - pref[ranges[u].first-1] == 0)
		mx++;
	return {mx,ind};

}

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
    n=N, c=C, last=R;
    for(int i=0;i<n-1;i++) k[i]=K[i];
    for(int i=0;i<c;i++) s[i]=S[i], e[i]=E[i];
   	seg_tree tree;
   	tree.build(n);
   	for(int i=0;i<c;i++){
   		int l=tree.get(s[i],1,n,1), r;
   		if(e[i]>=tree.tree[1]) r=n;
   		else r=tree.get(e[i],1,n,1);
   		ranges.push_back({l,r});
   		tree.update(l+1,r,1,n,1);
   	}
   	sort(ranges.begin(), ranges.end(), cmp);
   	pref.assign(n+1,0);
   	for(int i=1;i<n;i++) {
   		pref[i] += pref[i-1];
   		if(k[i-1] > last) pref[i]++;
   	}
   	edges.resize(n+1);
   	for(int i=1; i<ranges.size(); i++){
   		int j=i-1, fr=ranges[i].first, sc=ranges[i].second;
   		while(!(fr>=ranges[j].first && sc<=ranges[j].second)&&j>=0) j--;
   		edges[j].push_back(i);
   		edges[i].push_back(j);
   	}
   	auto ans=dfs(0,-1);
    return ans.second;
}
/*

5 3
3
1 0 2 4
1 3
0 1
0 1

*/

Compilation message (stderr)

tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:94:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |     for(int i=1; i<ranges.size(); i++){
      |                  ~^~~~~~~~~~~~~~

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