Submission #1097075

#	Time	Username	Problem	Language	Result	Execution time	Memory
1097075		RiverFlow	Train (APIO24_train)	C++17	100 / 100	336 ms	162572 KiB

train

#include <bits/stdc++.h>

#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,tune=native")

#define nl "\n"
#define no "NO"
#define yes "YES"
#define fi first
#define se second
#define vec vector
#define task "main"
#define _mp make_pair
#define ii pair<int, int>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define evoid(val) return void(cout << val)
#define FOR(i, a, b) for(int i = (a); i <= (b); ++i)
#define FOD(i, b, a) for(int i = (b); i >= (a); --i)
#define unq(x) sort(all(x)); x.resize(unique(all(x)) - x.begin())

using namespace std;

template<typename U, typename V> bool maxi(U &a, V b) {
    if (a < b) { a = b; return 1; } return 0;
}
template<typename U, typename V> bool mini(U &a, V b) {
    if (a > b or a == -1) { a = b; return 1; } return 0;
}

const int N = (int)1e5 + 9;
const int mod = (int)1e9 + 7;

struct edge {
    int a, b, x, y, c;
    edge () {};
    edge (int _a, int _b, int _x, int _y, int _c) {
        a  = _a, b = _b, x = _x, y = _y, c = _c;
    }
};

struct meals {
    int l, r;
    bool operator < (const meals & other) {
        return l < other.l;
    }
} meal[N];

edge e[N];

int n, m, w, land[N];

vector<int> g[N];

struct node {
    int l, r, c;
    node () {
        c = 0;
    }
};
node t[N * 100];

struct data_structure {

int cc = 0;

int ver[N], id[N];

    int build(int l, int r) {
        int cur = cc++;
        if (l == r) return cur;
        int m = (l + r) >> 1;
        t[cur].l = build(l, m);
        t[cur].r = build(m + 1, r);
        return cur;
    }
    int update(int id, int p, int l, int r) {
        int cur = cc++;
        t[cur] = t[id];
        ++t[cur].c;
        if (l == r) return cur;
        int m = (l + r) >> 1;
        if (p <= m) {
            t[cur].l = update(t[id].l, p, l, m);
        } else {
            t[cur].r = update(t[id].r, p, m+1, r);
        }
        return cur;
    }
    int m = 0;
    vec<int> val, val2;
    void init() {
        if (m == 0) return ;
        sort(meal, meal + m, [](meals x, meals y) {
            return x.l < y.l;
        });
        val.push_back(0);
        FOR(i, 0, m - 1) val.push_back(meal[i].l);
        unq(val);
        FOR(i, 0, m - 1) val2.push_back(meal[i].r);
        unq(val2);
        int R = sz(val2);
        ver[0] = build(1, R);

        int c = 0;
        FOR(i, 0, m - 1) {
            id[i] = lower_bound(all(val2), meal[i].r) - val2.begin() + 1;
        }
        for(int i = 0, j = i; i < m; i = j + 1) {
            while (j + 1 < m and meal[i].l == meal[j + 1].l) ++j;
            ver[c + 1] = update(ver[c], id[i], 1, R);
            ++c;
            for(int k = i + 1; k <= j; ++k) {
                ver[c] = update(ver[c], id[k], 1, R);
            }
        }
    }
    int get(int R, int L, int l, int r, int k) {
        if (t[R].c - t[L].c < k) return -1;
        if (l == r) return l;
        int m = (l + r) >> 1;
        int lchild = t[t[R].l].c - t[t[L].l].c;
        if (lchild >= k)
            return get(t[R].l, t[L].l, l, m, k);
        return get(t[R].r, t[L].r, m + 1, r, k - lchild);
    }

    int getK(int x, int y, long long k) { // -1 -> do not exist
        if (x > y or m == 0) return -1;
        int lb = lower_bound(all(val), x) - val.begin();
        if (lb == sz(val) or val[lb] > y) return -1;
        --lb;
        int rb = (--upper_bound(all(val), y) - val.begin());
        if (t[ver[rb]].c < k) return -1;
        int vx = get(ver[rb], ver[lb], 1, sz(val2), (int)k);
        if (vx == -1) return -1;
        return val2[vx - 1];
    }

};

long long dp[N]; //M

