Submission #117618

#	Time	Username	Problem	Language	Result	Execution time	Memory
117618		evpipis	Pinball (JOI14_pinball)	C++17	100 / 100	669 ms	151188 KiB

pinball

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int len = 1e5+5;
const ll inf = 1e18;
int lef[len], rig[len], pos[len], cost[len];
ll dp[len][3];

struct node{
    ll mn0, mn1;
    node *left, *right;

    node(ll m0 = inf, ll m1 = inf, node *l = NULL, node *r = NULL){
        mn0 = m0;
        mn1 = m1;
        left = l;
        right = r;
    }
};

typedef node* pnode;
pnode null = new node(), root = new node();

pnode upd(pnode t, int l, int r, int i, ll m0, ll m1){
    if (l == r)
        return new node(min(t->mn0, m0), min(t->mn1, m1), null, null);

    int mid = (l+r)/2;
    if (i <= mid)
        return new node(min(t->mn0, m0), min(t->mn1, m1), upd(t->left, l, mid, i, m0, m1), t->right);
    return new node(min(t->mn0, m0), min(t->mn1, m1), t->left, upd(t->right, mid+1, r, i, m0, m1));
}

node join(node a, node b){
    node c;
    c.mn0 = min(a.mn0, b.mn0);
    c.mn1 = min(a.mn1, b.mn1);
    return c;
}

node ask(pnode t, int l, int r, int i, int j){
    if (r < i || j < l)
        return node();
    if (i <= l && r <= j)
        return *t;

    int mid = (l+r)/2;
    return join(ask(t->left, l, mid, i, j), ask(t->right, mid+1, r, i, j));
}

int main(){
    int n, m;
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d %d %d %d", &lef[i], &rig[i], &pos[i], &cost[i]);

    null->left = null->right = root = null;
    ll ans = inf;
    for (int i = 1; i <= n; i++){
        ll d0 = ask(root, 1, m, lef[i], rig[i]).mn0+cost[i];
        ll d1 = ask(root, 1, m, lef[i], rig[i]).mn1+cost[i];

        if (lef[i] == 1 && rig[i] == m)
            d0 = d1 = cost[i];
        else if (lef[i] == 1)
            d0 = cost[i];
        else if (rig[i] == m)
            d1 = cost[i];

        ans = min(ans, d0+d1-cost[i]);
        root = upd(root, 1, m, pos[i], d0, d1);
        //printf("i = %d, d0 = %lld, d1 = %lld, d2 = %lld\n", i, d0, d1, d0+d1-cost[i]);
    }

    if (ans == inf)
        printf("-1\n");
    else
        printf("%lld", ans);
    return 0;
}

Compilation message (stderr)

pinball.cpp: In function 'int main()':
pinball.cpp:54:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~~
pinball.cpp:56:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d %d", &lef[i], &rig[i], &pos[i], &cost[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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