Submission #1097808

#	Time	Username	Problem	Language	Result	Execution time	Memory
1097808		MtSaka	Jousting tournament (IOI12_tournament)	C++17	49 / 100	1072 ms	5724 KiB

tournament

#include"bits/stdc++.h"
#define overload(a,b,c,d,...) d
#define rep1(a) for(ll _=0;_<(ll)a;++_)
#define rep2(i,a) for(ll i=0;i<(ll)(a);++i)
#define rep3(i,a,b) for(ll i=(ll)(a);i<(ll)(b);++i)
#define rep(...) overload(__VA_ARGS__,rep3,rep2,rep1)(__VA_ARGS__)
#define rrep1(i,a) for(ll i=(ll)(a)-1;i>=0;--i)
#define rrep2(i,a,b) for(ll i=(ll)(b)-1;i>=(ll)(a);--i)
#define rrep(...) overload(__VA_ARGS__,rrep2,rrep1)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define pb push_back
#define eb emplace_back
using namespace std;
using ll=long long;
using ull=unsigned long long;
using i128=__int128_t;
using ld=long double;
using vi=vector<int>;
using vl=vector<ll>;
template<typename T,typename U>inline bool chmin(T&a,const U&b){return (a>b?a=b,true:false);}
template<typename T,typename U>inline bool chmax(T&a,const U&b){return (a<b?a=b,true:false);}

struct segtree{
    private:
    int sz;
    vector<int>seg;
    public:
    segtree(vector<int>&v):sz(v.size()){
        seg.resize(sz<<1);
        rep(i,sz)seg[sz+i]=v[i];
        rrep(i,sz)seg[i]=max(seg[i<<1],seg[i<<1|1]);
    }
    int prod(int l,int r)const{
        l+=sz,r+=sz;
        int ret=-1e9;
        for(;l<r;l>>=1,r>>=1){
            if(l&1)chmax(ret,seg[l++]);
            if(r&1)chmax(ret,seg[--r]);
        }
        return ret;
    }
};
int GetBestPosition(int n, int c, int R, int *k, int *s, int *e) {
    vector<int>rate(n-1);
    rep(i,n-1)rate[i]=k[i];
    segtree seg(rate);
    vector<array<ll,4>>intervals(n);
    rep(i,n)intervals[i]={i,i,0,i};
    rep(i,c){
        //rep(j,intervals.size()){
        //    cerr<<intervals[j][0]<<" "<<intervals[j][1]<<" "<<intervals[j][2]<<" "<<intervals[j][3]<<endl;
        //}
        //cerr<<endl;
        int l=intervals[s[i]][0],r=intervals[e[i]][1];
        int ma=seg.prod(l,r);
        int nxt=-1;
        int id=-1;
        rep(j,s[i],e[i]+1){
            if(chmax(nxt,intervals[j][2])){
                id=intervals[j][3];
            }
        }
        if(ma<R)nxt++;
        intervals.erase(intervals.begin()+s[i]+1,intervals.begin()+e[i]+1);
        intervals[s[i]]={l,r,nxt,id};
    }
    int ma=-1e9;
    int ans=-1;
    rep(j,intervals.size()){
        if(chmax(ma,intervals[j][2])){
            ans=intervals[j][3];
        }
    }
    return ans;
}

• Subtask 1: 17 / 17
• Subtask 2: 32 / 32
• Subtask 3: 0 / 51