oj.uz

답안 #418178

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
418178 2021-06-05T07:39:49 Z usachevd0 Sky Walking (IOI19_walk) C++17
15 / 100
 178 ms 18464 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;
    }
    
    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});
            }
            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) {
        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

# 결과 실행 시간 메모리 Grader output
1 Runtime error 8 ms 9864 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 7 ms 9932 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 9024 KB Output is correct
2 Correct 93 ms 11244 KB Output is correct
3 Correct 109 ms 11200 KB Output is correct
4 Correct 150 ms 15384 KB Output is correct
5 Correct 172 ms 18272 KB Output is correct
6 Correct 176 ms 17116 KB Output is correct
7 Correct 83 ms 12484 KB Output is correct
8 Correct 109 ms 17560 KB Output is correct
9 Correct 159 ms 18456 KB Output is correct
10 Correct 107 ms 17092 KB Output is correct
11 Correct 15 ms 7064 KB Output is correct

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 9024 KB Output is correct
2 Correct 93 ms 11244 KB Output is correct
3 Correct 109 ms 11200 KB Output is correct
4 Correct 150 ms 15384 KB Output is correct
5 Correct 172 ms 18272 KB Output is correct
6 Correct 176 ms 17116 KB Output is correct
7 Correct 83 ms 12484 KB Output is correct
8 Correct 109 ms 17560 KB Output is correct
9 Correct 159 ms 18456 KB Output is correct
10 Correct 107 ms 17092 KB Output is correct
11 Correct 15 ms 7064 KB Output is correct
12 Correct 108 ms 11128 KB Output is correct
13 Correct 93 ms 15044 KB Output is correct
14 Correct 170 ms 18320 KB Output is correct
15 Correct 136 ms 15300 KB Output is correct
16 Correct 132 ms 15172 KB Output is correct
17 Correct 133 ms 15244 KB Output is correct
18 Correct 129 ms 15300 KB Output is correct
19 Correct 131 ms 15140 KB Output is correct
20 Correct 88 ms 12484 KB Output is correct
21 Correct 32 ms 8208 KB Output is correct
22 Correct 108 ms 13336 KB Output is correct
23 Correct 114 ms 13620 KB Output is correct
24 Correct 146 ms 14856 KB Output is correct
25 Correct 105 ms 13624 KB Output is correct
26 Correct 128 ms 16980 KB Output is correct
27 Correct 178 ms 18084 KB Output is correct
28 Correct 95 ms 14996 KB Output is correct
29 Correct 169 ms 17040 KB Output is correct
30 Correct 80 ms 12612 KB Output is correct
31 Correct 162 ms 18464 KB Output is correct
32 Correct 101 ms 16200 KB Output is correct
33 Incorrect 107 ms 17220 KB Output isn't correct
34 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 8 ms 9864 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -