oj.uz

Submission #966130

# Submission time Handle Problem Language Result Execution time Memory
966130 2024-04-19T12:14:02 Z hirayuu_oj Jousting tournament (IOI12_tournament) C++17
100 / 100
 192 ms 7768 KB 
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define all(x) x.begin(),x.end()
using ll=long long;

template<class S,auto op,auto e>
struct SegmentTree{
    int size;
    vector<S> tree;
    SegmentTree(int sz){
        size=sz;
        tree.resize(size*2);
        rep(i,size*2)tree[i]=e();
    }
    void set(int pos,S val){
        pos+=size;
        tree[pos]=val;
        pos/=2;
        while(pos>0){
            tree[pos]=op(tree[pos*2],tree[pos*2+1]);
            pos/=2;
        }
    }
    S get(int pos){
        return tree[pos+size];
    }
    S prod(int lf,int ri){
        lf+=size;
        ri+=size;
        S ret_lf=e();
        S ret_ri=e();
        while(lf<ri){
            if(lf%2==1){
                ret_lf=op(ret_lf,tree[lf]);
                lf++;
            }
            if(ri%2==1){
                ri--;
                ret_ri=op(tree[ri],ret_ri);
            }
            lf/=2;
            ri/=2;
        }
        return op(ret_lf,ret_ri);
    }
};

using T=pair<int,int>;
T op(T x,T y){
    return {x.first+y.first,max(x.second,x.first+y.second)};
}
T e(){
    return {0,0};
}
T add(T x,T y){
    return {x.first+y.first,max(0,x.second+y.second)};
}
int ma(int x,int y){
    return max(x,y);
}
int me(){
    return -1;
}

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
    SegmentTree<T, op, e> seg(N),seg2(N);
    SegmentTree<int, ma, me> night(N-1);
    rep(i,N){
        seg.set(i,{1,1});
        seg2.set(i,{1,1});
    }
    rep(i,N-1){
        night.set(i,K[i]);
    }
    vector<int> ans(N+1,0);
    rep(i,C){
        int s=S[i],e=E[i]+1;
        int ok=N,ng=-1;
        while(ok-ng>1){
            int mid=(ok+ng)/2;
            if(seg2.prod(0,mid).second>s){
                ok=mid;
            }
            else{
                ng=mid;
            }
        }
        int lf=ok-1;
        ok=N;
        ng=-1;
        while(ok-ng>1){
            int mid=(ok+ng)/2;
            if(seg.prod(0,mid).second>e-1){
                ok=mid;
            }
            else{
                ng=mid;
            }
        }
        int ri=ok;
        seg.set(lf,add(seg.get(lf),{-e+s+1,-e+s+1}));
        seg2.set(lf+1,add(seg2.get(lf+1),{-e+s+1,-e+s+1}));
        if(night.prod(lf,ri-1)<R){
            ans[lf]++;
            ans[ri]--;
        }
    }
    int fin=ans[0];
    int pos=0;
    rep(i,N-1){
        ans[i+1]+=ans[i];
        if(fin<ans[i+1]){
            fin=ans[i+1];
            pos=i+1;
        }
    }

    return pos;

}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 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 344 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 1 ms 344 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 6 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 6 ms 712 KB Output is correct
5 Correct 6 ms 604 KB Output is correct
6 Correct 6 ms 604 KB Output is correct
7 Correct 8 ms 604 KB Output is correct
8 Correct 6 ms 604 KB Output is correct
9 Correct 1 ms 600 KB Output is correct
10 Correct 8 ms 604 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 2908 KB Output is correct
2 Correct 187 ms 5880 KB Output is correct
3 Correct 33 ms 5812 KB Output is correct
4 Correct 192 ms 7768 KB Output is correct
5 Correct 185 ms 7248 KB Output is correct
6 Correct 173 ms 6740 KB Output is correct
7 Correct 188 ms 7408 KB Output is correct
8 Correct 190 ms 7460 KB Output is correct
9 Correct 22 ms 5724 KB Output is correct
10 Correct 36 ms 5764 KB Output is correct