Submission #390836

#	Time	Username	Problem	Language	Result	Execution time	Memory
390836		Joshc	Pinball (JOI14_pinball)	C++11	100 / 100	598 ms	48176 KiB

pinball

#include <cstdio>
#include <algorithm>
#include <set>
#include <unordered_map>
using namespace std;

#define ll long long
const ll INF = 1000000000000000000;
const int MAX_M = 100001;

int a[MAX_M], b[MAX_M], c[MAX_M], d[MAX_M];
ll dp[MAX_M], dp2[MAX_M], best[4*MAX_M], seg[13*MAX_M];

void update(int v, int tl, int tr, int pos, ll x) {
    if (tl == tr) seg[v] = x;
    else {
        int tm = (tl+tr) >> 1;
        if (pos <= tm) update(v<<1, tl, tm, pos, x);
        else update(v<<1|1, tm+1, tr, pos, x);
        seg[v] = min(seg[v<<1], seg[v<<1|1]);
    }
}

ll query(int v, int tl, int tr, int l, int r) {
    if (l > r) return INF;
    if (l == tl && r == tr) return seg[v];
    int tm = (tl+tr) >> 1;
    return min(query(v<<1, tl, tm, l, min(r, tm)), query(v<<1|1, tm+1, tr, max(l, tm+1), r));
}

int main() {
    int m, n, cur=0;
    scanf("%d%d", &m, &n);
    set<int> s = {1, n};
    unordered_map<int, int> z;
    for (int i=1; i<=m; i++) {
        scanf("%d%d%d%d", &a[i], &b[i], &c[i], &d[i]);
        s.insert(a[i]), s.insert(b[i]), s.insert(c[i]);
    }
    for (int i : s) z[i] = ++cur;
    for (int i=1; i<=m; i++) a[i] = z[a[i]], b[i] = z[b[i]], c[i] = z[c[i]];
    fill(&seg[0], &seg[13*MAX_M], INF);
    fill(&best[0], &best[4*MAX_M], INF);
    for (int i=1; i<=m; i++) update(1, 1, cur, c[i], best[c[i]] = min(best[c[i]], dp[i] = d[i] + (a[i]==1 ? 0 : query(1, 1, cur, a[i], b[i]))));
    fill(&seg[0], &seg[13*MAX_M], INF);
    fill(&best[0], &best[4*MAX_M], INF);
    for (int i=1; i<=m; i++) update(1, 1, cur, c[i], best[c[i]] = min(best[c[i]], dp2[i] = d[i] + (b[i]==cur ? 0 : query(1, 1, cur, a[i], b[i]))));
    ll ans = INF;
    for (int i=1; i<=m; i++) ans = min(ans, dp[i]+dp2[i]-d[i]);
    printf("%lld\n", ans == INF ? -1 : ans);
}

Compilation message (stderr)

pinball.cpp: In function 'int main()':
pinball.cpp:33:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   33 |     scanf("%d%d", &m, &n);
      |     ~~~~~^~~~~~~~~~~~~~~~
pinball.cpp:37:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   37 |         scanf("%d%d%d%d", &a[i], &b[i], &c[i], &d[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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