oj.uz

Submission #287914

# Submission time Handle Problem Language Result Execution time Memory
287914 2020-09-01T06:35:31 Z erd1 Jousting tournament (IOI12_tournament) C++14
100 / 100
 190 ms 9972 KB 
#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.0 / 17.0

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

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 7 ms 768 KB Output is correct
3 Correct 4 ms 640 KB Output is correct
4 Correct 8 ms 768 KB Output is correct
5 Correct 6 ms 768 KB Output is correct
6 Correct 6 ms 768 KB Output is correct
7 Correct 6 ms 768 KB Output is correct
8 Correct 6 ms 768 KB Output is correct
9 Correct 3 ms 640 KB Output is correct
10 Correct 7 ms 896 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 4440 KB Output is correct
2 Correct 190 ms 9592 KB Output is correct
3 Correct 107 ms 7800 KB Output is correct
4 Correct 173 ms 9972 KB Output is correct
5 Correct 172 ms 9380 KB Output is correct
6 Correct 183 ms 9332 KB Output is correct
7 Correct 180 ms 9592 KB Output is correct
8 Correct 179 ms 9808 KB Output is correct
9 Correct 89 ms 7544 KB Output is correct
10 Correct 108 ms 7672 KB Output is correct