読者です 読者をやめる 読者になる 読者になる

らての精進日記

修行をします

JOI2017本選

f:id:latte0119:20161222003033j:plain

aojに問題が上がった時のためにコードを保存しておきます


1問目

#include<bits/stdc++.h>
using namespace std;

#define int long long

typedef pair<int,int>pint;
typedef vector<int>vint;
typedef vector<pint>vpint;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
template<class T,class U>void chmin(T &t,U f){if(t>f)t=f;}
template<class T,class U>void chmax(T &t,U f){if(t<f)t=f;}

int N,Q,S,T;
int A[222222];
signed main(){
    scanf("%lld%lld%lld%lld",&N,&Q,&S,&T);
    rep(i,N+1)scanf("%lld",&A[i]);
    rep(i,N)A[i]=A[i+1]-A[i];

    int ans=0;
    rep(i,N){
        if(A[i]<0)ans+=A[i]*T;
        else ans+=A[i]*S;
    }


    rep(i,Q){
        int l,r,x;
        scanf("%lld%lld%lld",&l,&r,&x);
        l--;
        if(A[l]<0)ans-=A[l]*T;
        else ans-=A[l]*S;

        A[l]+=x;
        if(A[l]<0)ans+=A[l]*T;
        else ans+=A[l]*S;

        if(r!=N){
            if(A[r]<0)ans-=A[r]*T;
            else ans-=A[r]*S;

            A[r]-=x;
            if(A[r]<0)ans+=A[r]*T;
            else ans+=A[r]*S;
        }
        printf("%lld\n",-ans);

    }
    return 0;
}

2問目

#include<bits/stdc++.h>
using namespace std;

#define int long long

typedef pair<int,int>pint;
typedef vector<int>vint;
typedef vector<pint>vpint;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
template<class T,class U>void chmin(T &t,U f){if(t>f)t=f;}
template<class T,class U>void chmax(T &t,U f){if(t<f)t=f;}

int N,M,K;
int A,B,C,T;

int S[3333];

signed main(){
    scanf("%lld%lld%lld",&N,&M,&K);
    scanf("%lld%lld%lld%lld",&A,&B,&C,&T);
    rep(i,M)scanf("%lld",&S[i]),S[i]--;
    S[M]=S[M-1]+1;
    vint v;
    int ans=0;
    rep(i,M){
        if(i*B>T)break;
        int t=0;
        for(int j=0;j<=K;j++){
            if(t==S[i+1]-S[i]||S[i]*B+t*C>T)break;
            int s=min(S[i+1]-S[i]-t,(T-S[i]*B-t*C)/A+1);
            if(j==0)ans+=s;
            else v.pb(s);
            t+=s;
        }
    }
    sort(all(v));reverse(all(v));
    for(int i=0;i<v.size()&&i<K-M;i++)ans+=v[i];
    cout<<ans-1<<endl;
    return 0;
}

3問目
todo:二分探索しないで解く

#include<bits/stdc++.h>
using namespace std;

#define int long long

typedef pair<int,int>pint;
typedef vector<int>vint;
typedef vector<pint>vpint;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
template<class T,class U>void chmin(T &t,U f){if(t>f)t=f;}
template<class T,class U>void chmax(T &t,U f){if(t<f)t=f;}

int H,W;
int A[2222][2222];
int ma;

int idx[2222];

bool C(int d){
    int lim=ma-d;

    for(int i=0;i<H;i++){
        idx[i]=0;
        for(int j=0;j<W;j++){
            if(A[i][j]<lim)break;
            idx[i]++;
        }
        if(i)chmin(idx[i],idx[i-1]);
        int latte=-1;
        rep(j,W)if(A[i][j]==ma)latte=j+1;
        if(latte>idx[i])return false;
    }

    int l=INT_MAX,r=0;
    rep(i,H){
        for(int j=idx[i];j<W;j++){
            chmin(l,A[i][j]);
            chmax(r,A[i][j]);
        }
    }
    return r-l<=d;
}

int ans;

void solve(){
    int lb=-1,ub=1000000000;
    while(ub-lb>1){
        int mid=(ub+lb)/2;
        if(C(mid))ub=mid;
        else lb=mid;
    }
    chmin(ans,ub);
}

signed main(){
    scanf("%lld%lld",&H,&W);
    rep(i,H)rep(j,W)scanf("%lld",&A[i][j]),chmax(ma,A[i][j]);

    ans=INT_MAX;
    rep(i,2){
        rep(j,2){
            solve();
            rep(k,H)reverse(A[k],A[k]+W);
        }
        rep(l,W){
            for(int k=0;k<H/2;k++)swap(A[k][l],A[H-1-k][l]);
        }
    }
    cout<<ans<<endl;
    return 0;
}

4問目
todo:考察して

5問目
todo:seg木で甘えてる部分を線形(もしくはsortとかのlog)にする
これは罠で、seg木で通ればもうそれでいいや

#include<bits/stdc++.h>
using namespace std;

#define int long long

typedef pair<int,int>pint;
typedef vector<int>vint;
typedef vector<pint>vpint;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
template<class T,class U>void chmin(T &t,U f){if(t>f)t=f;}
template<class T,class U>void chmax(T &t,U f){if(t<f)t=f;}

struct segtree{
    static const int SEG=1<<20;
    vint dat;
    segtree():dat(SEG*2){}
    void update(int k,int x){
        k+=SEG-1;
        dat[k]=x;
        while(k){
            k=(k-1)/2;
            dat[k]=max(dat[k*2+1],dat[k*2+2]);
        }
    }
    int get(int a,int b,int k=0,int l=0,int r=SEG){
        if(r<=a||b<=l)return 0;
        if(a<=l&&r<=b)return dat[k];
        return max(get(a,b,k*2+1,l,(l+r)/2),get(a,b,k*2+2,(l+r)/2,r));
    }
};

int N,M;
int C[1111111];

int cnt[1111111];
int base[1111111];
vint G[1111111];

int ans[1111111];

signed main(){
    scanf("%lld%lld",&N,&M);
    rep(i,N)scanf("%lld",&C[i]),C[i]--;

    rep(i,N)cnt[C[i]]++;

    fill_n(ans,M,N);

    rep(lattemalta,2){
        rep(i,M)G[i].clear();
        memset(base,0,sizeof(base));
        segtree seg;
        rep(i,M)seg.update(i,cnt[i]);
        vint b;
        if(lattemalta==1)b.pb(C[0]);

        int cur=lattemalta;
        while(cur+1<N){
            if(C[cur]==C[cur+1]){
                base[C[cur]]+=2;
            }
            else{
                G[C[cur]].pb(C[cur+1]);
                G[C[cur+1]].pb(C[cur]);
            }
            cur+=2;
        }
        if(cur>N)b.pb(C[N-1]);

        rep(i,M){
            int a=N-cnt[i];
            int cost=G[i].size();

            for(auto t:G[i]){
                cnt[t]--;
                a--;
                seg.update(t,cnt[t]);
            }

            int tmp=0;
            if(i)tmp=seg.get(0,i);
            if(i+1!=M)chmax(tmp,seg.get(i+1,M));
            chmin(ans[i],cost+a-tmp);

            for(auto t:G[i]){
                cnt[t]++;
                seg.update(t,cnt[t]);
            }
        }
    }

    rep(i,M)printf("%lld\n",ans[i]);
    return 0;
}
広告を非表示にする