oj.uz

Submission #52508

# Submission time Handle Problem Language Result Execution time Memory
52508 2018-06-26T06:20:57 Z 강태규(#1363) Pinball (JOI14_pinball) C++11
51 / 100
 26 ms 1124 KB 
#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 << 11); ++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

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]
     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]
         scanf("%d%d%d%d", a + i, b + i, c + i, d + i);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Correct 2 ms 488 KB Output is correct
4 Correct 2 ms 488 KB Output is correct
5 Correct 3 ms 588 KB Output is correct
6 Correct 2 ms 600 KB Output is correct
7 Correct 2 ms 600 KB Output is correct
8 Correct 2 ms 600 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Correct 2 ms 488 KB Output is correct
4 Correct 2 ms 488 KB Output is correct
5 Correct 3 ms 588 KB Output is correct
6 Correct 2 ms 600 KB Output is correct
7 Correct 2 ms 600 KB Output is correct
8 Correct 2 ms 600 KB Output is correct
9 Correct 3 ms 600 KB Output is correct
10 Correct 2 ms 600 KB Output is correct
11 Correct 2 ms 600 KB Output is correct
12 Correct 3 ms 616 KB Output is correct
13 Correct 3 ms 616 KB Output is correct
14 Correct 2 ms 616 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Correct 2 ms 488 KB Output is correct
4 Correct 2 ms 488 KB Output is correct
5 Correct 3 ms 588 KB Output is correct
6 Correct 2 ms 600 KB Output is correct
7 Correct 2 ms 600 KB Output is correct
8 Correct 2 ms 600 KB Output is correct
9 Correct 3 ms 600 KB Output is correct
10 Correct 2 ms 600 KB Output is correct
11 Correct 2 ms 600 KB Output is correct
12 Correct 3 ms 616 KB Output is correct
13 Correct 3 ms 616 KB Output is correct
14 Correct 2 ms 616 KB Output is correct
15 Correct 2 ms 616 KB Output is correct
16 Correct 2 ms 616 KB Output is correct
17 Correct 5 ms 616 KB Output is correct
18 Correct 4 ms 616 KB Output is correct
19 Correct 4 ms 616 KB Output is correct
20 Correct 4 ms 616 KB Output is correct
21 Correct 3 ms 616 KB Output is correct
22 Correct 4 ms 616 KB Output is correct
23 Correct 3 ms 672 KB Output is correct
24 Correct 4 ms 672 KB Output is correct

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Correct 2 ms 488 KB Output is correct
4 Correct 2 ms 488 KB Output is correct
5 Correct 3 ms 588 KB Output is correct
6 Correct 2 ms 600 KB Output is correct
7 Correct 2 ms 600 KB Output is correct
8 Correct 2 ms 600 KB Output is correct
9 Correct 3 ms 600 KB Output is correct
10 Correct 2 ms 600 KB Output is correct
11 Correct 2 ms 600 KB Output is correct
12 Correct 3 ms 616 KB Output is correct
13 Correct 3 ms 616 KB Output is correct
14 Correct 2 ms 616 KB Output is correct
15 Correct 2 ms 616 KB Output is correct
16 Correct 2 ms 616 KB Output is correct
17 Correct 5 ms 616 KB Output is correct
18 Correct 4 ms 616 KB Output is correct
19 Correct 4 ms 616 KB Output is correct
20 Correct 4 ms 616 KB Output is correct
21 Correct 3 ms 616 KB Output is correct
22 Correct 4 ms 616 KB Output is correct
23 Correct 3 ms 672 KB Output is correct
24 Correct 4 ms 672 KB Output is correct
25 Incorrect 26 ms 1124 KB Output isn't correct
26 Halted 0 ms 0 KB -