oj.uz

Submission #13014

# Submission time Handle Problem Language Result Execution time Memory
13014 2015-01-25T01:14:42 Z dohyun0324 코알라 (JOI13_koala) C++
100 / 100
 258 ms 18340 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,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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 13720 KB Output is correct
2 Correct 0 ms 13720 KB Output is correct
3 Correct 0 ms 13720 KB Output is correct
4 Correct 1 ms 13720 KB Output is correct
5 Correct 0 ms 13720 KB Output is correct
6 Correct 0 ms 13720 KB Output is correct
7 Correct 0 ms 13720 KB Output is correct
8 Correct 0 ms 13720 KB Output is correct
9 Correct 2 ms 13720 KB Output is correct
10 Correct 2 ms 13720 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 13720 KB Output is correct
2 Correct 99 ms 13720 KB Output is correct
3 Correct 25 ms 13720 KB Output is correct
4 Correct 80 ms 13720 KB Output is correct
5 Correct 59 ms 13720 KB Output is correct
6 Correct 37 ms 13720 KB Output is correct
7 Correct 30 ms 13720 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 258 ms 16624 KB Output is correct
2 Correct 251 ms 18076 KB Output is correct
3 Correct 235 ms 18340 KB Output is correct
4 Correct 215 ms 18340 KB Output is correct
5 Correct 160 ms 16360 KB Output is correct
6 Correct 122 ms 15568 KB Output is correct