oj.uz

Submission #66084

# Submission time Handle Problem Language Result Execution time Memory
66084 2018-08-09T13:57:13 Z SpeedOfMagic Pinball (JOI14_pinball) C++17
51 / 100
 1000 ms 64104 KB 
/** MIT License Copyright (c) 2018 Vasilyev Daniil **/
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
template<typename T> using v = vector<T>;
#define int long long
typedef long double ld;
typedef string str;
typedef vector<int> vint;
#define rep(a, l, r) for(int a = (l); a < (r); a++)
#define pb push_back
#define sz(a) ((int) a.size())
const long long inf = 4611686018427387903; //2^62 - 1
#if 0  //FileIO
const string fileName = "";
ifstream fin ((fileName == "" ? "input.txt"  : fileName + ".in" ));
ofstream fout((fileName == "" ? "output.txt" : fileName + ".out"));
#define get fin>>
#define put fout<<
#else
#define get cin>>
#define put cout<<
#endif
#define eol put endl
#define check(a) put #a << ": " << a << endl;
void read() {}     template<typename Arg,typename... Args> void read (Arg& arg,Args&... args){get (arg)     ;read(args...) ;}
void print(){}     template<typename Arg,typename... Args> void print(Arg  arg,Args...  args){put (arg)<<" ";print(args...);}
void debug(){eol;} template<typename Arg,typename... Args> void debug(Arg  arg,Args...  args){put (arg)<<" ";debug(args...);}
int getInt(){int a; get a; return a;}
//code goes here
vint segTree;
int tot;
void init(int n) {
    tot = n;
    while (tot & (tot - 1))
        tot++;
    segTree = vint(2 * tot);
    rep(i, 1, tot * 2)
        segTree[i] = inf;
}

int query(int l, int r, int cur = 1, int ll = 1, int rr = tot) {
    if (l > r)
        return inf;
    if (l == ll && r == rr)
        return segTree[cur];
    int p = (ll + rr) / 2;
    return min(query(l, min(r, p), cur * 2, ll, p), query(max(l, p + 1), r, cur * 2 + 1, p + 1, rr));
}

void update(int pos, int val, int cur = 1, int ll = 1, int rr = tot) {
    if (ll == rr) {
        segTree[cur] = min(segTree[cur], val);
        return;
    }

    int p = (ll + rr) / 2;
    if (pos <= p)
        update(pos, val, cur * 2, ll, p);
    else
        update(pos, val, cur * 2 + 1, p + 1, rr);

    segTree[cur] = min(segTree[cur * 2], segTree[cur * 2 + 1]);
}

void run() {
    int m, n;
    read(m, n);
    int a[m], b[m], c[m], d[m];
    set<int> all;
    rep(i, 0, m) {
        read(a[i], b[i], c[i], d[i]);
        all.insert(a[i]);
        all.insert(b[i]);
        all.insert(c[i]);
    }

    if (!all.count(1) || !all.count(n)) {
        put -1;
        return;
    }

    map<int, int> hsh;
    int p = 1;
    for (int i : all)
        hsh[i] = p++;
    n = -inf;
    rep(i, 0, m) {
        a[i] = hsh[a[i]];
        b[i] = hsh[b[i]];
        c[i] = hsh[c[i]];
        n = max(n, b[i]);
    }

    int dp[2][m];
    rep(k, 0, 2) {
        init(n);
        rep(i, 0, m) {
            if ((!k && a[i] == 1) || (k && b[i] == n))
                dp[k][i] = d[i];
            else
                dp[k][i] = min(inf, query(a[i], b[i]) + d[i]);
            update(c[i], dp[k][i]);
        }
    }

    //rep(i, 0, 2) { rep(j, 0, m) print(dp[i][j]); eol; }

    int ans = inf;
    rep(i, 0, m)
        ans = min(ans, dp[0][i] + dp[1][i] - d[i]);
    if (ans == inf)
        put -1;
    else
        put ans;
}

