| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 800011 |
2023-08-01T09:20:41 Z |
박영우(#10085) |
Harvest (JOI20_harvest) |
C++17 |
|
5000 ms |
78020 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<int, int> pii;
#define MAX 505050
#define MAXS 20
#define INF 1000000000000000001
#define bb ' '
#define ln '\n'
#define Ln '\n'
#define MOD 1000000007
const int DEBUG = 0;
const int DEBUG2 = 0;
const int NAIVE = 1;
struct fenwick {
int N;
vector<int> tree;
fenwick(int N = 0) :N(N) { tree.resize(N + 1); }
void upd(int i, int x) { if (DEBUG2) cout << 'u' << i << bb << x << ln; while (i <= N) { tree[i] += x, i += i & -i; } }
int get(int i) { int ans = 0; while (i) { ans += tree[i], i -= i & -i; } return ans; }
int get(int l, int r) { if (DEBUG2) cout << 'd' << l << bb << r << ln; return get(r) - get(l - 1); }
};
int N, M, Q;
ll L, C;
ll A[MAX];
ll B[MAX];
int nxt[MAX]; // next staff
ll cst[MAX]; // distance to nxt[i]
int ccnt; // cycle count
vector<int> cyc[MAX]; // cycles (last element is root)
int topv[MAX]; // cycle number (only root)
int croot[MAX]; // root of cycle
int gp[MAX]; // component number (all vertex)
int 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];
int vis[MAX];
vector<int> adj[MAX]; // tree
ll dep[MAX];
pii range[MAX];
int cnt;
int treein[MAX]; // first staff
ll appledep[MAX]; // apple depth
int applenum[MAX]; // subtree apple number
ll ans[MAX]; // query answer
ll T[MAX]; // query T
int V[MAX]; // query V
ll qdep[MAX];
void dfs(int x) {
if (topv[x]) gp[x] = topv[x];
cnt++;
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);
int i, j;
if (!DEBUG) {
cin >> N >> M >> L >> C;
for (i = 1; i <= N; i++) cin >> A[i];
for (i = 1; i <= M; i++) cin >> B[i];
cin >> Q;
for (i = 1; i <= Q; i++) cin >> V[i] >> T[i];
}
else {
cin >> N >> M >> L >> C;
for (i = 1; i <= N; i++) A[i] = i;
for (j = 1; j <= M; j++) B[i] = N + j;
cin >> Q;
for (i = 1; i <= Q; i++) V[i] = i, T[i] = rand();
}
int c = C % L;
vector<ll> v;
for (i = 1; i <= N; i++) v.push_back(A[i]);
for (i = 1; i <= N; i++) v.push_back(A[i] + L);
for (i = 1; i <= N; i++) {
int 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;
int v = i;
vector<int> 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];
int 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++) {
int 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]];
vector<int> qv, av;
for (i = 1; i <= Q; i++) qv.push_back(i), ans[i] = applenum[V[i]], qdep[i] = dep[V[i]] + T[i];
sort(qv.begin(), qv.end(), [&](int i, int j) {return qdep[i] > qdep[j]; });
fenwick fen(N);
for (i = 1; i <= M; i++) av.push_back(i);
sort(av.begin(), av.end(), [&](int i, int j) {return appledep[i] > appledep[j]; });
int 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++) {
if (sttime[i].empty()) continue;
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];
for (j = 1; j < dv[i].size(); j++) psum[i][j] += psum[i][j - 1];
}
for (i = 1; i <= Q; i++) {
int v = V[i];
ll t = T[i];
int cn = gp[v];
if (sttime[cn].empty()) continue;
if (!iscyc[v]) continue;
t -= cdis[v];
t -= cycstart[cn];
if (t < 0) continue;
if (NAIVE) {
for (auto tt : rsttime[cn]) {
if (t >= tt) {
t -= tt;
ans[i] += t / clen[cn] + 1;
t += tt;
}
}
}
else {
ll rot = t / clen[cn];
ans[i] += rot * sttime[cn].size();
t -= rot * clen[cn];
int ind = upper_bound(rsttime[cn].begin(), rsttime[cn].end(), t) - rsttime[cn].begin();
ans[i] += ind;
int 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:160:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
160 | while (ptr < av.size() && qdep[q] <= appledep[av[ptr]]) fen.upd(range[treein[av[ptr++]]].first, 1);
| ~~~~^~~~~~~~~~~
harvest.cpp:176:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
176 | for (j = 1; j < dv[i].size(); j++) psum[i][j] += psum[i][j - 1];
| ~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
64 ms |
71748 KB |
Output is correct |
| 2 |
Correct |
37 ms |
72268 KB |
Output is correct |
| 3 |
Correct |
116 ms |
72232 KB |
Output is correct |
| 4 |
Correct |
37 ms |
72252 KB |
Output is correct |
| 5 |
Incorrect |
36 ms |
72412 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5044 ms |
78020 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
64 ms |
71748 KB |
Output is correct |
| 2 |
Correct |
37 ms |
72268 KB |
Output is correct |
| 3 |
Correct |
116 ms |
72232 KB |
Output is correct |
| 4 |
Correct |
37 ms |
72252 KB |
Output is correct |
| 5 |
Incorrect |
36 ms |
72412 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
