oj.uz

Submission #649353

# Submission time Handle Problem Language Result Execution time Memory
649353 2022-10-10T04:24:03 Z PoonYaPat Jousting tournament (IOI12_tournament) C++14
100 / 100
 112 ms 13440 KB 
#include <bits/stdc++.h>
using namespace std;

int s[1<<18],n,cnt[100001];

void build(int l, int r, int idx, int *c) {
    if (l==r) s[idx]=c[l];
    else {
        int mid=(l+r)/2;
        build(l,mid,2*idx,c);
        build(mid+1,r,2*idx+1,c);
        s[idx]=max(s[2*idx],s[2*idx+1]);
    }
}

int query(int l, int r, int idx, int x, int y) {
    if (x>r || y<l) return 0;
    if (x<=l && r<=y) return s[idx];

    int mid=(l+r)/2;
    return max(query(l,mid,2*idx,x,y),query(mid+1,r,2*idx+1,x,y));
}

struct node {
    int prior,val,sz; //val is the max position contained in that node
    struct node *l,*r;
    node(int x) : prior(rand()), val(x), sz(1), l(NULL), r(NULL) {}
};
typedef node* pnode;

int get_sz(pnode t) {
    if (t==NULL) return 0;
    else return t->sz;
}

void upd(pnode t) {
    if (t) t->sz=get_sz(t->l)+get_sz(t->r)+1;
}

void split(pnode t, pnode &l, pnode &r, int k) {
    if (t==NULL) l=r=NULL;
    else if (get_sz(t->l)<k) split(t->r,t->r,r,k-get_sz(t->l)-1), l=t;
    else split(t->l,l,t->l,k), r=t;
    upd(t);
}

void merge(pnode &t, pnode l, pnode r) {
    if (l==NULL) t=r;
    else if (r==NULL) t=l;
    else if (l->prior > r->prior) merge(l->r,l->r,r), t=l;
    else merge(r->l,l,r->l), t=r;
    upd(t);
}

int find_max(pnode t) {
    if (t==NULL) return -1;
    while ((t->r)!=NULL) t=t->r;
    return t->val;
}

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
    n=N;
    build(0,n-2,1,K); //build segment

    pnode treap=0;
    for (int i=0; i<n; ++i) merge(treap,treap,new node(i)); //build treap

    for (int i=0; i<C; ++i) {
        //start at S[i], end at E[i]
        pnode A,B,C;
        split(treap,A,B,S[i]);
        split(B,B,C,E[i]-S[i]+1);
        int mmin=find_max(A)+1, mmax=find_max(B);
        if (query(0,n-2,1,mmin,mmax-1)<R) ++cnt[mmin], --cnt[mmax+1];
        merge(treap,A,new node(mmax));
        merge(treap,treap,C);
    }

    int sum_best=0,sum=0,ans=0;
    for (int i=0; i<=n-1; ++i) {
        sum+=cnt[i];
        if (sum>sum_best) {
            sum_best=sum;
            ans=i;
        }
    }
    return ans;
}

Subtask #1
17.0 / 17.0

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

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 5 ms 904 KB Output is correct
3 Correct 2 ms 576 KB Output is correct
4 Correct 5 ms 952 KB Output is correct
5 Correct 5 ms 832 KB Output is correct
6 Correct 4 ms 852 KB Output is correct
7 Correct 5 ms 960 KB Output is correct
8 Correct 7 ms 928 KB Output is correct
9 Correct 3 ms 596 KB Output is correct
10 Correct 6 ms 980 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 5896 KB Output is correct
2 Correct 110 ms 13424 KB Output is correct
3 Correct 27 ms 7324 KB Output is correct
4 Correct 111 ms 13440 KB Output is correct
5 Correct 110 ms 13008 KB Output is correct
6 Correct 111 ms 11352 KB Output is correct
7 Correct 111 ms 13432 KB Output is correct
8 Correct 112 ms 13352 KB Output is correct
9 Correct 21 ms 6996 KB Output is correct
10 Correct 32 ms 7628 KB Output is correct