Submission #287900

#	Time	Username	Problem	Language	Result	Execution time	Memory
287900		erd1	Jousting tournament (IOI12_tournament)	C++14	0 / 100	61 ms	11644 KiB

tournament

#include<bits/stdc++.h>
using namespace std;
#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;

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(rounds.back().ff+1, N, E[i]-S[i]);
    roote->update(rounds.back().ff, N, E[i]-S[i]);
  }
  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];
  return max_element(all(oops))-oops.begin();
  //cout << rounds << endl << lcnt << endl;
  //return 0;
}

Compilation message (stderr)

tournament.cpp: In constructor 'node::node(int, int)':
tournament.cpp:38:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |     else L = new node(l, l+r>>1), R = new node((l+r>>1)+1, r);
      |                          ~^~
tournament.cpp:38:50: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |     else L = new node(l, l+r>>1), R = new node((l+r>>1)+1, r);
      |                                                 ~^~
tournament.cpp: In member function 'int node::query(int)':
tournament.cpp:48:33: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   48 |     else return down(), (i <= (l+r>>1)?L:R)->query(i);
      |                                ~^~

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