int32_t main() {srand(time(0)); ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); put fixed; put setprecision(15); run(); return 0;}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 2 ms 360 KB Output is correct
3 Correct 3 ms 440 KB Output is correct
4 Correct 2 ms 520 KB Output is correct
5 Correct 3 ms 732 KB Output is correct
6 Correct 2 ms 732 KB Output is correct
7 Correct 2 ms 732 KB Output is correct
8 Correct 2 ms 732 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 2 ms 360 KB Output is correct
3 Correct 3 ms 440 KB Output is correct
4 Correct 2 ms 520 KB Output is correct
5 Correct 3 ms 732 KB Output is correct
6 Correct 2 ms 732 KB Output is correct
7 Correct 2 ms 732 KB Output is correct
8 Correct 2 ms 732 KB Output is correct
9 Correct 3 ms 732 KB Output is correct
10 Correct 3 ms 732 KB Output is correct
11 Correct 4 ms 732 KB Output is correct
12 Correct 3 ms 732 KB Output is correct
13 Correct 3 ms 780 KB Output is correct
14 Correct 2 ms 788 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 2 ms 360 KB Output is correct
3 Correct 3 ms 440 KB Output is correct
4 Correct 2 ms 520 KB Output is correct
5 Correct 3 ms 732 KB Output is correct
6 Correct 2 ms 732 KB Output is correct
7 Correct 2 ms 732 KB Output is correct
8 Correct 2 ms 732 KB Output is correct
9 Correct 3 ms 732 KB Output is correct
10 Correct 3 ms 732 KB Output is correct
11 Correct 4 ms 732 KB Output is correct
12 Correct 3 ms 732 KB Output is correct
13 Correct 3 ms 780 KB Output is correct
14 Correct 2 ms 788 KB Output is correct
15 Correct 3 ms 788 KB Output is correct
16 Correct 3 ms 832 KB Output is correct
17 Correct 5 ms 1052 KB Output is correct
18 Correct 6 ms 1052 KB Output is correct
19 Correct 5 ms 1052 KB Output is correct
20 Correct 5 ms 1052 KB Output is correct
21 Correct 5 ms 1140 KB Output is correct
22 Correct 6 ms 1412 KB Output is correct
23 Correct 6 ms 1540 KB Output is correct
24 Correct 5 ms 1540 KB Output is correct

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 2 ms 360 KB Output is correct
3 Correct 3 ms 440 KB Output is correct
4 Correct 2 ms 520 KB Output is correct
5 Correct 3 ms 732 KB Output is correct
6 Correct 2 ms 732 KB Output is correct
7 Correct 2 ms 732 KB Output is correct
8 Correct 2 ms 732 KB Output is correct
9 Correct 3 ms 732 KB Output is correct
10 Correct 3 ms 732 KB Output is correct
11 Correct 4 ms 732 KB Output is correct
12 Correct 3 ms 732 KB Output is correct
13 Correct 3 ms 780 KB Output is correct
14 Correct 2 ms 788 KB Output is correct
15 Correct 3 ms 788 KB Output is correct
16 Correct 3 ms 832 KB Output is correct
17 Correct 5 ms 1052 KB Output is correct
18 Correct 6 ms 1052 KB Output is correct
19 Correct 5 ms 1052 KB Output is correct
20 Correct 5 ms 1052 KB Output is correct
21 Correct 5 ms 1140 KB Output is correct
22 Correct 6 ms 1412 KB Output is correct
23 Correct 6 ms 1540 KB Output is correct
24 Correct 5 ms 1540 KB Output is correct
25 Correct 51 ms 4604 KB Output is correct
26 Correct 149 ms 11268 KB Output is correct
27 Correct 504 ms 22772 KB Output is correct
28 Correct 218 ms 22772 KB Output is correct
29 Correct 392 ms 26536 KB Output is correct
30 Correct 349 ms 26536 KB Output is correct
31 Correct 817 ms 41328 KB Output is correct
32 Correct 664 ms 41328 KB Output is correct
33 Correct 103 ms 41328 KB Output is correct
34 Correct 438 ms 41328 KB Output is correct
35 Correct 529 ms 64104 KB Output is correct
36 Execution timed out 1087 ms 64104 KB Time limit exceeded
37 Halted 0 ms 0 KB -