Submission #269377

#	Time	Username	Problem	Language	Result	Execution time	Memory
269377		imeimi2000	Pinball (JOI14_pinball)	C++17	100 / 100	360 ms	10420 KiB

pinball

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_map>
#include <functional>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cstdlib>
 
using namespace std;
typedef long long llong;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<llong, llong> pll;
 
const llong inf = 1e16;
int sz;
struct seg {
    llong dat[1 << 18];
    seg() {
        for (int i = 0; i < (1 << 18); ++i) {
            dat[i] = inf;
        }
    }
    void update(int i, int s, int e, int x, llong v) {
        if (s == e) {
            dat[i] = min(dat[i], v);
            return;
        }
        int m = (s + e) / 2;
        if (x <= m) update(i << 1, s, m, x, v);
        else update(i << 1 | 1, m + 1, e, x, v);
        dat[i] = min(dat[i << 1], dat[i << 1 | 1]);
    }
    void update(int x, llong v) {
        update(1, 0, sz, x, v);
    }
    
    llong query(int i, int s, int e, int x, int y) const {
        if (e < x || y < s) return inf;
        if (x <= s && e <= y) return dat[i];
        int m = (s + e) / 2;
        return min(query(i << 1, s, m, x, y)
                   , query(i << 1 | 1, m + 1, e, x, y));
    }
    llong query(int x, int y) const {
        return query(1, 0, sz, x, y);
    }
} lseg, rseg;
 
int m, n;
int a[100001], b[100001], c[100001], d[100001];
vector<int> comp;
 
int find(int x) {
    return lower_bound(comp.begin(), comp.end(), x) - comp.begin();
}
 
int main() {
    scanf("%d%d", &m, &n);
    for (int i = 0; i < m; ++i) {
        scanf("%d%d%d%d", a + i, b + i, c + i, d + i);
        comp.push_back(c[i]);
    }
    comp.push_back(1);
    comp.push_back(n);
    sort(comp.begin(), comp.end());
    comp.erase(unique(comp.begin(), comp.end()), comp.end());
    sz = comp.size() - 1;
    for (int i = 0; i < m; ++i) {
        a[i] = find(a[i]);
        b[i] = find(b[i] + 1) - 1;
        c[i] = find(c[i]);
    }
    lseg.update(0, 0);
    rseg.update(sz, 0);
    llong ans = inf;
    for (int i = 0; i < m; ++i) {
        ans = min(ans, lseg.query(a[i], b[i]) + rseg.query(a[i], b[i]) + d[i]);
        lseg.update(c[i], lseg.query(a[i], c[i]) + d[i]);
        rseg.update(c[i], rseg.query(c[i], b[i]) + d[i]);
    }
    
    printf("%lld\n", ans < inf ? ans : -1);
	return 0;
}

Compilation message (stderr)

pinball.cpp: In function 'int main()':
pinball.cpp:65:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   65 |     scanf("%d%d", &m, &n);
      |     ~~~~~^~~~~~~~~~~~~~~~
pinball.cpp:67:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   67 |         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