oj.uz

Submission #418331

# Submission time Handle Problem Language Result Execution time Memory
418331 2021-06-05T09:57:40 Z usachevd0 Sky Walking (IOI19_walk) C++17
15 / 100
 241 ms 22400 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;
#ifdef LOCAL
    const int maxN = 35;
#else
    const int maxN = 100005;
#endif
int n, m;
vector<int> bg[maxN], en[maxN];
ll V[maxN];

namespace sgt {
    const int logN = 17;
    const int N = 1 << logN;
    int mx[2 * N];
    
    void build(vector<int>& H) {
        for (int i = 0; i < n; ++i)
            mx[i + N] = H[i];
        for (int i = N - 1; i >= 1; --i)
            mx[i] = max(mx[i << 1], mx[i << 1 | 1]);
    }
    int rmxq(int l, int r) {
        int ans = -1e9;
        for (l += N, r += N; l <= r; l >>= 1, r >>= 1) {
            if (l & 1)  chkmax(ans, mx[l++]);
            if (~r & 1) chkmax(ans, mx[r--]);
        }
        return ans;
    }
}

namespace dsu {
    int q[maxN];
    
    void init() {
        memset(q, 255, sizeof q);
    }
    int gt(int x) {
        return q[x] < 0 ? x : q[x] = gt(q[x]);
    }
    bool join(int x, int y) { // y is the parent of x
        x = gt(x), y = gt(y);
        if (x == y) return false;
        //if (-q[x] > -q[y]) swap(x, y);
        q[y] += q[x];
        q[x] = y;
        return true;
    }
}

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);
    }
    
    
    
    dsu::init();
    fill(V, V + m, INF64);
    auto gv = [&](int j) -> ll {
        return V[j];
        int r = dsu::gt(j);
        return V[r] + Y[r] - Y[j];
    };
    
    set<pii> a;
    for (int j : bg[0]) {
        int y = Y[j];
        a.insert({y, j});
        V[j] = y;
        // debug(j, V[j]);
    }
    
    sgt::build(H);
    
    set<pii> needUp;
    for (int i = 1; i < n; ++i) {
        if (a.empty()) return -1;
        
        // while (!needUp.empty()) {
        //     int y = -needUp.begin()->fi;
        //     if (y > H[i]) break;
        //     int j = needUp.begin()->se;
        //     if (!a.count({Y[j], j})) continue;
        //     needUp.erase(needUp.begin());
        //     auto it = a.upper_bound({Y[j], j});
        //     if (it != a.end() && it->fi <= H[i]) {
        //         ll fv = it->fi - Y[j] + gv(it->se);
        //         if (fv <= V[j]) {
        //             V[j] = fv;
        //             dsu::join(j, it->se);
        //         }
        //     }
        // }
        
        for (int j : bg[i]) {
            V[j] = +INF64;
            auto it = a.lower_bound({Y[j], -1});
            if (it != a.begin()) {
                auto pit = prev(it);
                chkmin(V[j], Y[j] - pit->fi + gv(pit->se));
            }
            if (it != a.end() && it->fi <= H[i]) {
                ll fv = it->fi - Y[j] + gv(it->se);
                if (fv <= V[j]) {
                    V[j] = fv;
                    // dsu::join(j, it->se);
                }
            }
            else if (it != a.end()) {
                int j1 = it->se;
                int r = min(R[j], R[j1]);
                if (sgt::rmxq(i, r) >= Y[j1]) {
                    ll fv = it->fi - Y[j] + gv(it->se);
                    if (fv <= V[j]) {
                        V[j] = fv;
                        // dsu::join(j, it->se);
                    }
                }
                // needUp.insert({it->fi, j});
            }
            if (V[j] < INF64 / 2) a.insert({Y[j], j});
        }
        if (i == n - 1) break;
        for (int j : en[i]) {
            int y = Y[j];
            a.erase({y, j});
        }
        
        // debug(i);
        // for (auto el : a) cerr << el << ' ' << gv(el.se) << "  "; cerr << endl;
    }
    ll ans = INF64;
    for (auto& [y, j] : a) {
        // debug(y, j, gv(j));
        chkmin(ans, X[n - 1] - X[0] + y + gv(j));
    }
    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 7 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 7 ms 9928 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 34 ms 8604 KB Output is correct
2 Correct 90 ms 10284 KB Output is correct
3 Correct 113 ms 13052 KB Output is correct
4 Correct 152 ms 19212 KB Output is correct
5 Correct 172 ms 22148 KB Output is correct
6 Correct 179 ms 20804 KB Output is correct
7 Correct 95 ms 15244 KB Output is correct
8 Correct 130 ms 21248 KB Output is correct
9 Correct 186 ms 22400 KB Output is correct
10 Correct 121 ms 20228 KB Output is correct
11 Correct 15 ms 7568 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 8604 KB Output is correct
2 Correct 90 ms 10284 KB Output is correct
3 Correct 113 ms 13052 KB Output is correct
4 Correct 152 ms 19212 KB Output is correct
5 Correct 172 ms 22148 KB Output is correct
6 Correct 179 ms 20804 KB Output is correct
7 Correct 95 ms 15244 KB Output is correct
8 Correct 130 ms 21248 KB Output is correct
9 Correct 186 ms 22400 KB Output is correct
10 Correct 121 ms 20228 KB Output is correct
11 Correct 15 ms 7568 KB Output is correct
12 Correct 114 ms 13024 KB Output is correct
13 Correct 98 ms 18824 KB Output is correct
14 Correct 194 ms 22024 KB Output is correct
15 Correct 147 ms 18832 KB Output is correct
16 Correct 136 ms 18948 KB Output is correct
17 Correct 148 ms 18940 KB Output is correct
18 Correct 153 ms 18816 KB Output is correct
19 Correct 148 ms 18988 KB Output is correct
20 Correct 103 ms 15228 KB Output is correct
21 Correct 33 ms 9860 KB Output is correct
22 Correct 103 ms 16772 KB Output is correct
23 Correct 109 ms 17044 KB Output is correct
24 Correct 130 ms 17448 KB Output is correct
25 Correct 106 ms 17028 KB Output is correct
26 Correct 125 ms 18028 KB Output is correct
27 Correct 241 ms 21808 KB Output is correct
28 Correct 108 ms 18832 KB Output is correct
29 Correct 227 ms 20888 KB Output is correct
30 Correct 103 ms 15228 KB Output is correct
31 Correct 220 ms 22172 KB Output is correct
32 Correct 119 ms 19112 KB Output is correct
33 Incorrect 132 ms 20220 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 7 ms 9932 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -