Submission #13011

#	Time	Username	Problem	Language	Result	Execution time	Memory
13011		dohyun0324	코알라 (JOI13_koala)	C++98	0 / 100	265 ms	13108 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,d,a,n,mod[100010],t=1;
ll D[100010];
struct data{
    int 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[400010];
void query(int x,int y,int k,int s,int e,int p)
{
    if(tree[k].ch){
        if(tree[k].maxi==-2147483647) tree[k].maxi=0;
        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;
        }
        if(tree[k].maxi==-2147483647) tree[k].maxi=0;
        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("%d %d %d %d %d",&b[0].p,&m,&d,&a,&n);
    for(i=1;;i++){if(t>=n) break; t*=2;}
    for(i=1;i<=n;i++) scanf("%d %d",&b[i].p,&b[i].val);
    b[n+1].p=m;
    for(i=1;i<=t*2;i++) tree[i].maxi=-2147483647;
    for(i=0;i<=n+1;i++){arr[i].x=b[i].p%d; arr[i].y=i;}
    sort(arr,arr+n+2);
    for(i=0;i<=n+1;i++){
        if(arr[i].x!=arr[i+1].x){
            mod[++w]=arr[i].x;
            pos[arr[i].x]=w;
        }
    }
    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: 0 / 20
• Subtask 2: 0 / 30
• Subtask 3: 0 / 50