oj.uz

Submission #931363

# Submission time Handle Problem Language Result Execution time Memory
931363 2024-02-21T16:25:45 Z kim Jousting tournament (IOI12_tournament) C++17
100 / 100
 75 ms 13156 KB 
#include<bits/stdc++.h>
using namespace std;
using pii=pair<int,int>;
#define eb emplace_back
using ll=long long;
#define f first
#define s second

mt19937 rng(time(nullptr));

struct info{
  int vL,vR,mn,mx;
  info():vL(1e9),vR(-1),mn(1e9),mx(-1){}
  info(int vL,int vR):vL(vL),vR(vR),mn(vL),mx(vR){}
};
struct treap{
  struct node{
    int sz,prio;
    info val;
    node *l,*r;
    node(info val):sz(1),val(val),prio(rng()),l(nullptr),r(nullptr){}
  };
  using pnode=node*;
  pnode rt;
  int sz(pnode t){return t?t->sz:0;}
  info val(pnode t){return t?t->val:info();}
  void upd(pnode t){
    if(!t) return;
    t->sz=sz(t->l)+1+sz(t->r);
    t->val.mn=min(val(t->l).mn,t->val.vL);
    t->val.mx=max(val(t->r).mx,t->val.vR);
  }
  void split(pnode t,pnode &l,pnode &r,int x){
    if(!t) return void(l=r=nullptr);
    if(sz(t->l)>=x) split(t->l,l,t->l,x),r=t;
    else split(t->r,t->r,r,x-sz(t->l)-1),l=t;
    upd(t);
  }
  void merge(pnode &t,pnode l,pnode r){
    if(!l||!r) return void(t=l?l:r);
    if(l->prio>r->prio) merge(l->r,l->r,r),t=l;
    else merge(r->l,l,r->l),t=r;
    upd(t);
  }
  void init(int n){
    rt=nullptr;
    for(int i=0;i<n;++i) merge(rt,rt,new node(info(i,i)));
  }
  pii qr(int l,int r){
    pnode t1,t2,t3;
    split(rt,t1,t2,l-1);
    split(t2,t2,t3,r-l+1);
    pii ret(val(t2).mn,val(t2).mx);
    merge(rt,t1,new node(info(ret.f,ret.s)));
    merge(rt,rt,t3);
    return ret;
  }
}t;

int rm[100005],qs[100005];

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {

  for(int i=N-2,cur=N+1;i>=0;--i){
    if(K[i]>R) cur=i;
    rm[i]=cur;
  }

  t.init(N);

  for(int i=0;i<C;++i){
    auto [l,r]=t.qr(S[i]+1,E[i]+1);
    if(rm[l]<r) continue;
    ++qs[l],--qs[r+1];
    // cerr<<l<<"-"<<r<<endl;
  }
  int ans=0,mx=qs[0];
  for(int i=1;i<N;++i){
    qs[i]+=qs[i-1];
    if(qs[i]>mx) mx=qs[i],ans=i;
  }
  return ans;

}

Compilation message

tournament.cpp: In constructor 'treap::node::node(info)':
tournament.cpp:19:10: warning: 'treap::node::val' will be initialized after [-Wreorder]
   19 |     info val;
      |          ^~~
tournament.cpp:18:12: warning:   'int treap::node::prio' [-Wreorder]
   18 |     int sz,prio;
      |            ^~~~
tournament.cpp:21:5: warning:   when initialized here [-Wreorder]
   21 |     node(info val):sz(1),val(val),prio(rng()),l(nullptr),r(nullptr){}
      |     ^~~~

Subtask #1
17.0 / 17.0

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

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 4 ms 860 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 3 ms 860 KB Output is correct
5 Correct 3 ms 880 KB Output is correct
6 Correct 3 ms 860 KB Output is correct
7 Correct 3 ms 860 KB Output is correct
8 Correct 3 ms 872 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 4 ms 860 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 4940 KB Output is correct
2 Correct 70 ms 11348 KB Output is correct
3 Correct 21 ms 7260 KB Output is correct
4 Correct 67 ms 13068 KB Output is correct
5 Correct 75 ms 12612 KB Output is correct
6 Correct 62 ms 10892 KB Output is correct
7 Correct 69 ms 13112 KB Output is correct
8 Correct 68 ms 13156 KB Output is correct
9 Correct 18 ms 7000 KB Output is correct
10 Correct 20 ms 7060 KB Output is correct