template<typename T>
struct fenwick {
    int n; vector<T> bit; bool up = 0;
    fenwick() {};
    fenwick(int _n, bool _up) { n = _n; bit.resize(n + 7); up = _up; }
    void upd(int id, T val) {
        if (up) for(; id <= n; id += id & -id) bit[id] += val;
        else    for(; id  > 0; id -= id & -id) bit[id] += val;
    }
    T get(int id) {
        T ans = 0;
        if (up) for(; id  > 0; id -= id & -id) ans += bit[id];
        else    for(; id <= n; id += id & -id) ans += bit[id];
        return ans;
    }
};

data_structure ds;

int idd[N];

struct epoint {
    int ld = 0;

    vector<int> idx;

    set<int> pos;

    void init(int i) {
        ld = i;
        sort(all(idx), [&](int x, int y) {
            return e[x].b < e[y].b;
        });
        for(int i = 0; i < sz(idx); ++i) {
            idd[idx[i]] = i;
        }
    }

    priority_queue<ii, vec<ii>, greater<ii>> pq; // (value, pair)

    void skip(int time) {
        while (sz(pq) and pq.top().fi <= time) {

            // if it exceeds a value -> then left value is no longer to be true
            int p = pq.top().se; pq.pop();

            if (pos.find(p) == pos.end()) {
                continue ;
            }
            pos.erase(p);
            if (sz(pos) >= 2 and *pos.begin() < p and *pos.rbegin() > p) {
                int x = *(--pos.lower_bound(p));
                int y = *pos.lower_bound(p);
                int i = idx[x], j = idx[y];

                long long t = (dp[j] - dp[i]) / land[ld] + 1;
                int tim = ds.getK(e[i].b + 1, e[j].b - 1, t);
                if (tim > 0) {
                    pq.push(_mp(tim, x));
                }
            }
        }
    }
    int query(int time) {
        if (sz(pos) == 0) return -1;
        skip(time);
        return idx[*pos.begin()];
    }

    int key(int x) {
        return idd[x];
    }
    void add(int i, int time) {
        int j = key(i);

        if (sz(pos) == 0) {
            pos.insert(j);
            return ;
        }

        if (*pos.rbegin() > j and dp[idx[*pos.rbegin()]] <= dp[i]) {
            return ;
        }
        skip(time);

        pos.insert(j);
        while (sz(pos)) {
            if (*pos.begin() == j) break ;
            int k = *(--pos.lower_bound(j));
            if (dp[idx[k]] >= dp[i]) {
                pos.erase(k);
            } else
                break ;
        }
        if (*pos.begin() < j) {
            int k = *(--pos.lower_bound(j));
            int p = idx[k];
            long long t = (dp[i] - dp[p]) / land[ld] + 1;
            int tim = ds.getK(e[p].b + 1, e[i].b - 1, t);
            if (tim > 0) {
                pq.push(_mp(tim, k));
            }
        }
        if (*pos.rbegin() > j) {
            int k = *(--pos.upper_bound(j));
            int p = idx[k];
            long long t = (dp[p] - dp[i]) / land[ld] + 1;
            int tim = ds.getK(e[i].b + 1, e[p].b - 1, t);
            if (tim > 0) {
                pq.push(_mp(tim, j));
            }
        }
    }


} ep[N];

