# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
223574 | 2020-04-15T13:43:02 Z | gs14004 | Harvest (JOI20_harvest) | C++17 | 5000 ms | 22836 KB |
#include <bits/stdc++.h> #define sz(v) ((int)(v).size()) #define all(v) (v).begin(), (v).end() using namespace std; using lint = long long; using pi = pair<lint, lint>; const int MAXN = 200005; const int MAXT = 530000; int n, m, q, l, c; vector<pi> v[MAXN]; vector<pi> gph[MAXN]; vector<int> deliv[MAXN]; int nxt[MAXN]; lint len[MAXN]; lint cyclen[MAXN], ans[MAXN]; bool vis[MAXN]; lint dfs(int x, lint d, lint isCycle){ if(vis[x]) return 0; vis[x] = 1; lint ret = 0; for(auto &j : deliv[x]){ if(d >= j){ ret += 1; if(isCycle) ret += (d - j) / isCycle; } } for(auto &[w, v] : gph[x]){ ret += dfs(v, d - w, isCycle); } return ret; } void solve(){ vector<int> indeg(n); for(int i=0; i<n; i++){ gph[nxt[i]].emplace_back(len[i], i); indeg[nxt[i]]++; } queue<int> que; for(int i=0; i<n; i++){ if(!indeg[i]){ que.push(i); } } while(sz(que)){ int i = que.front(); que.pop(); indeg[nxt[i]]--; if(indeg[nxt[i]] == 0) que.push(nxt[i]); } for(int i=0; i<n; i++){ if(indeg[i]){ lint tot = len[i]; for(int j=nxt[i]; j!=i; j=nxt[j]) tot += len[j]; for(int j=i; indeg[j]; j=nxt[j]){ cyclen[j] = tot; indeg[j] = 0; } } } for(int i=0; i<n; i++){ for(auto &j : v[i]){ memset(vis, 0, sizeof(vis)); ans[j.second] = dfs(i, j.first, cyclen[i]); } } } int main(){ scanf("%d %d %d %d",&n,&m,&l,&c); vector<int> a(n), b(m), idx(n); for(int i=0; i<n; i++){ scanf("%d",&a[i]); a[i] = (l - a[i]) % l; idx[i] = i; } for(int i=0; i<m; i++){ scanf("%d",&b[i]); b[i] = (l - b[i]) % l; } reverse(all(a)); reverse(all(idx)); reverse(all(b)); if(a.back() == 0){ rotate(a.begin(), a.end() - 1, a.end()); rotate(idx.begin(), idx.end() - 1, idx.end()); } scanf("%d",&q); for(int i=0; i<q; i++){ int x; lint t; scanf("%d %lld",&x,&t); x = idx[x - 1]; v[x].emplace_back(t, i); } for(int i=0; i<n; i++){ int nxtpos = (c + a[i]) % l; nxt[i] = lower_bound(all(a), nxtpos) - a.begin(); lint newpos = (c + a[i]) + (nxt[i] == n ? (a[0] + l) : a[nxt[i]]) - nxtpos; len[i] = newpos - a[i]; if(nxt[i] == n) nxt[i] = 0; } for(int i=0; i<m; i++){ int nxt = lower_bound(all(a), b[i]) - a.begin(); if(nxt == n) nxt = 0; int delay = (a[nxt] - b[i] + l) % l; deliv[nxt].push_back(delay); } solve(); for(int i=0; i<q; i++) printf("%lld\n", ans[i]); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 33 ms | 14848 KB | Output is correct |
2 | Correct | 36 ms | 15232 KB | Output is correct |
3 | Correct | 132 ms | 15096 KB | Output is correct |
4 | Correct | 39 ms | 15104 KB | Output is correct |
5 | Correct | 75 ms | 15232 KB | Output is correct |
6 | Correct | 76 ms | 15232 KB | Output is correct |
7 | Correct | 77 ms | 15232 KB | Output is correct |
8 | Correct | 32 ms | 15104 KB | Output is correct |
9 | Correct | 32 ms | 15104 KB | Output is correct |
10 | Correct | 33 ms | 15104 KB | Output is correct |
11 | Correct | 34 ms | 15104 KB | Output is correct |
12 | Correct | 130 ms | 15232 KB | Output is correct |
13 | Correct | 242 ms | 15332 KB | Output is correct |
14 | Correct | 85 ms | 15228 KB | Output is correct |
15 | Correct | 58 ms | 15224 KB | Output is correct |
16 | Correct | 58 ms | 15104 KB | Output is correct |
17 | Correct | 55 ms | 15104 KB | Output is correct |
18 | Correct | 59 ms | 15104 KB | Output is correct |
19 | Correct | 60 ms | 15224 KB | Output is correct |
20 | Correct | 62 ms | 15104 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 5097 ms | 22836 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 33 ms | 14848 KB | Output is correct |
2 | Correct | 36 ms | 15232 KB | Output is correct |
3 | Correct | 132 ms | 15096 KB | Output is correct |
4 | Correct | 39 ms | 15104 KB | Output is correct |
5 | Correct | 75 ms | 15232 KB | Output is correct |
6 | Correct | 76 ms | 15232 KB | Output is correct |
7 | Correct | 77 ms | 15232 KB | Output is correct |
8 | Correct | 32 ms | 15104 KB | Output is correct |
9 | Correct | 32 ms | 15104 KB | Output is correct |
10 | Correct | 33 ms | 15104 KB | Output is correct |
11 | Correct | 34 ms | 15104 KB | Output is correct |
12 | Correct | 130 ms | 15232 KB | Output is correct |
13 | Correct | 242 ms | 15332 KB | Output is correct |
14 | Correct | 85 ms | 15228 KB | Output is correct |
15 | Correct | 58 ms | 15224 KB | Output is correct |
16 | Correct | 58 ms | 15104 KB | Output is correct |
17 | Correct | 55 ms | 15104 KB | Output is correct |
18 | Correct | 59 ms | 15104 KB | Output is correct |
19 | Correct | 60 ms | 15224 KB | Output is correct |
20 | Correct | 62 ms | 15104 KB | Output is correct |
21 | Execution timed out | 5097 ms | 22836 KB | Time limit exceeded |
22 | Halted | 0 ms | 0 KB | - |