Submission #1013159

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013159		jcelin	Jousting tournament (IOI12_tournament)	C++14	100 / 100	79 ms	9412 KiB

tournament

#include<bits/stdc++.h>

using namespace std;

#define X first
#define Y second
#define PB push_back
#define PPB pop_back
#define all(x) (x).begin(), (x).end()

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef pair<ll, ll> pll;

const int inf = 1e9 + 7;
const int MAXN = 1e5 + 7;
const int logo = 17;
const int off = 1 << logo;
const int trsz = off << 1;
const int mod = 1e9;
const int dx[] = {0, 0, -1, 1};
const int dy[] = {1, -1, 0, 0};

struct tournament{
	int seg[trsz];
	
	void update(int x, int vl){
		x += off;
		seg[x] = vl;
		for(x /= 2; x; x /= 2) seg[x] = seg[x * 2] + seg[x * 2 + 1];
	}
	
	int query(int x, int k){
		if(x >= off) return (x - off) - 1;
		if(seg[x * 2] > k) return query(x * 2, k);
		k -= seg[x * 2];
		return query(x * 2 + 1, k);
	}
}t;

int pf[MAXN], p[MAXN], cnt[MAXN];
vi temp;
set<int> act;

int GetBestPosition(int n, int m, int rank, int *K, int *L, int *R) {
    for(int i=0; i<n; i++){
		if(i) pf[i] = pf[i - 1];
		if(i != n - 1 and K[i] > rank) pf[i]++;			
		t.update(i, 1);
		act.insert(i);
	}
	
    for(int i=0; i<m; i++){
        int l = t.query(1, L[i]) + 1;
        int r = min(t.query(1, R[i] + 1), n - 1);
        temp.clear();
        
        auto it = act.lower_bound(l);
        while(1){
			temp.PB(*it);
			it++;
			if(it == act.end() or *it > r) break;
		}
		
		for(auto &x : temp){
			t.update(x, 0);
			act.erase(x);
		}
        
        t.update(l, 1);
        act.insert(l);
        
        //mogu kickat zadnjeg
        
        int vl = pf[r - 1];
        if(l != 0) vl -= pf[l - 1];
        
        if(vl == 0){
			cnt[l]++;
			cnt[r + 1]--;	
		}
    }
    
    ii ans = {-inf, -inf};
    for(int i=0; i<n; i++){
		if(i) cnt[i] += cnt[i - 1];
		//cout << cnt[i] << " " << i << "\n";
		ans = max(ans, (ii){cnt[i], -i});
	}
    return -ans.Y;
}

/*
int kk[MAXN], le[MAXN], ri[MAXN]; 
void solve(){
	int n, m, ja;
	cin >> n >> m >> ja;
	for(int i=0; i<n-1; i++) cin >> kk[i];
	for(int i=0; i<m; i++) cin >> le[i] >> ri[i];
	cout << GetBestPosition(n, m, ja, kk, le, ri) << "\n";
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int _ = 1;
	//cin >> _;
	while(_--) solve();
	return 0;
}
*/

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