oj.uz

Submission #418131

# Submission time Handle Problem Language Result Execution time Memory
418131 2021-06-05T06:50:08 Z usachevd0 Sky Walking (IOI19_walk) C++17
15 / 100
 184 ms 21596 KB 
#include <bits/stdc++.h>
#ifndef LOCAL
    #include "walk.h"
#endif

using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define Time (clock() * 1.0 / CLOCKS_PER_SEC)
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
using ld = long double;
template<typename T1, typename T2> bool chkmin(T1& x, T2 y) {
    return y < x ? (x = y, true) : false;
}
template<typename T1, typename T2> bool chkmax(T1& x, T2 y) {
    return y > x ? (x = y, true) : false;
}
void debug_out() {
    cerr << endl;
}
template<typename T1, typename... T2> void debug_out(T1 A, T2... B) {
    cerr << ' ' << A;
    debug_out(B...);
}
template<typename T> void mdebug_out(T* a, int n) {
    for (int i = 0; i < n; ++i)
        cerr << a[i] << ' ';
    cerr << endl;
}
#ifdef LOCAL
    #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
    #define mdebug(a, n) cerr << #a << ": ", mdebug_out(a, n)
#else
    #define debug(...) 1337
    #define mdebug(a, n) 1337
#endif
template<typename T> ostream& operator << (ostream& stream, const vector<T>& v) {
    for (auto& x : v)
        stream << x << ' ';
    return stream;
}
template<typename T1, typename T2> ostream& operator << (ostream& stream, const pair<T1, T2>& p) {
    return stream << p.first << ' ' << p.second;
}

const ll INF64 = 1e18;
const int maxN = 100005;
int n, m;
vector<int> bg[maxN], en[maxN];

ll min_distance(vector<int> X, vector<int> H, vector<int> L, vector<int> R, vector<int> Y, int SI, int TI) {
    n = X.size(), m = L.size();
    assert(SI == 0 && TI == n - 1);
    
    for (int j = 0; j < m; ++j) {
        int l = L[j], r = R[j];
        bg[l].push_back(j);
        en[r].push_back(j);
    }
    
    multiset<pil> a;
    for (int j : bg[0]) {
        int y = Y[j];
        a.insert({y, y});
    }
    for (int i = 1; i < n; ++i) {
        if (a.empty()) return -1;
        
        for (int j : bg[i]) {
            int y = Y[j];
            ll v = INF64;
            auto it = a.lower_bound({y, -1});
            if (it != a.end() && it->fi <= H[i])
                chkmin(v, it->fi - y + it->se);
            if (it != a.begin()) {
                it = prev(it);
                chkmin(v, y - it->fi + it->se);
            }
            a.insert({y, v});
        }
        if (i == n - 1) break;
        for (int j : en[i]) {
            int y = Y[j];
            a.erase(a.lower_bound({y, -1}));
        }
    }
    ll ans = INF64;
    for (auto& [y, v] : a) {
        chkmin(ans, X[n - 1] - X[0] + y + v);
    }
    return ans;
}


#ifdef LOCAL

int32_t main() {
#ifdef LOCAL
    freopen("in", "r", stdin);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);
    
        int n, m;
    assert(2 == scanf("%d%d", &n, &m));
    vector<int> x(n), h(n);
    for (int i = 0; i < n; i++)
        assert(2 == scanf("%d%d", &x[i], &h[i]));
    vector<int> l(m), r(m), y(m);
    for (int i = 0; i < m; i++)
        assert(3 == scanf("%d%d%d", &l[i], &r[i], &y[i]));
    int s, g;
    assert(2 == scanf("%d%d", &s, &g));
    fclose(stdin);

    long long result = min_distance(x, h, l, r, y, s, g);

    printf("%lld\n", result);
    fclose(stdout);
    
    return 0;
}

#endif

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 8 ms 9932 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 9932 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 7440 KB Output is correct
2 Correct 92 ms 9016 KB Output is correct
3 Correct 106 ms 11512 KB Output is correct
4 Correct 156 ms 17268 KB Output is correct
5 Correct 178 ms 21596 KB Output is correct
6 Correct 167 ms 19524 KB Output is correct
7 Correct 86 ms 13556 KB Output is correct
8 Correct 113 ms 19188 KB Output is correct
9 Correct 164 ms 20872 KB Output is correct
10 Correct 106 ms 18948 KB Output is correct
11 Correct 15 ms 6476 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 7440 KB Output is correct
2 Correct 92 ms 9016 KB Output is correct
3 Correct 106 ms 11512 KB Output is correct
4 Correct 156 ms 17268 KB Output is correct
5 Correct 178 ms 21596 KB Output is correct
6 Correct 167 ms 19524 KB Output is correct
7 Correct 86 ms 13556 KB Output is correct
8 Correct 113 ms 19188 KB Output is correct
9 Correct 164 ms 20872 KB Output is correct
10 Correct 106 ms 18948 KB Output is correct
11 Correct 15 ms 6476 KB Output is correct
12 Correct 114 ms 11344 KB Output is correct
13 Correct 90 ms 16772 KB Output is correct
14 Correct 170 ms 21508 KB Output is correct
15 Correct 128 ms 16996 KB Output is correct
16 Correct 125 ms 17168 KB Output is correct
17 Correct 131 ms 17160 KB Output is correct
18 Correct 127 ms 17012 KB Output is correct
19 Correct 133 ms 17164 KB Output is correct
20 Correct 84 ms 13508 KB Output is correct
21 Correct 32 ms 8516 KB Output is correct
22 Correct 102 ms 14852 KB Output is correct
23 Correct 106 ms 15112 KB Output is correct
24 Correct 111 ms 16644 KB Output is correct
25 Correct 99 ms 15072 KB Output is correct
26 Correct 119 ms 19204 KB Output is correct
27 Correct 184 ms 21348 KB Output is correct
28 Correct 87 ms 16768 KB Output is correct
29 Correct 165 ms 19416 KB Output is correct
30 Correct 80 ms 13572 KB Output is correct
31 Correct 161 ms 20856 KB Output is correct
32 Correct 99 ms 17444 KB Output is correct
33 Incorrect 102 ms 18572 KB Output isn't correct
34 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Runtime error 8 ms 9932 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -