oj.uz

Submission #799908

# Submission time Handle Problem Language Result Execution time Memory
799908 2023-08-01T08:06:06 Z 이동현(#10084) Harvest (JOI20_harvest) C++17
0 / 100
 5000 ms 6388 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define int long long
using namespace std;

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, m, l, c;
    cin >> n >> m >> l >> c;
    vector<int> a(n), b(m);
    for(int i = 0; i < n; ++i){
        cin >> a[i];
    }
    for(int i = 0; i < m; ++i){
        cin >> b[i];
    }

    auto god = [&](int x, int y){
        return c + (y - c % l - x + l * 2) % l;
    };

    vector<deque<int>> mine(n);
    vector<int> madd(n);
    int p = 0;
    for(int i = 0; i < n; ++i){
        while(p < m && a[i] > b[p]) ++p;

        int r = p - 1;
        while(r + 1 < m && (i == n - 1 || b[r + 1] < a[i + 1])){
            ++r;
            mine[i].push_back(b[r] - a[i]);
        }

        p = r;
    }

    for(int i = 0; i < m && b[i] < a[0]; ++i){
        mine[n - 1].push_back(b[i] - a[n - 1] + l);
    }

    vector<int> got(n);
    vector<vector<int>> way(n);
    for(int i = 0; i < n; ++i){
        int pos = (a[i] - c % l + l) % l;

        int p = lower_bound(a.begin(), a.end(), pos + 1) - a.begin();
        --p;
        if(p < 0) p = n - 1;

        got[i] = p;
        way[p].push_back(i);
    }

    int q;
    cin >> q;
    vector<int> ans(q);
    vector<vector<array<int, 2>>> que(n);
    for(int i = 0; i < q; ++i){
        int x, y;
        cin >> x >> y;
        --x;
        que[x].push_back({y, i});
    }

    vector<int> cyclen(n, -1);
    vector<int> chk(n), cdist(n);
    int cn = 0;

    auto checkcycle = [&](auto&&self, int x)->void{
        if(chk[x]) return;
        chk[x] = cn;

        if(chk[got[x]] == chk[x]){
            int val = cdist[x] - cdist[got[x]] + god(a[got[x]], a[x]);
            // cout << x << ' ' << dist << ' ' << god(a[x], a[x]) << endl;
            while(cyclen[x] == -1){
                cyclen[x] = val;
                x = got[x];
            }
            return;
        }

        cdist[got[x]] = cdist[x] + god(a[got[x]], a[x]);
        self(self, got[x]);
    };

    for(int i = 0; i < n; ++i){
        ++cn;
        checkcycle(checkcycle, i);
    }

    vector<int> chk1(n);
    auto sol1 = [&](auto&&self, int x)->void{
        assert(cyclen[x] == -1);
        if(chk1[x]) return;
        chk1[x] = 1;

        for(auto&nxt:way[x]){
            self(self, nxt);

            madd[nxt] += god(a[x], a[nxt]);
        }
        sort(way[x].begin(), way[x].end(), [&](int&x, int&y){
            return (!(int)mine[x].size() ? -(int)6e18 : mine[x][0]) + madd[x] < (!(int)mine[y].size() ? -(int)6e18 : mine[y][0]) + madd[y];
        });
        for(auto&nxt:way[x]){
            if((int)mine[x].size() < (int)mine[nxt].size()){
                swap(mine[x], mine[nxt]);
                swap(madd[x], madd[nxt]);
            }

            if((int)mine[nxt].size()){
                if(mine[x].back() + madd[x] < mine[nxt].front() + madd[nxt]){
                    while((int)mine[nxt].size()){
                        mine[x].push_back(mine[nxt].front() + madd[nxt] - madd[x]);
                        mine[nxt].pop_front();
                    }
                }
                else if(mine[x].front() + madd[x] > mine[nxt].back() + madd[nxt]){
                    while((int)mine[nxt].size()){
                        mine[x].push_front(mine[nxt].back() + madd[nxt] - madd[x]);
                        mine[nxt].pop_back();
                    }
                }
                else{
                    assert(0);
                }
            }
        }
    };

    for(int i = 0; i < n; ++i){
        vector<int> chk(n);

        auto sol = [&](auto&&self, int x, int dist)->void{
            if(chk[x]) return;
            chk[x] = 1;

            for(auto&[t, anspos]:que[i]){
                for(auto&j:mine[x]){
                    if(j + dist > t) continue;

                    ans[anspos] += 1 + (cyclen[i] != -1 ? (t - (j + dist)) / cyclen[i] : 0);
                }
            }

            for(auto&nxt:way[x]){
                self(self, nxt, dist + god(a[x], a[nxt]));
            }
        };

        sol(sol, i, 0);
    }

    for(int i = 0; i < n; ++i){
        if(cyclen[i] != -1) continue;

        sol1(sol1, i);
    }

    for(int i = 0; i < q; ++i){
        cout << ans[i] << '\n';
    }
    
    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 4 ms 3020 KB Output is correct
3 Correct 81 ms 3008 KB Output is correct
4 Runtime error 15 ms 5704 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5039 ms 6388 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 4 ms 3020 KB Output is correct
3 Correct 81 ms 3008 KB Output is correct
4 Runtime error 15 ms 5704 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -