oj.uz

답안 #13013

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
13013 2015-01-24T18:28:00 Z dohyun0324 코알라 (JOI13_koala) C++
100 / 100
 275 ms 18728 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[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("%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,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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 14108 KB Output is correct
2 Correct 0 ms 14108 KB Output is correct
3 Correct 2 ms 14108 KB Output is correct
4 Correct 0 ms 14108 KB Output is correct
5 Correct 0 ms 14108 KB Output is correct
6 Correct 0 ms 14108 KB Output is correct
7 Correct 1 ms 14108 KB Output is correct
8 Correct 0 ms 14108 KB Output is correct
9 Correct 0 ms 14108 KB Output is correct
10 Correct 0 ms 14108 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 104 ms 14108 KB Output is correct
2 Correct 90 ms 14108 KB Output is correct
3 Correct 30 ms 14108 KB Output is correct
4 Correct 96 ms 14108 KB Output is correct
5 Correct 70 ms 14108 KB Output is correct
6 Correct 39 ms 14108 KB Output is correct
7 Correct 41 ms 14108 KB Output is correct

Subtask #3
50.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 261 ms 17012 KB Output is correct
2 Correct 275 ms 18464 KB Output is correct
3 Correct 239 ms 18728 KB Output is correct
4 Correct 203 ms 18728 KB Output is correct
5 Correct 159 ms 16748 KB Output is correct
6 Correct 119 ms 15956 KB Output is correct