PCK2013予選 G プログラミングコンテスト

問題概要

Nチームがコンテストをする.R回の得点変動(負の変動もありうる)が与えられるので,1位になってる時間が一番長いチームを求めよ.

解法

普通のセグ木で殴ればいいだけだが,ライブラリをまともに作ってなかったためバチャ中に通せなかった.
しっかり整備したので殴る.この問題は絶対落とせない…
「得点最大のなかでもっとも左のもの」は,セグ木のモノイドをpairにしてsecondに要素番号を持っておき,各クエリではsecondをみることで求められる.

ソースコード

#include<bits/stdc++.h>
using namespace std;
template<typename Monoid>
struct SegTree{
    //0-indexed
    using F=function<Monoid(Monoid,Monoid)>;
    int size;       //要素数
    vector<Monoid> dat;
    const F func;   //二項演算
    const Monoid Mdef;  //初期値
    SegTree(int sz,const F func,const Monoid &Mdef):func(func),Mdef(Mdef)
    {
        size=1;
        while(size<sz){
            size*=2;
        }
        dat.assign(size*2,Mdef);
    }
    void set(int k,const Monoid&x){
        //k番目の要素をxで初期化
        //あとでbuildが必要
        dat[k+size-1]=x;
    }
    void build(){
        //構築 O(N)
        for(int k=size-2;k>=0;k--){
            dat[k]=func(dat[k*2+1],dat[k*2+2]);
        }
    }
    void update(int k,const Monoid& x){
        //k番目の要素をxに変更 O(log N)
        int now=k+size-1;
        dat[now]=x;
        while(now){
            now=(now-1)/2;
            dat[now]=func(dat[now*2+1],dat[now*2+2]);
        }
    }
    Monoid _query(int a,int b,int k,int l,int r){
        if(r<a||b<l){
            return Mdef;
        }
        if(a<=l&&b>=r){
            return dat[k];
        }
        Monoid vl=_query(a,b,k*2+1,l,(l+r)/2);
        Monoid vr=_query(a,b,k*2+2,(l+r)/2+1,r);
        return func(vl,vr);
    }
    Monoid query(int l,int r){
        //[l,r]に対する演算funcの結果を返す O(log N)
        return _query(l,r,0,0,size-1);
    }
    Monoid operator[](const int &k)const{
        return dat[k+size-1];
    }
};
#define ll long long
#define FOR(i,n,m) for(int i=(n);i<(m);i++)
#define REP(i,n) FOR(i,0,n)
#define REPR(i,n) for(int i=(n);i>=0;i--)
#define all(vec) vec.begin(),vec.end()
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using P=pair<int,int>;
using PP=pair<int,P>;
using vp=vector<P>;
using vpp=vector<PP>;
using vs=vector<string>;
#define fi first
#define se second
#define pb push_back
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>bool chmin(T &a,const T &b){if(a>b){a=b;return true;}return false;}
const ll MOD=1000000007LL;
const int INF=1<<30;
const ll LINF=1LL<<60;
int main(){
    int n,m,r;
    cin>>n>>m>>r;
    SegTree<P> tree(n,[](P a,P b){
        if(a.fi==b.fi){
            return a.se<b.se?a:b;
        }
        return max(a,b);
    },P(0,0));
    REP(i,n){
        tree.set(i,P(0,i));
    }
    tree.build();
    int now=0;
    vi ans(n);
    REP(i,m){
        int a,b,c;
        cin>>a>>b>>c;
        a--;
        int ma=tree.query(0,n-1).se;
        ans[ma]+=b-now;
        now=b;
        auto t=tree[a];
        t.fi+=c;
        tree.update(a,t);
    }
    ans[tree.query(0,n-1).se]+=r-now;
    int x=0;
    REP(i,n){
        if(ans[i]>ans[x]){
            x=i;
        }
    }
    cout<<x+1<<endl;
    return 0;
}