oj.uz

Submission #931362

# Submission time Handle Problem Language Result Execution time Memory
931362 2024-02-21T16:19:47 Z kim Jousting tournament (IOI12_tournament) C++17
49 / 100
 1000 ms 14344 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 lm[100005],rm[100005];

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

  vector<pii> opr(C);
  t.init(N);
  vector<int> L;
  for(int i=0;i<C;++i){
    auto [l,r]=t.qr(S[i]+1,E[i]+1);
    opr[i]={l,r};
    L.eb(l);
    // cerr<<l<<"-"<<r<<endl;
  }
  sort(opr.begin(),opr.end());
  sort(L.begin(),L.end());
  L.erase(unique(L.begin(),L.end()),L.end());

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

  int ans=0,mx=0;
  for(auto &i:L){
    int cnt=0;
    for(auto &[l,r]:opr){
      if(l>i||r<i||rm[l]<r) continue;
      ++cnt;
    }
    if(cnt>mx) mx=cnt,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 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 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 456 KB Output is correct
9 Correct 0 ms 392 KB Output is correct
10 Correct 1 ms 348 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 14 ms 1064 KB Output is correct
3 Correct 2 ms 600 KB Output is correct
4 Correct 12 ms 860 KB Output is correct
5 Correct 15 ms 860 KB Output is correct
6 Correct 7 ms 860 KB Output is correct
7 Correct 13 ms 860 KB Output is correct
8 Correct 13 ms 1064 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 13 ms 1076 KB Output is correct

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 457 ms 5468 KB Output is correct
2 Execution timed out 1031 ms 14344 KB Time limit exceeded
3 Halted 0 ms 0 KB -