oj.uz

Submission #146074

# Submission time Handle Problem Language Result Execution time Memory
146074 2019-08-21T23:06:14 Z osaaateiasavtnl Pinball (JOI14_pinball) C++14
0 / 100
 18 ms 19320 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcount
const int N = 1e5 + 7, C = 3e5 + 7, INF = 1e18 + 7;
int m, n;
struct Seg { int l, r, p, c; } a[N];
vector <int> c;
int pos(int x) { return lower_bound(all(c), x) - c.begin(); }
void upd(int v, int tl, int tr, int p, int x, int *tree) {
    if (tl == tr) { tree[v] = min(tree[v], x); return; }
    int tm = (tl + tr) >> 1; 
    if (p <= tm) upd(v * 2 + 1, tl, tm, p, x, tree);
    else upd(v * 2 + 2, tm + 1, tr, p, x, tree);
    tree[v] = min(tree[v * 2 + 1], tree[v * 2 + 2]);
}
int get(int v, int tl, int tr, int l, int r, int *tree) {
    if (tr < l || r < tl) return INF;
    if (l <= tl && tr <= r) return tree[v];
    int tm = (tl + tr) >> 1;
    return min(get(v * 2 + 1, tl, tm, l, r, tree), get(v * 2 + 2, tm + 1, tr, l, r, tree));            
}
int dp[N][2], tree[2][C << 2];
signed main() {
    #ifdef HOME
    freopen("input.txt", "r", stdin);
    #else
    ios_base::sync_with_stdio(0); cin.tie(0);
    #endif
    for (int i = 0; i < 2; ++i) for (int j = 0; j < (C << 2); ++j) tree[i][j] = INF;
    cin >> m >> n;
    for (int i = 0; i < m; ++i) { cin >> a[i].l >> a[i].r >> a[i].p >> a[i].c; c.app(a[i].l); c.app(a[i].r); c.app(a[i].p); }
    sort(all(c)); c.resize(unique(all(c)) - c.begin());
    upd(0, 0, C, 0, 0, tree[0]); upd(0, 0, C, (int)c.size() - 1, 0, tree[1]);
    int ans = INF;
    for (int i = 0; i < m; ++i) { 
        a[i].l = pos(a[i].l); a[i].r = pos(a[i].r); a[i].p = pos(a[i].p);
        for (int j = 0; j < 2; ++j) { 
            dp[i][j] = get(0, 0, C, a[i].l, a[i].r, tree[j]) + a[i].c; 
            upd(0, 0, C, a[i].p, dp[i][j], tree[j]);
        }
        ans = min(ans, dp[i][0] + dp[i][1] - a[i].c);
    }
    if (ans == INF) cout << "-1\n";
    else cout << ans << '\n';
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 19320 KB Output is correct
2 Correct 17 ms 19064 KB Output is correct
3 Correct 17 ms 19192 KB Output is correct
4 Correct 17 ms 19192 KB Output is correct
5 Correct 17 ms 19196 KB Output is correct
6 Correct 18 ms 19192 KB Output is correct
7 Incorrect 17 ms 19192 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 19320 KB Output is correct
2 Correct 17 ms 19064 KB Output is correct
3 Correct 17 ms 19192 KB Output is correct
4 Correct 17 ms 19192 KB Output is correct
5 Correct 17 ms 19196 KB Output is correct
6 Correct 18 ms 19192 KB Output is correct
7 Incorrect 17 ms 19192 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 19320 KB Output is correct
2 Correct 17 ms 19064 KB Output is correct
3 Correct 17 ms 19192 KB Output is correct
4 Correct 17 ms 19192 KB Output is correct
5 Correct 17 ms 19196 KB Output is correct
6 Correct 18 ms 19192 KB Output is correct
7 Incorrect 17 ms 19192 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 19320 KB Output is correct
2 Correct 17 ms 19064 KB Output is correct
3 Correct 17 ms 19192 KB Output is correct
4 Correct 17 ms 19192 KB Output is correct
5 Correct 17 ms 19196 KB Output is correct
6 Correct 18 ms 19192 KB Output is correct
7 Incorrect 17 ms 19192 KB Output isn't correct
8 Halted 0 ms 0 KB -