Submission #439942

#	Time	Username	Problem	Language	Result	Execution time	Memory
439942		prvocislo	Jousting tournament (IOI12_tournament)	C++17	100 / 100	203 ms	15504 KiB

tournament

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<pair<int, int>, null_type,less<pair<int, int>>, rb_tree_tag,tree_order_statistics_node_update>

struct node
{
  int d, l, r, maxi, maxlast, i;
  node(int D = -1, int L = -1, int R = -1, int MAXI = -1, int MAXLAST = -1, int I = -1): d(D), l(L), r(R), maxi(MAXI), maxlast(MAXLAST), i(I) {}
};
void upd(node &a, const node &b)
{
  if (b.d > a.d || (a.d == b.d && b.i < a.i)) a.d = b.d, a.i = b.i;
}
int GetBestPosition(int n, int m, int nw, int *k, int *l, int *r) 
{
  ordered_set s;
  vector<node> v;
  for (int i = 0; i < n - 1; i++) v.push_back(node(0, i, i, k[i], 0, i)), s.insert({i, i});
  node best; best.i = 0;
  for (int i = 0; i < m; i++)
  {
    node now;
    int len = r[i] - l[i] + 1;
    for (int j = 0; j < len; j++)
    {
      auto it = s.find_by_order(l[i]);
      node nj = v[it->second];
      now.maxi = max(now.maxi, nj.maxi);
      if (j == 0) now.l = nj.l;
      if (j == len-1) now.r = nj.r, now.maxlast = max(now.maxlast, nj.maxlast);
      else now.maxlast = max(now.maxlast, nj.maxi);
      upd(now, nj);
      s.erase(it);
    }
    now.d++;
    if (now.maxlast < nw) 
      upd(best, now);
    v.push_back(now);
    s.insert({now.l, v.size() - 1});
  }
  return best.i;
}

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