oj.uz

Submission #1097075

# Submission time Handle Problem Language Result Execution time Memory
1097075 2024-10-06T03:15:25 Z RiverFlow Train (APIO24_train) C++17
100 / 100
 336 ms 162572 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 131260 KB Correct.
2 Correct 60 ms 131152 KB Correct.
3 Correct 63 ms 131148 KB Correct.
4 Correct 63 ms 131188 KB Correct.
5 Correct 60 ms 131152 KB Correct.
6 Correct 62 ms 131156 KB Correct.
7 Correct 64 ms 131100 KB Correct.

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 218 ms 147612 KB Correct.
2 Correct 178 ms 154308 KB Correct.
3 Correct 65 ms 130980 KB Correct.
4 Correct 69 ms 132692 KB Correct.
5 Correct 60 ms 131152 KB Correct.
6 Correct 156 ms 146540 KB Correct.
7 Correct 63 ms 131156 KB Correct.
8 Correct 140 ms 150976 KB Correct.
9 Correct 184 ms 154304 KB Correct.

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 218 ms 147612 KB Correct.
2 Correct 178 ms 154308 KB Correct.
3 Correct 65 ms 130980 KB Correct.
4 Correct 69 ms 132692 KB Correct.
5 Correct 60 ms 131152 KB Correct.
6 Correct 156 ms 146540 KB Correct.
7 Correct 63 ms 131156 KB Correct.
8 Correct 140 ms 150976 KB Correct.
9 Correct 184 ms 154304 KB Correct.
10 Correct 288 ms 155128 KB Correct.
11 Correct 270 ms 162236 KB Correct.
12 Correct 69 ms 132728 KB Correct.
13 Correct 62 ms 131136 KB Correct.
14 Correct 235 ms 153916 KB Correct.
15 Correct 285 ms 162500 KB Correct.
16 Correct 240 ms 154324 KB Correct.
17 Correct 209 ms 157364 KB Correct.

Subtask #4
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 131260 KB Correct.
2 Correct 60 ms 131152 KB Correct.
3 Correct 63 ms 131148 KB Correct.
4 Correct 63 ms 131188 KB Correct.
5 Correct 60 ms 131152 KB Correct.
6 Correct 62 ms 131156 KB Correct.
7 Correct 64 ms 131100 KB Correct.
8 Correct 218 ms 147612 KB Correct.
9 Correct 178 ms 154308 KB Correct.
10 Correct 65 ms 130980 KB Correct.
11 Correct 69 ms 132692 KB Correct.
12 Correct 60 ms 131152 KB Correct.
13 Correct 156 ms 146540 KB Correct.
14 Correct 63 ms 131156 KB Correct.
15 Correct 140 ms 150976 KB Correct.
16 Correct 184 ms 154304 KB Correct.
17 Correct 288 ms 155128 KB Correct.
18 Correct 270 ms 162236 KB Correct.
19 Correct 69 ms 132728 KB Correct.
20 Correct 62 ms 131136 KB Correct.
21 Correct 235 ms 153916 KB Correct.
22 Correct 285 ms 162500 KB Correct.
23 Correct 240 ms 154324 KB Correct.
24 Correct 209 ms 157364 KB Correct.
25 Correct 315 ms 162436 KB Correct.
26 Correct 310 ms 162416 KB Correct.
27 Correct 331 ms 162572 KB Correct.
28 Correct 335 ms 162484 KB Correct.
29 Correct 306 ms 155324 KB Correct.
30 Correct 298 ms 154312 KB Correct.
31 Correct 305 ms 154376 KB Correct.
32 Correct 283 ms 154572 KB Correct.
33 Correct 284 ms 153920 KB Correct.
34 Correct 284 ms 153888 KB Correct.
35 Correct 280 ms 153920 KB Correct.
36 Correct 273 ms 154504 KB Correct.
37 Correct 313 ms 162328 KB Correct.
38 Correct 311 ms 154208 KB Correct.
39 Correct 279 ms 153788 KB Correct.
40 Correct 318 ms 162392 KB Correct.
41 Correct 248 ms 155088 KB Correct.
42 Correct 234 ms 153028 KB Correct.
43 Correct 277 ms 152156 KB Correct.
44 Correct 321 ms 162568 KB Correct.
45 Correct 336 ms 162548 KB Correct.
46 Correct 307 ms 162280 KB Correct.
47 Correct 207 ms 158880 KB Correct.
48 Correct 200 ms 158788 KB Correct.
49 Correct 203 ms 158024 KB Correct.
50 Correct 200 ms 158788 KB Correct.
51 Correct 195 ms 158656 KB Correct.
52 Correct 198 ms 157752 KB Correct.