oj.uz

Submission #902978

# Submission time Handle Problem Language Result Execution time Memory
902978 2024-01-11T05:03:06 Z box Harvest (JOI20_harvest) C++17
5 / 100
 5000 ms 84152 KB 
#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
template <class T, class... U> void bug_h(const T& t, const U&... u) { cerr << t; ((cerr << " | " << u), ...); cerr << endl; }
#define bug(...) cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]: ", bug_h(__VA_ARGS__)
#else
#define cerr if (0) cerr
#define bug(...)
#endif

#define ar array
#define all(v) std::begin(v), std::end(v)
#define sz(v) int(std::size(v))
typedef long long i64;
typedef vector<int> vi;
typedef vector<i64> v64;
typedef pair<int, int> pi;

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;

template <class K> using oset = tree<K, null_type, less<K>, rb_tree_tag, tree_order_statistics_node_update>;

struct DS {
    oset<pair<i64, int>> S; i64 tag = 0;
    constexpr int size() { return sz(S); }
    void insert(i64 v) { S.insert({v - tag, sz(S)}); }
    void extend(i64 v) { tag += v; }
    int num_leq(i64 v) { return S.order_of_key({v - tag, INT_MAX}); }
    void pr() {
        for (auto [k,v] : S) cout << k+tag << ' ';
        cout << '\n';
    }
};
void mrg_self(DS &me, DS &ds) {
    if (me.size() < ds.size()) swap(me, ds);
    for (auto [k, v] : exchange(ds.S, {})) me.insert(k+ds.tag);
}

i64 fdiv(i64 a, i64 b) {
    return a/b - ((a^b) < 0 && a%b);
}

int N, M, L, C, Q;
vi A, B, P;
vector<vi> adj;
vector<DS> ds;
v64 D, pf;
vector<v64> orig;
vi done, on_cyc;
vector<vi> qry;
v64 T, ans;
pi banned;
bool only_cyc;

