oj.uz

Submission #966123

# Submission time Handle Problem Language Result Execution time Memory
966123 2024-04-19T12:07:35 Z hirayuu_oj Jousting tournament (IOI12_tournament) C++17
49 / 100
 1000 ms 7500 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,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;
        assert(seg.prod(lf,ri).first==e-s);
        assert(seg2.prod(lf,ri).first==e-s);
        //seg.set(lf,add(seg.get(lf),{-e+s+1,0}));
        //seg2.set(lf+1,add(seg2.get(lf+1),{-e+s+1,0}));
        for(int j=lf; j<ri; j++){
            seg.set(j,{0,0});
            seg2.set(j,{0,0});
        }
        seg.set(ri-1,{1,1});
        seg2.set(lf,{1,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 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 5 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 3 ms 348 KB Output is correct
8 Correct 3 ms 464 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 604 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 602 ms 604 KB Output is correct
3 Correct 3 ms 604 KB Output is correct
4 Correct 142 ms 748 KB Output is correct
5 Correct 290 ms 852 KB Output is correct
6 Correct 9 ms 604 KB Output is correct
7 Correct 428 ms 752 KB Output is correct
8 Correct 232 ms 740 KB Output is correct
9 Correct 2 ms 604 KB Output is correct
10 Correct 14 ms 600 KB Output is correct

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 3040 KB Output is correct
2 Execution timed out 1074 ms 7500 KB Time limit exceeded
3 Halted 0 ms 0 KB -