namespace SUB {

long long sol() {
    ds.m = w;
    ds.init();

    sort(meal, meal + w, [](meals x, meals y) {
        return x.r < y.r;
    });

    for(int i = 0; i < m; ++i) {
        ep[e[i].y].idx.push_back(i);
    }

    for(int i = 0; i < n; ++i)
        ep[i].init(i);

    vector<ii> ev;

    for(int i = 0; i < m; ++i) {
        ev.push_back(_mp(e[i].a, -(i+1)));
        ev.push_back(_mp(e[i].b, i+1));
    }
    const int mx = (int)1e9;
    for(int i = 0; i < w; ++i) {
        ev.push_back(_mp(meal[i].r, i+mx));
    }


    int j = 0;
    for(int i = 0; i < m; ++i) {
        dp[i] = -1;
        if (e[i].x == 0) {
            int j = 0;
            int lb = 0, rb = w - 1;
            while (lb <= rb) {
                int mid = (lb + rb) >> 1;
                if (meal[mid].r < e[i].a) {
                    j = mid + 1;
                    lb = mid + 1;
                } else
                    rb = mid - 1;
            }

            dp[i] = 1LL * land[0] * j + e[i].c;
        }
    }


    vector<int> val;
    FOR(i, 0, m - 1) val.push_back(e[i].a - 1), val.push_back(e[i].b + 1);
    FOR(i, 0, w - 1) val.push_back(meal[i].l);
    unq(val);

    auto key = [&](int x) {
        return lower_bound(all(val), x) - val.begin() + 1;
    };

    fenwick<int> bit(sz(val), 1);

    sort(ev.begin(), ev.end());

    for(int i = 0, j = 0; i < sz(ev); i = j + 1) {
        while (j + 1 < sz(ev) and ev[j + 1].fi == ev[i].fi) ++j;

//        cerr << "i, j: " << i << ' ' << j << nl;
        for(int k = i; k <= j; ++k) {
            if (ev[k].se > 0 and ev[k].se < mx) {
                int id = ev[k].se - 1;
                if (dp[id] == -1) continue ;
                int y = e[id].y;
                ep[y].add(id, e[id].b);
            }
            // add vao
        }

        for(int k = i; k <= j; ++k) {
            if (ev[k].se < 0) {
                int id = -ev[k].se - 1;
                // dp(id)
//                cerr<<"id: " << id << nl;
                int x = e[id].x;
                int p = ep[x].query(e[id].a - 1);
                if (p == -1) continue ;
                int k = 0;
                if (e[id].a >= e[p].b + 2) {
                    k = bit.get(key(e[id].a - 1)) - bit.get(key(e[p].b + 1) - 1);
                }
                mini(dp[id], 1LL * land[x] * k + e[id].c + dp[p]);
            }
        }

        for(int k = i; k <= j; ++k) {
            if (ev[k].se >= mx) {
                int id = ev[k].se - mx;
                bit.upd(key(meal[id].l), 1);
            }
        }
    }
    sort(meal, meal + w, [](meals x, meals y) {
        return x.l < y.l;
    });
    FOR(i, 0, m - 1) if (dp[i]!=-1){
        int lb = 0, rb = w - 1, ans = -1;
        while (lb <= rb) {
            int m = (lb + rb) >> 1;
            if (meal[m].l > e[i].b) {
                ans = m;
                rb = m - 1;
            } else
                lb = m + 1;
        }
        if (ans != -1) {
            dp[i] += 1LL * land[e[i].y] * (w-ans);
        }
    }
    long long ans = -1;
    FOR(i, 0, m - 1) if (dp[i] != -1 and e[i].y == n - 1) {
        mini(ans, dp[i]);
    }
    return ans;
}

};


long long solve(
    int N, int M, int W,
    vector<int> T, vector<int> X, vector<int> Y,
    vector<int> A, vector<int> B, vector<int> C, vector<int> L, vector<int> R) {

    n = N, m = M, w = W;
    for(int i = 0; i < n; ++i) land[i] = T[i];
    for(int i = 0; i < m; ++i) {
        e[i] = edge(A[i], B[i], X[i], Y[i], C[i]);
        g[X[i]].push_back(i);
    }
    e[m] = edge(0, 0, 0, 0, 0);
    for(int i = 0; i < w; ++i) {
        meal[i].l = L[i], meal[i].r = R[i];
    }
//    if (w <= 10 and m <= 1000) {
//        return SUB1::sol();
//    }
    return SUB::sol();
}

#ifdef LOCAL
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    freopen("main.inp", "r", stdin);
    freopen("main.out", "w", stdout);
  int N, M, W;
  assert(3 == scanf("%d %d %d", &N, &M, &W));
  std::vector<int> t(N), x(M), y(M), a(M), b(M), c(M), l(W), r(W);
  for (int i = 0; i < N; i++)
    assert(1 == scanf("%d", &t[i]));
  for (int i = 0; i < M; i++)
    assert(5 == scanf("%d %d %d %d %d", &x[i], &y[i], &a[i], &b[i], &c[i]));
  for (int i = 0; i < W; i++)
    assert(2 == scanf("%d %d", &l[i], &r[i]));
  printf("%lld", solve(N, M, W, t, x, y, a, b, c, l, r));
}
#endif LOCAL

Compilation message (stderr)

train.cpp:425:8: warning: extra tokens at end of #endif directive [-Wendif-labels]
  425 | #endif LOCAL
      |        ^~~~~
train.cpp: In function 'long long int SUB::sol()':
train.cpp:290:9: warning: unused variable 'j' [-Wunused-variable]
  290 |     int j = 0;
      |         ^

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 30 / 30
• Subtask 4: 60 / 60