void dfs(int i) {
    done[i] = 1;
    for (int j : adj[i]) {
        if (only_cyc && !on_cyc[j]) continue;
        if (!only_cyc && on_cyc[j]) {
            bug(j);
        }
        if (pi(i,j) == banned) continue;
        // bug("EDGE", i, j);
        dfs(j);
        mrg_self(ds[i], ds[j]);
    }
    for (auto x : orig[i]) ds[i].insert(x);
    for (auto x : qry[i]) ans[x] = ds[i].num_leq(T[x]);
    ds[i].extend(D[i]);
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> N >> M >> L >> C;
    A = vi(N), B = vi(M);
    for (auto &x : A) cin >> x;
    for (auto &x : B) cin >> x;
    orig.resize(N);
    ds.resize(N);
    for (auto x : B) {
        int y = x;
        if (y < A[0]) y += L;
        int p = upper_bound(all(A), y)-begin(A)-1;
        // bug(p, y-A[p]);
        orig.at(p).push_back(y-A[p]);
    }
    P = vi(N), D = v64(N);
    adj.resize(N);
    for (int i = 0; i < N; i++) {
        int y = (A[i]-C)%L;
        if (y < 0) y += L;
        if (y < A[0]) y += L;
        int p = upper_bound(all(A), y)-begin(A)-1;
        assert(0 <= p && p < N);
        P[i] = p;
        D[i] = C + (y-A[p]);
        bug(i+1, P[i]+1, D[i]);
        adj.at(p).push_back(i);
    }
    cin >> Q;
    qry.resize(N);
    ans = T = v64(Q, -i64(1e18));
    for (int i = 0; i < Q; i++) {
        int v; cin >> v >> T[i], v--;
        qry.at(v).push_back(i);
    }
    done = on_cyc = vi(N);
    pf.resize(N);
    for (int i = 0; i < N; i++) {
        if (done[i]) continue;
        int x = i, y = P.at(i);
        while (x != y) x = P.at(x), y = P.at(P.at(y));
        vi cyc;
        do {
            done[x] = 1;
            cyc.push_back(x);
            x = P[x];
        } while (!done[x]);
        i64 len = 0;
        for (int x : cyc) {
            pf[x] = len;
            len += D[x];
        }
        for (auto x : cyc) on_cyc.at(x) = 1;
        // cerr << "NODE " << x+1 << endl;
        // cerr << "DONE" << endl;
        v64 upds;
        int funny = cyc.back();
        bug(funny+1);
        banned = {P.at(funny), funny};
        only_cyc = 0;
        for (int x : cyc) for (auto z : orig[x]) upds.push_back(z+len-pf.at(x));
        for (auto x : cyc) {
            for (int y : adj[x]) if (!on_cyc[y]) {
                dfs(y);
                for (auto [k, v] : ds[y].S) {
                    orig[x].push_back(k+ds[y].tag);
                    upds.push_back(k+ds[y].tag+len-pf.at(x));
                }
            }
        }
        only_cyc = 1;
        dfs(funny);
        vector<pair<i64, int>> qrys;
        for (int x : cyc) for (int y : qry[x]) qrys.push_back({T[y]-pf.at(x), y});
        sort(all(qrys));
        sort(all(upds), greater<>());
        DS ds; i64 con = 0;
        for (auto [v, y] : qrys) {
            while (sz(upds) && upds.back() <= v) {
                bug(upds.back());
                ds.insert(upds.back()%len);
                con += fdiv(upds.back(), len);
                upds.pop_back();
            }
            bug(y, v);
            ans.at(y) += fdiv(v,len)*ds.size()-con+ds.num_leq(v%len);
        }

    }
    for (auto x : ans) cout << x << '\n';
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 604 KB Output is correct
2 Correct 3 ms 1628 KB Output is correct
3 Correct 6 ms 1624 KB Output is correct
4 Correct 13 ms 1880 KB Output is correct
5 Correct 127 ms 2132 KB Output is correct
6 Correct 124 ms 2204 KB Output is correct
7 Correct 134 ms 1984 KB Output is correct
8 Correct 4 ms 1628 KB Output is correct
9 Correct 3 ms 1628 KB Output is correct
10 Correct 4 ms 1600 KB Output is correct
11 Correct 4 ms 1628 KB Output is correct
12 Correct 131 ms 2140 KB Output is correct
13 Correct 125 ms 2128 KB Output is correct
14 Correct 73 ms 1892 KB Output is correct
15 Correct 81 ms 2016 KB Output is correct
16 Correct 68 ms 1972 KB Output is correct
17 Correct 73 ms 1820 KB Output is correct
18 Correct 83 ms 1872 KB Output is correct
19 Correct 65 ms 1756 KB Output is correct
20 Correct 77 ms 1780 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 13712 KB Output is correct
2 Correct 429 ms 60328 KB Output is correct
3 Correct 178 ms 61976 KB Output is correct
4 Correct 162 ms 63128 KB Output is correct
5 Execution timed out 5064 ms 84152 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 604 KB Output is correct
2 Correct 3 ms 1628 KB Output is correct
3 Correct 6 ms 1624 KB Output is correct
4 Correct 13 ms 1880 KB Output is correct
5 Correct 127 ms 2132 KB Output is correct
6 Correct 124 ms 2204 KB Output is correct
7 Correct 134 ms 1984 KB Output is correct
8 Correct 4 ms 1628 KB Output is correct
9 Correct 3 ms 1628 KB Output is correct
10 Correct 4 ms 1600 KB Output is correct
11 Correct 4 ms 1628 KB Output is correct
12 Correct 131 ms 2140 KB Output is correct
13 Correct 125 ms 2128 KB Output is correct
14 Correct 73 ms 1892 KB Output is correct
15 Correct 81 ms 2016 KB Output is correct
16 Correct 68 ms 1972 KB Output is correct
17 Correct 73 ms 1820 KB Output is correct
18 Correct 83 ms 1872 KB Output is correct
19 Correct 65 ms 1756 KB Output is correct
20 Correct 77 ms 1780 KB Output is correct
21 Correct 98 ms 13712 KB Output is correct
22 Correct 429 ms 60328 KB Output is correct
23 Correct 178 ms 61976 KB Output is correct
24 Correct 162 ms 63128 KB Output is correct
25 Execution timed out 5064 ms 84152 KB Time limit exceeded
26 Halted 0 ms 0 KB -