Submission #287914

#	Time	Username	Problem	Language	Result	Execution time	Memory
287914		erd1	Jousting tournament (IOI12_tournament)	C++14	100 / 100	190 ms	9972 KiB

tournament

#include<bits/stdc++.h>
using namespace std;
#include<bits/extc++.h>
using namespace __gnu_pbds;
template<typename T>
using order_statistics_tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
#define pb push_back
typedef int64_t lld;
typedef pair<int, int> pii;
typedef long double ld;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, pair<T1, T2> p){
  return out << "(" << p.ff << ", " << p.ss << ")";
}

template<typename Iter>
ostream& outIt(ostream& out, Iter b, Iter e){
  for(Iter i = b; i != e; i++)
    out << (i==b?"":" ") << *i;
  return out;
}

template<typename T>
ostream& operator<<(ostream& out, vector<T> v){
  return outIt(out << '[', all(v)) << ']';
}

vector<pii> rounds;
vector<int> lcnt, oops;

/*
struct node{
  node*L = 0, *R = 0;
  int l, r;
  int val = 0;
  node(int ll, int rr){
    l = ll, r = rr;
    if(l == r)val = l;
    else L = new node(l, l+r>>1), R = new node((l+r>>1)+1, r);
  }
  void down(){ L->val += val, R->val += val, val = 0; }
  void update(int ll, int rr, int x){
    if(ll <= l && rr >= r)val += x;
    else if(ll > r || rr < l || ll > rr)return;
    else L->update(ll, rr, x), R->update(ll, rr, x);
  }
  int query(int i){
    if(l == r && l == i)return val;
    else return down(), (i <= (l+r>>1)?L:R)->query(i);
  }
} *roots, *roote;
*/

order_statistics_tree<pii> reps;

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
  /*
  roots = new node(0, N-1), roote = new node(1, N);
  for(int i = 0; i < C; i++){
    rounds.pb({roots->query(S[i]), roote->query(E[i])});
    roots->update(S[i]+1, N, E[i]-S[i]);
    roote->update(S[i], N, E[i]-S[i]);
  }
  */
  for(int i = 0; i < N; i++)reps.insert({i, i});
  for(int i = 0; i < C; i++){
    auto b = reps.find_by_order(S[i]), e = reps.find_by_order(E[i]), ne = next(e);
    rounds.pb({b->ff, e->ss});
    for(auto i = b; i != ne; i=reps.erase(i));
    reps.insert(rounds.back());
  }
  lcnt.resize(N);
  for(int i = N-2; i >= 0; i--)
    lcnt[i] = K[i] < R ? 1+lcnt[i+1] : 0;
  oops.resize(N+1);
  for(auto& p: rounds)
    if(lcnt[p.ff] >= p.ss-p.ff)oops[p.ff]++, oops[p.ss+1]--;
  for(int i = 1; i <= N; i++)oops[i] += oops[i-1];
  //cout << rounds << endl << lcnt << endl << oops << endl;
  return max_element(all(oops))-oops.begin();
  //return 0;
}

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