Submission #13014

#	Time	Username	Problem	Language	Result	Execution time	Memory
13014		dohyun0324	코알라 (JOI13_koala)	C++98	100 / 100	258 ms	18340 KiB

koala

#include<stdio.h>
#include<map>
#include<algorithm>
typedef long long ll;
using namespace std;
map<int,int>pos;
int sw,w,k,m,n,t=1;
ll d,a,M=-214748364700000000LL,D[100010];
struct data{
    ll p,val;
}b[100010];
struct data2{
    int x,y;
    bool operator<(const data2&r)const{
        return x<r.x;
    }
}arr[100010];
struct data3{
    ll maxi,ch;
}tree[600010];
void query(int x,int y,int k,int s,int e,ll p)
{
    if(tree[k].ch){
        tree[k].maxi+=tree[k].ch;
        tree[k*2].ch=tree[k*2+1].ch+=tree[k].ch;
        tree[k].ch=0;
    }
    if(s<=x && y<=e){
        if(sw){
            tree[k].maxi=p;
            return;
        }
        tree[k].maxi+=p;
        tree[k*2].ch=tree[k*2+1].ch+=p;
        return;
    }
    if(s>y || e<x) return;
    query(x,(x+y)/2,k*2,s,e,p);
    query((x+y)/2+1,y,k*2+1,s,e,p);
    tree[k].maxi=max(tree[k*2].maxi,tree[k*2+1].maxi);
}
int main()
{
    int i,s,e;
    scanf("%lld %d %lld %lld %d",&b[0].p,&m,&d,&a,&n);
    for(i=1;i<=n;i++) scanf("%lld %lld",&b[i].p,&b[i].val);
    b[n+1].p=m;
    for(i=0;i<=n+1;i++){arr[i].x=b[i].p%d; arr[i].y=i;}
    sort(arr,arr+n+2);
    arr[n+2].x=-1;
    for(i=0;i<=n+1;i++){
        if(arr[i].x!=arr[i+1].x) pos[arr[i].x]=++w;
    }
    for(i=1;;i++){if(t>=w) break; t*=2;}
    for(i=1;i<=t*2;i++) tree[i].maxi=M;
    sw=1; query(1,t,1,pos[b[0].p%d],pos[b[0].p%d],0); sw=0;
    for(i=1;i<=n+1;i++)
    {
        s=pos[b[i-1].p%d]; e=pos[b[i].p%d]-1;
        query(1,t,1,1,w,-((b[i].p-b[i-1].p-1)/d)*a);
        if(e<s)
        {
            query(1,t,1,s,w,-a);
            if(e) query(1,t,1,1,e,-a);
        }
        else query(1,t,1,s,e,-a);
        D[i]=tree[1].maxi+b[i].val;
        sw=1; query(1,t,1,e+1,e+1,D[i]); sw=0;
    }
    printf("%lld",D[n+1]);
    return 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 30 / 30
• Subtask 3: 50 / 50