oj.uz

Submission #315899

# Submission time Handle Problem Language Result Execution time Memory
315899 2020-10-24T10:45:23 Z amunduzbaev Jousting tournament (IOI12_tournament) C++14
100 / 100
 115 ms 18796 KB 
//#include "grader.cpp"

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

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

struct seg_tree{
	int n;
	vector<int> tree;
    void mtree(int l,int r,int x){
    	if(l==r) {
    		tree[x]=1; 
    		return;
    	}
    	int m=(l+r)/2;
    	mtree(l,m,x*2);
    	mtree(m+1,r,x*2+1);
    	tree[x]=tree[x*2] + tree[x*2+1];
    }
    void build(int N){
    	n=N;
    	tree.assign(n*4, 0);
    	mtree(1,n,1);
    }
	int get1(int val,int lx,int rx,int x){
		if(lx==rx) return lx;
		int m=(lx+rx)/2;
		if(val <= tree[x*2]) return get1(val,lx,m,x*2);
		else return get1(val-tree[x*2], m+1, rx, x*2+1);
	} 
	int get(int val){
		return get1(val,1,n,1);
	}

	void update1(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;
		update1(l,r,lx,mid,x*2);
		update1(l,r,mid+1,rx,x*2+1);
		tree[x] = tree[x*2]+tree[x*2+1];
	} 
	void update(int l,int r){
		update1(l,r,1,n,1);
	}
	void print(){
		for(int i=0;i<n*2;i++) cout<<tree[i]<<" ";
			cout<<"\n";
	}
	int fr(){
		return tree[1];
	}

};

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

}

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;
}


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



/*

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

*/

Compilation message

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

Subtask #1
17.0 / 17.0

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

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 5 ms 1280 KB Output is correct
3 Correct 2 ms 640 KB Output is correct
4 Correct 5 ms 1024 KB Output is correct
5 Correct 5 ms 1024 KB Output is correct
6 Correct 4 ms 768 KB Output is correct
7 Correct 6 ms 1152 KB Output is correct
8 Correct 5 ms 1024 KB Output is correct
9 Correct 2 ms 768 KB Output is correct
10 Correct 6 ms 896 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 4596 KB Output is correct
2 Correct 115 ms 18796 KB Output is correct
3 Correct 26 ms 5752 KB Output is correct
4 Correct 114 ms 14404 KB Output is correct
5 Correct 110 ms 15084 KB Output is correct
6 Correct 85 ms 8852 KB Output is correct
7 Correct 113 ms 15852 KB Output is correct
8 Correct 114 ms 15852 KB Output is correct
9 Correct 21 ms 6016 KB Output is correct
10 Correct 27 ms 6272 KB Output is correct