| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 799930 |
2023-08-01T08:33:35 Z |
박영우(#10085) |
Harvest (JOI20_harvest) |
C++17 |
|
286 ms |
223928 KB |
#include <bits/stdc++.h>
#include <cassert>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<ll, ll> pii;
#define MAX 505050
#define MAXS 20
#define INF 1000000000000000001
#define bb ' '
#define ln '\n'
#define Ln '\n'
#define MOD 1000000007
struct fenwick {
ll N;
vector<ll> tree;
fenwick(ll N = 0) :N(N) { tree.resize(N + 1); }
void upd(ll i, ll x) { while (i <= N) { tree[i] += x, i += i & -i; } }
ll get(ll i) { ll ans = 0; while (i) { ans += tree[i], i -= i & -i; } return ans; }
ll get(ll l, ll r) { return get(r) - get(l - 1); }
};
ll N, M;
ll L, C;
ll A[MAX];
ll B[MAX];
ll nxt[MAX]; // next staff
ll cst[MAX]; // distance to nxt[i]
ll ccnt; // cycle count
vector<ll> cyc[MAX]; // cycles (last element is root)
ll topv[MAX]; // cycle number (only root)
ll croot[MAX]; // root of cycle
ll gp[MAX]; // component number (all vertex)
ll iscyc[MAX]; // 1 if cycle
ll cdis[MAX]; // distanct from cyc[0]
ll clen[MAX]; // length of cycle
vector<ll> sttime[MAX];
vector<ll> rsttime[MAX]; //real value
vector<ll> dv[MAX];
vector<ll> psum[MAX];
ll cycstart[MAX];
ll vis[MAX];
vector<ll> adj[MAX]; // tree
ll dep[MAX];
pii range[MAX];
ll cnt;
ll treein[MAX]; // first staff
ll appledep[MAX]; // apple depth
ll applenum[MAX]; // subtree apple number
ll ans[MAX]; // query answer
ll T[MAX]; // query T
ll V[MAX]; // query V
ll qdep[MAX];
void dfs(ll x) {
if (topv[x]) gp[x] = topv[x];
cnt++;
assert(cnt <= N);
range[x] = { cnt, cnt };
for (auto v : adj[x]) {
dep[v] = dep[x] + cst[v];
gp[v] = gp[x];
dfs(v);
applenum[x] += applenum[v];
range[x].second = max(range[x].second, range[v].second);
}
}
signed main() {
ios::sync_with_stdio(false), cin.tie(0);
cin >> N >> M >> L >> C;
ll i, j;
ll c = C % L;
vector<ll> v;
for (i = 1; i <= N; i++) cin >> A[i], v.push_back(A[i]);
for (i = 1; i <= N; i++) v.push_back(A[i] + L);
for (i = 1; i <= N; i++) {
ll ind = upper_bound(v.begin(), v.end(), A[i] - c + L) - v.begin();
ind--;
ind %= N;
if (ind < 0) ind += N;
nxt[i] = ind + 1;
cst[i] = A[i] - A[nxt[i]] + L;
cst[i] %= L;
ll d = C - cst[i];
if (d > 0) {
d = (d + L - 1) / L;
d *= L;
cst[i] += d;
}
}
for (i = 1; i <= N; i++) {
if (vis[i]) continue;
ll v = i;
vector<ll> path;
while (1) {
path.push_back(v);
vis[v] = 1;
if (vis[nxt[v]]) {
if (!iscyc[nxt[v]]) {
ccnt++;
while (path.size()) {
cyc[ccnt].push_back(path.back());
if (path.back() == nxt[v]) break;
path.pop_back();
}
reverse(cyc[ccnt].begin(), cyc[ccnt].end());
for (auto v : cyc[ccnt]) iscyc[v] = 1;
for (auto v : cyc[ccnt]) clen[ccnt] += cst[v];
ll pv = -1;
for (auto v : cyc[ccnt]) {
if (~pv) cdis[v] = cdis[pv] + cst[pv];
pv = v;
}
topv[cyc[ccnt].back()] = ccnt;
croot[ccnt] = cyc[ccnt].back();
}
break;
}
v = nxt[v];
}
}
for (i = 1; i <= M; i++) {
cin >> B[i];
ll ind = upper_bound(v.begin(), v.end(), B[i]) - v.begin() - 1;
ind %= N;
if (ind < 0) ind += N;
ind++;
treein[i] = ind;
appledep[i] = B[i] - A[ind];
if (appledep[i] < 0) appledep[i] += L;
applenum[ind]++;
}
for (i = 1; i <= N; i++) if (!topv[i]) adj[nxt[i]].push_back(i);
for (i = 1; i <= N; i++) if (topv[i]) dfs(i);
for (i = 1; i <= M; i++) appledep[i] += dep[treein[i]];
ll Q;
cin >> Q;
vector<ll> qv, av;
for (i = 1; i <= Q; i++) cin >> V[i] >> T[i], qv.push_back(i), ans[i] = applenum[V[i]], qdep[i] = dep[V[i]] + T[i];
sort(qv.begin(), qv.end(), [&](ll i, ll j) {return qdep[i] > qdep[j]; });
fenwick fen(N);
for (i = 1; i <= M; i++) av.push_back(i);
sort(av.begin(), av.end(), [&](ll i, ll j) {return appledep[i] > appledep[j]; });
ll ptr = 0;
for (auto q : qv) {
while (ptr < av.size() && qdep[q] < appledep[av[ptr]]) fen.upd(range[treein[av[ptr++]]].first, 1);
ans[q] -= fen.get(range[V[q]].first, range[V[q]].second);
}
for (i = 1; i <= M; i++) sttime[gp[treein[i]]].push_back(appledep[i] + cst[croot[gp[treein[i]]]]);
for (i = 1; i <= ccnt; i++) {
sort(sttime[i].begin(), sttime[i].end());
cycstart[i] = sttime[i][0];
for (auto& v : sttime[i]) v -= cycstart[i];
rsttime[i] = sttime[i];
for (auto& v : sttime[i]) {
dv[i].push_back(v / clen[i]);
v %= clen[i];
}
sort(dv[i].begin(), dv[i].end());
psum[i] = dv[i];
psum[0] = dv[0];
for (j = 1; j < dv[i].size(); j++) psum[i][j] += psum[i][j - 1];
}
for (i = 1; i <= Q; i++) {
ll v = V[i];
ll t = T[i];
ll cn = gp[v];
if (sttime[cn].empty()) continue;
if (!iscyc[v]) continue;
t -= cdis[v];
t -= cycstart[cn];
if (t < 0) continue;
ll rot = t / clen[cn];
ans[i] += rot * sttime[cn].size();
t -= rot * clen[cn];
ll ind = upper_bound(sttime[cn].begin(), sttime[cn].end(), t) - sttime[cn].begin();
ans[i] += ind;
ll rind = lower_bound(dv[cn].begin(), dv[cn].end(), rot) - dv[cn].begin();
if (rind > 0) ans[i] -= psum[cn][rind - 1];
ans[i] -= ((ll)dv[cn].size() - rind) * rot;
}
for (i = 1; i <= Q; i++) cout << ans[i] << Ln;
}
Compilation message
harvest.cpp: In function 'int main()':
harvest.cpp:148:14: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
148 | while (ptr < av.size() && qdep[q] < appledep[av[ptr]]) fen.upd(range[treein[av[ptr++]]].first, 1);
| ~~~~^~~~~~~~~~~
harvest.cpp:164:17: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
164 | for (j = 1; j < dv[i].size(); j++) psum[i][j] += psum[i][j - 1];
| ~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
43 ms |
71700 KB |
Output is correct |
| 2 |
Runtime error |
97 ms |
146368 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
132 ms |
83224 KB |
Output is correct |
| 2 |
Runtime error |
286 ms |
223928 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
43 ms |
71700 KB |
Output is correct |
| 2 |
Runtime error |
97 ms |
146368 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
