oj.uz

Submission #1006046

# Submission time Handle Problem Language Result Execution time Memory
1006046 2024-06-23T10:41:09 Z Unforgettablepl Harvest (JOI20_harvest) C++17
5 / 100
 1431 ms 524288 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define int long long
 
const int INF = 1e18;

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m,l,c;
    cin >> n >> m >> l >> c;
    vector<int> employee(n+1);
    vector<int> apple(m);
    vector<pair<int,int>> adj(n+1);
    for(int i=1;i<=n;i++)cin>>employee[i];
    for(int&i:apple)cin>>i;
    for(int i=1;i<=n;i++){
        int modded = c%l;
        int iter = 0;
        for(int jump=131072;jump;jump/=2){
            if(iter+jump>n)continue;
            if((l+employee[i]-employee[(n-iter-jump+i)%n +1])%l < modded)iter+=jump;
        }
        iter++;
        if(iter==n+1){
            adj[i] = {i,(c/l)*l + l};
            continue;
        }
        adj[i] = {(n-iter+i)%n +1,(c/l)*l + (l+employee[i]-employee[(n-iter+i)%n +1])%l};
    }
    vector<vector<pair<int,int>>> eqn(n+1);
    for(int&i:apple){
        int start = -1;
        if(i<employee[1])start = n;
        else {
            start = upper_bound(employee.begin()+1,employee.end(),i)-employee.begin()-1;
        }
        vector<pair<int,int>> curr(n+1,{INF,INF});
        function<void (int,int)> dfs = [&](int x,int tim){
            if(curr[x].second!=INF)return;
            if(curr[x].first!=INF)curr[x].second=tim-curr[x].first;
            else curr[x].first = tim;
            dfs(adj[x].first,tim+adj[x].second);
        };
        dfs(start,(l+i-employee[start])%l);
        for(int i=1;i<=n;i++)eqn[i].emplace_back(curr[i]);
    }
    int q;
    cin >> q;
    for(int i=1;i<=q;i++){
        int v,t;
        cin >> v >> t;
        int ans = 0;
        for(auto[a,b]:eqn[v]){
            if(t<a)continue;
            ans+=(t-a)/b + 1;
        }
        cout << ans << '\n';
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 164 ms 173652 KB Output is correct
3 Correct 153 ms 173716 KB Output is correct
4 Correct 157 ms 173652 KB Output is correct
5 Correct 165 ms 173908 KB Output is correct
6 Correct 176 ms 173868 KB Output is correct
7 Correct 175 ms 173908 KB Output is correct
8 Correct 174 ms 173652 KB Output is correct
9 Correct 160 ms 174084 KB Output is correct
10 Correct 149 ms 173652 KB Output is correct
11 Correct 161 ms 173788 KB Output is correct
12 Correct 248 ms 174052 KB Output is correct
13 Correct 303 ms 173952 KB Output is correct
14 Correct 212 ms 173908 KB Output is correct
15 Correct 179 ms 173728 KB Output is correct
16 Correct 183 ms 173756 KB Output is correct
17 Correct 176 ms 173720 KB Output is correct
18 Correct 183 ms 173936 KB Output is correct
19 Correct 179 ms 173788 KB Output is correct
20 Correct 224 ms 173940 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1431 ms 8052 KB Output is correct
2 Runtime error 508 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 164 ms 173652 KB Output is correct
3 Correct 153 ms 173716 KB Output is correct
4 Correct 157 ms 173652 KB Output is correct
5 Correct 165 ms 173908 KB Output is correct
6 Correct 176 ms 173868 KB Output is correct
7 Correct 175 ms 173908 KB Output is correct
8 Correct 174 ms 173652 KB Output is correct
9 Correct 160 ms 174084 KB Output is correct
10 Correct 149 ms 173652 KB Output is correct
11 Correct 161 ms 173788 KB Output is correct
12 Correct 248 ms 174052 KB Output is correct
13 Correct 303 ms 173952 KB Output is correct
14 Correct 212 ms 173908 KB Output is correct
15 Correct 179 ms 173728 KB Output is correct
16 Correct 183 ms 173756 KB Output is correct
17 Correct 176 ms 173720 KB Output is correct
18 Correct 183 ms 173936 KB Output is correct
19 Correct 179 ms 173788 KB Output is correct
20 Correct 224 ms 173940 KB Output is correct
21 Correct 1431 ms 8052 KB Output is correct
22 Runtime error 508 ms 524288 KB Execution killed with signal 9
23 Halted 0 ms 0 KB -