Submission #170958

#	Time	Username	Problem	Language	Result	Execution time	Memory
170958		ne4eHbKa	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	57 / 100	1081 ms	4260 KiB

skyscraper

//{ <defines>
#ifndef _LOCAL
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-O3")
#pragma GCC optimize("Ofast")
#endif

#include <bits/stdc++.h>
using namespace std;

#define fr(i, n) for(int i = 0; i < n; ++i)
#define fo(n) fr(i, n)

#define re return
#define ef else if
#define ifn(x) if(!(x))
#define _  << ' ' <<

#define ft first
#define sd second
#define ve vector
#define pb push_back
#define eb emplace_back

#define sz(x) int(x.size())
#define pw(x) (1 << (x))
#define PW(x) (1ll << (x))
#define bnd(x) x.begin(), x.end()
#define clr(x, y) memset(x, y, sizeof x)

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef ve<int> vi;

const int oo = 2e9;
const ll OO = 4e18;
//const ld pi = arg(complex<ld>(-1, 0));
//const ld pi2 = pi + pi;
const int md = 0x3b800001;
const int MD = 1e9 + 7;

inline ll time() {re chrono :: system_clock().now().time_since_epoch().count();}
mt19937 rnd(time());
mt19937_64 RND(time());

template<typename t> inline void umin(t &a, t b) {a = min(a, b);}
template<typename t> inline void umax(t &a, t b) {a = max(a, b);}
//} </defines>
const int N = 3e4 + 5;

int n, m, st, fn, d[N];
vi g[N];
bool mk[N];

inline int mn(int x, int y) {re d[x] < d[y] ? x : y;}

struct tree {
    tree *l, *r;
    int v;
    tree(int tl = 0, int tr = n - 1): l(r = 0), v(tl) {
        if(tl < tr) {
            int tm = (tl + tr) >> 1;
            l = new tree(tl, tm); ++tm;
            r = new tree(tm, tr);
            v = mn(l -> v, r -> v);
        }
    }
    void upd(int ps, int tl = 0, int tr = n - 1) {
        if(tl + 1 < tr) {
            int tm = (tl + tr) >> 1;
            ps <= tm
                ? l -> upd(ps, tl, tm)
                : r -> upd(ps, tm + 1, tr);
        }
        if(l) v = mn(l -> v, r -> v);
    }
};

void solve() {
    cin >> n >> m;
    fo(m) {
        int b, p;
        cin >> b >> p;
        if(i == 0) st = b;
        if(i == 1) fn = b;
        g[b].pb(p);
    }

    fo(n) d[i] = N;
    d[st] = 0;

    fo(n) sort(bnd(g[i]));

    struct sc {
        inline bool operator() (const int &a, const int &b) const
            {re d[a] == d[b] ? a < b : d[a] < d[b];}
    };

    tree *t = new tree();

    for(;;) {
        int v = t -> v;
        if(mk[v]) break;
        if(v == fn) re void(cout << d[fn] << endl);
        int pr = -1;
        for(int p : g[v]) if(p != pr) {
            pr = p;
            for(int sign = -1; sign <= 1; sign += 2) {
                for(int w = d[v] + 1, u = v + sign * p; u >= 0 && u < n; ++w, u += sign * p) {
                    if(mk[u]) continue;
                    if(w < d[u]) {
                        d[u] = w;
                        t -> upd(u);
                    }
                }
            }
        }
        d[v] = N; t -> upd(v); mk[v] = true;
    }

    cout << -1 << endl;
}

/*
5 3
0 2
1 1
4 1
*/

int main() {
    solve();
}

• Subtask 1: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 14 / 14
• Subtask 4: 21 / 21
• Subtask 5: 0 / 43