oj.uz

Submission #13685

# Submission time Handle Problem Language Result Execution time Memory
13685 2015-02-27T14:22:27 Z gs14004 Pinball (JOI14_pinball) C++14
100 / 100
 236 ms 24200 KB 
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long lint;

struct sti{int s,e,d,x;}a[100005];

vector<int> v;
lint dpl[100005], dpu[100005];

struct rmq{
    lint tree[1050000];
    int lim;
    void init(int n){
        memset(tree,0x3f,sizeof(tree));
        for(lim = 1; lim <= n; lim <<= 1);
    }
    void add(int x, lint v){
        x += lim;
        tree[x] = min(tree[x],v);
        while(x > 1){
            x >>= 1;
            tree[x] = min(tree[2*x],tree[2*x+1]);
        }
    }
    lint query(int s, int e){
        s += lim;
        e += lim;
        lint r = 1e18;
        while(s < e){
            if(s%2 == 1) r = min(r,tree[s++]);
            if(e%2 == 0) r = min(r,tree[e--]);
            s >>= 1;
            e >>= 1;
        }
        if(s == e) r = min(r,tree[s]);
        return r;
    }
}rmq;

struct seg{
    lint tree[1050000];
    void init(){
        memset(tree,0x3f,sizeof(tree));
    }
    void lazydown(int p){
        tree[2*p] = min(tree[p],tree[2*p]);
        tree[2*p+1] = min(tree[p],tree[2*p+1]);
    }
    void add(int s, int e, lint x, int ps, int pe, int p){
        if(e < ps || pe < s) return;
        if(s <= ps && pe <= e){
            tree[p] = min(tree[p],x);
            return;
        }
        lazydown(p);
        int pm = (ps+pe)/2;
        add(s,e,x,ps,pm,2*p);
        add(s,e,x,pm+1,pe,2*p+1);
    }
    lint q(int x, int ps, int pe, int p){
        if(ps == pe) return tree[p];
        lazydown(p);
        int pm = (ps+pe)/2;
        if(x <= pm) return q(x,ps,pm,2*p);
        return q(x,pm+1,pe,2*p+1);
    }
}seg;

int n,m;

void input(){
    scanf("%d %d",&n,&m);
    v.push_back(1);
    v.push_back(m);
    for (int i=2; i<=n+1; i++) {
        scanf("%d %d %d %d",&a[i].s,&a[i].e,&a[i].d,&a[i].x);
        v.push_back(a[i].s);
        v.push_back(a[i].e);
        v.push_back(a[i].d);
    }
    sort(v.begin(),v.end());
    v.resize(unique(v.begin(),v.end()) - v.begin());
    for (int i=2; i<=n+1; i++) {
        a[i].s = (int)(lower_bound(v.begin(),v.end(),a[i].s) - v.begin());
        a[i].e = (int)(lower_bound(v.begin(),v.end(),a[i].e) - v.begin());
        a[i].d = (int)(lower_bound(v.begin(),v.end(),a[i].d) - v.begin());
    }
    a[1] = {0,0,0,0};
    a[0] = {(int)v.size()-1,(int)v.size()-1,(int)v.size()-1,0};
}

int main(){
    input();
    rmq.init((int)v.size());
    seg.init();
    rmq.add(a[0].d,0);
    for (int i=1; i<n+2; i++) {
        dpu[i] = rmq.query(0,a[i].e) + a[i].x;
        rmq.add(a[i].d,dpu[i]);
    }
    for (int i=n+1; i; i--) {
        dpl[i] = seg.q(a[i].d,0,(int)v.size()-1,1) + a[i].x;
        dpl[i] = min(dpl[i],dpu[i]);
        seg.add(a[i].s,a[i].e,dpl[i],0,(int)v.size()-1,1);
    }
    if(dpl[1] >= 1e17) puts("-1");
    else printf("%lld",dpl[1]);
}

Subtask #1
11.0 / 11.0

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

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 21124 KB Output is correct
2 Correct 0 ms 21124 KB Output is correct
3 Correct 0 ms 21124 KB Output is correct
4 Correct 0 ms 21124 KB Output is correct
5 Correct 0 ms 21124 KB Output is correct
6 Correct 4 ms 21124 KB Output is correct

Subtask #3
22.0 / 22.0

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

Subtask #4
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 21256 KB Output is correct
2 Correct 61 ms 21896 KB Output is correct
3 Correct 154 ms 22664 KB Output is correct
4 Correct 165 ms 24200 KB Output is correct
5 Correct 113 ms 22664 KB Output is correct
6 Correct 217 ms 24200 KB Output is correct
7 Correct 223 ms 24200 KB Output is correct
8 Correct 210 ms 24200 KB Output is correct
9 Correct 40 ms 21512 KB Output is correct
10 Correct 112 ms 22664 KB Output is correct
11 Correct 178 ms 24200 KB Output is correct
12 Correct 232 ms 24200 KB Output is correct
13 Correct 236 ms 24200 KB Output is correct
14 Correct 226 ms 24200 KB Output is correct