oj.uz

Submission #439942

# Submission time Handle Problem Language Result Execution time Memory
439942 2021-07-01T09:02:47 Z prvocislo Jousting tournament (IOI12_tournament) C++17
100 / 100
 203 ms 15504 KB 
#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.0 / 17.0

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

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 9 ms 1100 KB Output is correct
3 Correct 4 ms 716 KB Output is correct
4 Correct 6 ms 996 KB Output is correct
5 Correct 8 ms 972 KB Output is correct
6 Correct 6 ms 844 KB Output is correct
7 Correct 6 ms 1100 KB Output is correct
8 Correct 6 ms 1100 KB Output is correct
9 Correct 4 ms 716 KB Output is correct
10 Correct 8 ms 1100 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 6988 KB Output is correct
2 Correct 182 ms 15424 KB Output is correct
3 Correct 115 ms 10112 KB Output is correct
4 Correct 178 ms 15440 KB Output is correct
5 Correct 172 ms 15168 KB Output is correct
6 Correct 203 ms 14844 KB Output is correct
7 Correct 181 ms 15504 KB Output is correct
8 Correct 187 ms 15404 KB Output is correct
9 Correct 91 ms 9844 KB Output is correct
10 Correct 119 ms 10208 KB Output is correct