Submission #411287

#	Time	Username	Problem	Language	Result	Execution time	Memory
411287		AlperenT	Pinball (JOI14_pinball)	C++17	100 / 100	301 ms	11188 KiB

pinball

#include <bits/stdc++.h>

using namespace std;

const int M = 1e5 + 5, MMAX = 3e5 + 5;
const long long INF = 1e18 + 5;

int n, m, lft, rght, indx;
long long curans[M], leftans[M], rightans[M], ans;

struct Device{
    int l, r, c;
    long long p;
};

Device devices[M];

struct SegTree{
    int tree[MMAX * 4];

    void reset(){
        fill(tree, tree + MMAX, 0);
        fill(curans, curans + M, INF);
    }

    void update(int v, int l, int r, int pos, int val){
        if(l == r){
            if(curans[val] <= curans[tree[v]]) tree[v] = val;
        }
        else{
            int m = l + (r - l) / 2;
            if(pos <= m) update(v * 2, l, m, pos, val);
            else update(v * 2 + 1, m + 1, r, pos, val);

            if(curans[tree[v * 2]] <= curans[tree[v * 2 + 1]]) tree[v] = tree[v * 2];
            else tree[v] = tree[v * 2 + 1];
        }
    }

    int query(int v, int tl, int tr, int l, int r){
        if(l > r) return 0;
        else if(tl == l && tr == r) return tree[v];
        else{
            int tm = tl + (tr - tl) / 2;

            int a = query(v * 2, tl, tm, l, min(tm, r));
            int b = query(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r);

            if(curans[a] <= curans[b]) return a;
            else return b;
        }
    }
};

SegTree segtree;

void compress(){
    vector<int> nums;

    for(int i = 1; i <= m; i++) nums.push_back(devices[i].l), nums.push_back(devices[i].r), nums.push_back(devices[i].c);

    sort(nums.begin(), nums.end());
    nums.erase(unique(nums.begin(), nums.end()), nums.end());

    for(int i = 1; i <= m; i++){
        devices[i].l = lower_bound(nums.begin(), nums.end(), devices[i].l) - nums.begin() + 1;
        devices[i].r = lower_bound(nums.begin(), nums.end(), devices[i].r) - nums.begin() + 1;
        devices[i].c = lower_bound(nums.begin(), nums.end(), devices[i].c) - nums.begin() + 1;

        lft = min(lft, devices[i].l);
        rght = max(rght, devices[i].r);
    }
}

int main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    
    cin >> m >> n;

    for(int i = 1; i <= m; i++){
        cin >> devices[i].l >> devices[i].r >> devices[i].c >> devices[i].p;
        if(devices[i].l == 1) lft = n;
        if(devices[i].r == n) rght = 1;
    }

    if(lft == 0 || rght == 0){
        cout << -1;
        return 0;
    }

    lft = n, rght = 1;

    compress();

    devices[0] = {0, 0, 0, INF};

    segtree.reset();

    for(int i = 1; i <= m; i++){
        if(devices[i].l == lft){
            curans[i] = leftans[i] = devices[i].p;
            segtree.update(1, lft, rght, devices[i].c, i);
        }
        else{
            indx = segtree.query(1, lft, rght, devices[i].l, devices[i].r);
            if(indx != 0){
                curans[i] = leftans[i] = devices[i].p + leftans[indx];
                segtree.update(1, lft, rght, devices[i].c, i);
            }
            else{
                leftans[i] = INF;
            }
        }
    }

    segtree.reset();

    for(int i = 1; i <= m; i++){
        if(devices[i].r == rght){
            curans[i] = rightans[i] = devices[i].p;
            segtree.update(1, lft, rght, devices[i].c, i);
        }
        else{
            indx = segtree.query(1, lft, rght, devices[i].l, devices[i].r);
            if(indx != 0){
                curans[i] = rightans[i] = devices[i].p + rightans[indx];
                segtree.update(1, lft, rght, devices[i].c, i);
            }
            else{
                rightans[i] = INF;
            }
        }
    }

    ans = INF;

    for(int i = 1; i <= m; i++){
        ans = min(ans, leftans[i] + rightans[i] - devices[i].p);
    }

    cout << (ans != INF ? ans : -1);
}

• Subtask 1: 11 / 11
• Subtask 2: 18 / 18
• Subtask 3: 22 / 22
• Subtask 4: 49 / 49