| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 902894 |
2024-01-11T04:23:45 Z |
box |
Harvest (JOI20_harvest) |
C++17 |
|
5000 ms |
486404 KB |
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
template <class T, class... U> void bug_h(const T& t, const U&... u) { cerr << t; ((cerr << " | " << u), ...); cerr << endl; }
#define bug(...) cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]: ", bug_h(__VA_ARGS__)
#else
#define cerr if (0) cerr
#define bug(...)
#endif
#define ar array
#define all(v) std::begin(v), std::end(v)
#define sz(v) int(std::size(v))
typedef long long i64;
typedef vector<int> vi;
typedef vector<i64> v64;
typedef pair<int, int> pi;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <class K> using oset = tree<K, null_type, less<K>, rb_tree_tag, tree_order_statistics_node_update>;
struct DS {
oset<pair<i64, int>> S; i64 tag = 0;
constexpr int size() { return sz(S); }
void insert(i64 v) { S.insert({v - tag, sz(S)}); }
void extend(i64 v) { tag += v; }
int num_leq(i64 v) { return S.order_of_key({v - tag, INT_MAX}); }
void pr() {
for (auto [k,v] : S) cout << k+tag << ' ';
cout << '\n';
}
};
void mrg_self(DS &me, DS &ds) {
if (me.size() < ds.size()) swap(me, ds);
for (auto [k, v] : exchange(ds.S, {})) me.insert(k+ds.tag);
}
i64 fdiv(i64 a, i64 b) {
return a/b - ((a^b) < 0 && a%b);
}
int N, M, L, C, Q;
vi A, B, P;
vector<vi> adj;
vector<DS> ds;
v64 D, pf;
vector<v64> orig;
vi done, on_cyc;
vector<vi> qry;
v64 T, ans;
vi nodes;
pi banned;
bool ban_cyc;
void dfs(int i, bool top) {
nodes.push_back(i);
done[i] = 1;
for (int j : adj[i]) {
if (!ban_cyc && pi(i,j) == banned) continue;
if (ban_cyc && on_cyc[j]) continue;
// bug("EDGE", i, j);
dfs(j, 0);
ds[j].extend(D[j]);
mrg_self(ds[i], ds[j]);
}
// cout << "\t\t\t" << i << ": ";
// ds[i].pr();
if (top) return;
for (auto x : qry[i]) {
ans[x] += ds[i].num_leq(T[x]);
// bug(x, T[x], ans[x]);
ds[i].pr();
}
// ds[i].extend(D[i]);
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
cin >> N >> M >> L >> C;
A = vi(N), B = vi(M);
for (auto &x : A) cin >> x;
for (auto &x : B) cin >> x;
orig.resize(N);
ds.resize(N);
for (auto x : B) {
int y = x;
if (y < A[0]) y += L;
int p = upper_bound(all(A), y)-begin(A)-1;
// bug(p, y-A[p]);
ds.at(p).insert(y-A[p]);
}
P = vi(N), D = v64(N);
adj.resize(N);
for (int i = 0; i < N; i++) {
int y = (A[i]-C)%L;
if (y < 0) y += L;
if (y < A[0]) y += L;
int p = upper_bound(all(A), y)-begin(A)-1;
assert(0 <= p && p < N);
P[i] = p;
D[i] = C + (y-A[p]);
// bug(i, P[i], D[i]);
adj.at(p).push_back(i);
}
cin >> Q;
qry.resize(N);
ans = T = v64(Q);
for (int i = 0; i < Q; i++) {
int v; cin >> v >> T[i], v--;
qry.at(v).push_back(i);
}
done = on_cyc = vi(N);
pf.resize(N);
for (int i = 0; i < N; i++) {
if (done[i]) continue;
int x = i, y = P.at(i);
while (x != y) x = P.at(x), y = P.at(P.at(y));
vi cyc;
do {
done[x] = 1;
cyc.push_back(x);
x = P[x];
} while (!done[x]);
i64 len = 0;
for (int x : cyc) {
pf[x] = len;
len += D[x];
}
for (auto x : cyc) on_cyc.at(x) = 1;
v64 upds;
int funny = cyc.back();
banned = {P.at(funny), funny};
ban_cyc = 1;
for (auto x : cyc) {
if (x == funny) ban_cyc = 0;
dfs(x, x != funny);
if (x != funny) for (auto [k, v] : ds[x].S) upds.push_back(k+ds[x].tag+len-pf.at(x));
}
vector<pair<i64, int>> qrys;
for (int x : cyc) for (int y : qry[x]) qrys.push_back({T[y]-pf.at(x), y});
sort(all(qrys));
sort(all(upds), greater<>());
DS ds; i64 con = 0;
for (auto [v, y] : qrys) {
while (sz(upds) && upds.back() <= v) {
// bug(upds.back());
ds.insert(upds.back()%len);
con += fdiv(upds.back(), len);
upds.pop_back();
}
// bug(y, v);
ans.at(y) += fdiv(v,len)*ds.size()-con+ds.num_leq(v%len);
}
}
for (auto x : ans) cout << x << '\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
608 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5027 ms |
486404 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
608 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
