PCK 2013 予選

予選終わったけど去年の予選一人でやってみました。
今年よりも少し難易度高いかな〜と思った

1〜6真にやるだけなので省略

7

更新が一点にしか来ないから普通にsegtreeで数えてあげればイイ

#include <cstdio>
#include <algorithm>
using namespace std;
typedef pair<int,int> P;
#define INF 2000000000
#define fi first
#define sec second
const int SIZE = 1<<17;
int N,R,L;
struct segtree
{
    P seg[SIZE*2];
    void init()
    {
        for(int i=0;i<N;i++)
        {
            seg[i+SIZE-1].fi=0;
            seg[i+SIZE-1].sec=-i;
        }
    }
    void build()
    {
        for(int i=SIZE-2;i>=0;i--)seg[i]=max(seg[i*2+1],seg[i*2+2]);
    }
    void update(int k,int x)
    {
        k+=SIZE-1;
        seg[k].fi+=x;
        while(k>0)
        {
            k=(k-1)/2;
            seg[k]=max(seg[k*2+1],seg[k*2+2]);
        }
    }
    P query(int a,int b,int k,int l,int r)
    {
        if(r<=a||b<=l)return P(-INF,INF);
        else if(a<=l&&r<=b)return seg[k];
        else return max(query(a,b,k*2+1,l,(l+r)/2),query(a,b,k*2+2,(l+r)/2,r));
    }
    P query()
    {
        return query(0,N,0,0,SIZE);
    }
};
segtree seg;
int total[100100];
int d[1000100],t[1000100],x[1000100];
int main()
{
    scanf("%d %d %d",&N,&R,&L);
    for(int i=0;i<R;i++)
    {
        scanf("%d %d %d",&d[i],&t[i],&x[i]);
        d[i]--;
    }
    t[R]=L;
    seg.init();
    seg.build();
    total[-((seg.query()).sec)]+=t[0];
    for(int i=0;i<R;i++)
    {
        seg.update(d[i],x[i]);
        total[-((seg.query()).sec)]+=t[i+1]-t[i];
    }
    int ansv=-1,ans;
    for(int i=0;i<N;i++)if(ansv<total[i])
    {
        ansv=total[i];
        ans=i;
    }
    printf("%d\n",ans+1);
    return 0;
}

8

にぶたんでグループに入れる人を数えるだけ

#include <cstdio>
#include <string>
#include <algorithm>
#include <vector>
#include <iostream>
#include <set>
using namespace std;
typedef pair<int,int> P;
#define pb push_back
#define INF 1000001000
#define fi first
#define sec second
int id[1000100];
int s[1000100];
vector<P> vec;
int Max_s=-INF;
int maxcount=0;
set<int> S;
int N,Q,X;
bool C(int r)
{
    int cur=-1;
    int cnt=0;
    set<int>::iterator it;
    for(it=S.begin();it!=S.end();it++)
    {
        int a = max((s[*it]-r),cur+1);
        int b = s[*it];
        if(a>b)continue;
        cnt+=upper_bound(s,s+N,b)-lower_bound(s,s+N,a);
        cur=max(cur,s[*it]);
    }
    return (N-cnt)<=X;
}
int main()
{
    scanf("%d %d",&N,&Q);
    for(int i=0;i<N;i++)
    {
        scanf("%d",&s[i]);
        vec.pb(P(s[i],i));
        Max_s=max(Max_s,s[i]);
    }
    sort(s,s+N);
    sort(vec.begin(),vec.end());
    for(int i=0;i<N;i++)id[vec[i].sec]=i;
    string type;
    int a;
    for(int i=0;i<Q;i++)
    {
        cin >> type;
        if(type=="ADD")
        {
            scanf("%d",&a);
            a--;
            S.insert(id[a]);
            //cout << s[id[a]] << endl;
            if(s[id[a]]==Max_s)maxcount++;
        }
        else if(type=="REMOVE")
        {
            scanf("%d",&a);
            a--;
            S.erase(id[a]);
            if(s[id[a]]==Max_s)maxcount--;
        }
        else
        {
            scanf("%d",&X);
            int l=-1,r=INF;
            while(r-l>1)
            {
                int mid=(l+r)/2;
                if(C(mid))r=mid;
                else l=mid;
            }
            if(r==INF)printf("NA\n");
            else printf("%d\n",r);
        }
    }
    return 0;
}

9

時間内に解けなかった、Ruinsっぽい、解いたら載せます