oj.uz

Submission #13012

# Submission time Handle Problem Language Result Execution time Memory
13012 2015-01-24T18:20:43 Z dohyun0324 코알라 (JOI13_koala) C++
0 / 100
 266 ms 15340 KB 
#include<stdio.h>
#include<map>
#include<algorithm>
typedef long long ll;
using namespace std;
map<int,int>pos;
int sw,w,k,m,n,mod[100010],t=1;
ll d,a,M=-214748364700000000LL;
ll 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[400010];
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("%d %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){
            mod[++w]=arr[i].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,1,1,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
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10984 KB Output is correct
2 Correct 2 ms 10984 KB Output is correct
3 Incorrect 0 ms 10984 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 10984 KB Output is correct
2 Correct 100 ms 10984 KB Output is correct
3 Correct 38 ms 10984 KB Output is correct
4 Incorrect 95 ms 10984 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 255 ms 13888 KB Output is correct
2 Incorrect 266 ms 15340 KB Output isn't correct
3 Halted 0 ms 0 KB -