Submission #1097832

#	Time	Username	Problem	Language	Result	Execution time	Memory
1097832		MtSaka	Jousting tournament (IOI12_tournament)	C++17	100 / 100	25 ms	7172 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(const vector<int>&v):sz(1){
        while(sz<(int)v.size())sz<<=1;
        seg.resize(sz<<1,0);
        rep(i,sz)seg[sz+i]=v[i];
        rrep(i,sz)seg[i]=seg[i<<1]+seg[i<<1|1];
    }
    int get_kth(int k)const{
        int id=1;
        while(id<sz){
            id<<=1;
            if(seg[id]<k)k-=seg[id++];
        }
        return id-sz;
    }
    void add(int k,int val){
        k+=sz;
        seg[k]+=val;
        while(k>>=1){
            seg[k]+=val;
        }
    }
};
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(vector<int>(n,1));
    vl nxt(n);
    rep(i,n)nxt[i]=i+1;
    vector<pair<int,int>>query(c);
    rep(i,c){
        query[i].first=seg.get_kth(s[i]+1);
        int now=nxt[query[i].first];
        rep(j,e[i]-s[i]){
            seg.add(now,-1);
            now=nxt[now];
        }
        query[i].second=now-1;
        nxt[query[i].first]=now;
    }
    vector<int>sum(n);
    rep(i,1,n)sum[i]=sum[i-1]+(k[i-1]>R);
    vl a(n+1);
    rep(i,c){
        if(sum[query[i].first]==sum[query[i].second]){
            a[query[i].first]++;
            a[query[i].second]--;
        }
    }
    int nows=0;
    int ma=-1e9,id=-1;
    rep(i,n){
        nows+=a[i];
        if(chmax(ma,nows))id=i;
    }
    //cerr<<ma<<endl;
    return id;
}

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