| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 960745 |
2024-04-11T02:36:27 Z |
Pring |
Harvest (JOI20_harvest) |
C++17 |
|
5000 ms |
63356 KB |
#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
#ifdef MIKU
string dbmc = "\033[1;38;2;57;197;187m", dbrs = "\033[0m";
#define debug(x...) cout << dbmc << "[" << #x << "]: ", dout(x)
void dout() { cout << dbrs << endl; }
template <typename T, typename ...U>
void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); }
#else
#define debug(...) 39
#endif
// #define int long long
#define int __int128_t
#define ll __int128_t
#define lll __int128_t
#define fs first
#define sc second
#define mp make_pair
#define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++)
// using ll = long long;
// using lll = __int128_t;
typedef pair<int, int> pii;
typedef tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update> PBDS_TREE;
const int MXN = 200005;
int n, m, L, adf, a[MXN], b[MXN], q, qid[MXN];
ll qt[MXN];
int p[MXN], pt[MXN];
ll ans[MXN];
vector<pii> edge[MXN];
vector<int> qry[MXN];
bitset<MXN> vis;
PBDS_TREE tr[MXN];
// vector<int> tr[MXN];
ll lz[MXN];
istream &operator>>(istream &ss, __int128_t &x) {
long long y;
ss >> y;
x = y;
return ss;
}
ostream &operator<<(ostream &ss, __int128_t x) {
long long y = x;
ss << y;
return ss;
}
struct VSET {
bitset<MXN> b;
vector<int> v;
void init() {
b.reset();
v.clear();
}
void insert(int x) {
if (b[x]) return;
b[x] = true;
v.push_back(x);
}
void clear() {
for (auto &i : v) b[i] = false;
v.clear();
}
} sr;
struct BIT {
int n;
lll val[MXN];
void init(int _n) {
n = _n;
fill(val, val + n, 0);
}
void modify(int id, lll v) {
for (id++; id <= n; id += (id & -id)) val[id] += v;
}
lll query(int id) {
ll ans = 0;
for (; id > 0; id -= (id & -id)) ans += val[id];
return ans;
}
} B;
void PUT_TREE() {
FOR(i, 0, m) {
int pp = lower_bound(a, a + n, b[i]) - a - 1;
if (pp == -1) pp += n;
int x = (b[i] - a[pp] + L) % L;
debug(i, pp, x);
tr[pp].insert(x);
// tr[pp].push_back(x);
}
}
void GET_P() {
vector<pii> v;
FOR(i, 0, n) v.push_back(mp(a[i], i));
FOR(i, 0, n) v.push_back(mp(a[i] + L, i));
FOR(i, 0, n) {
auto pp = prev(lower_bound(v.begin(), v.end(), mp(a[i] + L - adf % L, MXN)));
p[i] = pp -> sc;
pt[i] = adf / L * L + (a[i] + L - pp -> fs);
debug(i, p[i], pt[i]);
edge[p[i]].push_back(mp(pt[i], i));
}
}
void CALC_CYC(vector<ll> &v, vector<pair<ll, int>> &vq, ll C) {
for (auto [Q, aid] : vq) {
int sum = 0;
for (auto &i : v) {
if (Q - i < 0) break;
// ans[aid] += (Q - i) / C + 1;
sum += (Q - i) - (Q - i) % C + C;
}
ans[aid] += sum / C;
}
return;
int n = v.size(), m = vq.size();
vector<lll> p(1, 0), pc(1, 0);
FOR(i, 0, n) {
p.push_back(p.back() + v[i]);
pc.push_back(pc.back() + (C - v[i] % C) % C);
}
B.init(n);
vector<pair<ll, int>> dist;
FOR(i, 0, n) dist.push_back(mp((v[i] ? v[i] - 1 : LLONG_MAX), i));
FOR(i, 0, m) assert(vq[i].fs >= 0);
FOR(i, 0, m) dist.push_back(mp(vq[i].fs % C, -i - 1));
sort(dist.begin(), dist.end());
for (auto &[t, id] : dist) {
if (id < 0) {
id = -id - 1;
auto [Q, aid] = vq[id];
int s = upper_bound(v.begin(), v.end(), Q) - v.begin();
if (s == 0) continue;
lll x = Q * s - p[s] - (pc[s] + t * s + B.query(s));
assert(x % C == 0);
// debug(Q, s, aid, x, x / C);
debug(x, C, x / C);
ans[aid] += x / C + s;
} else {
B.modify(id, -C);
}
}
}
namespace JELLY {
void MERGE(int rt, int id, ll w) {
if (tr[rt].size() >= tr[id].size()) {
for (auto i : tr[id]) tr[rt].insert(i + lz[id] + w - lz[rt]);
} else {
lz[id] += w;
for (auto i : tr[rt]) tr[id].insert(i + lz[rt] - lz[id]);
tr[rt].swap(tr[id]);
swap(lz[rt], lz[id]);
}
tr[id].clear();
}
void GET_SR() {
vector<int> ind(n), ban(n);
queue<int> q;
FOR(i, 0, n) ind[p[i]]++;
FOR(i, 0, n) if (ind[i] == 0) q.push(i);
while (q.size()) {
int id = q.front();
q.pop();
ban[id] = true;
if (--ind[p[id]] == 0) q.push(p[id]);
}
FOR(i, 0, n) {
if (ban[i]) continue;
sr.insert(i);
int now = i;
while (!ban[now]) {
ban[now] = true;
now = p[now];
}
}
}
void CALC_MERGE(int id, bool f = true) {
vis[id] = true;
for (auto &[w, i] : edge[id]) {
if (vis[i]) continue;
CALC_MERGE(i);
MERGE(id, i, w);
}
if (f) {
for (auto &i : qry[id]) {
ll Q = qt[i] - lz[id];
// for (auto j : tr[id]) {
// if (j <= Q) ans[i]++;
// }
int x = tr[id].order_of_key(Q + 1);
debug(i, x);
ans[i] += x;
}
}
}
void SOLVE(int rt) {
// debug(rt);
CALC_MERGE(rt, false);
vector<ll> v;
for (auto i : tr[rt]) v.push_back(i + lz[rt]);
vector<pair<ll, int>> vq;
vector<int> cyc;
cyc.push_back(rt);
while (p[cyc.back()] != rt) cyc.push_back(p[cyc.back()]);
int acc = 0;
FOR(i, 0, cyc.size()) {
debug(cyc[i]);
for (auto &j : qry[cyc[i]]) {
debug(j);
// vq.push_back(mp(qt[j] - acc, j));
if (qt[j] - acc >= 0) vq.push_back(mp(qt[j] - acc, j));
}
acc += pt[cyc[i]];
}
CALC_CYC(v, vq, acc);
}
}
void miku() {
cin >> n >> m >> L >> adf;
FOR(i, 0, n) cin >> a[i];
FOR(i, 0, m) cin >> b[i];
cin >> q;
FOR(i, 0, q) {
cin >> qid[i] >> qt[i];
qid[i]--;
qry[qid[i]].push_back(i);
}
PUT_TREE();
GET_P();
JELLY::GET_SR();
for (auto &i : sr.v) {
debug(i);
JELLY::SOLVE(i);
}
FOR(i, 0, q) {
assert(ans[i] <= LLONG_MAX);
cout << (long long) ans[i] << '\n';
}
}
int32_t main() {
cin.tie(0) -> sync_with_stdio(false);
cin.exceptions(cin.failbit);
miku();
return 0;
}
Compilation message
harvest.cpp: In function 'void PUT_TREE()':
harvest.cpp:13:20: warning: statement has no effect [-Wunused-value]
13 | #define debug(...) 39
| ^~
harvest.cpp:94:9: note: in expansion of macro 'debug'
94 | debug(i, pp, x);
| ^~~~~
harvest.cpp: In function 'void GET_P()':
harvest.cpp:13:20: warning: statement has no effect [-Wunused-value]
13 | #define debug(...) 39
| ^~
harvest.cpp:108:9: note: in expansion of macro 'debug'
108 | debug(i, p[i], pt[i]);
| ^~~~~
harvest.cpp: In function 'void CALC_CYC(std::vector<__int128>&, std::vector<std::pair<__int128, __int128> >&, __int128)':
harvest.cpp:13:20: warning: statement has no effect [-Wunused-value]
13 | #define debug(...) 39
| ^~
harvest.cpp:145:13: note: in expansion of macro 'debug'
145 | debug(x, C, x / C);
| ^~~~~
harvest.cpp: In function 'void JELLY::CALC_MERGE(__int128, bool)':
harvest.cpp:13:20: warning: statement has no effect [-Wunused-value]
13 | #define debug(...) 39
| ^~
harvest.cpp:200:17: note: in expansion of macro 'debug'
200 | debug(i, x);
| ^~~~~
harvest.cpp: In function 'void JELLY::SOLVE(__int128)':
harvest.cpp:13:20: warning: statement has no effect [-Wunused-value]
13 | #define debug(...) 39
| ^~
harvest.cpp:216:13: note: in expansion of macro 'debug'
216 | debug(cyc[i]);
| ^~~~~
harvest.cpp:13:20: warning: statement has no effect [-Wunused-value]
13 | #define debug(...) 39
| ^~
harvest.cpp:218:17: note: in expansion of macro 'debug'
218 | debug(j);
| ^~~~~
harvest.cpp: In function 'void miku()':
harvest.cpp:13:20: warning: statement has no effect [-Wunused-value]
13 | #define debug(...) 39
| ^~
harvest.cpp:242:9: note: in expansion of macro 'debug'
242 | debug(i);
| ^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
49076 KB |
Output is correct |
| 2 |
Correct |
19 ms |
49440 KB |
Output is correct |
| 3 |
Correct |
100 ms |
49740 KB |
Output is correct |
| 4 |
Correct |
22 ms |
49436 KB |
Output is correct |
| 5 |
Correct |
18 ms |
49700 KB |
Output is correct |
| 6 |
Correct |
21 ms |
49956 KB |
Output is correct |
| 7 |
Correct |
20 ms |
49700 KB |
Output is correct |
| 8 |
Correct |
18 ms |
49632 KB |
Output is correct |
| 9 |
Correct |
19 ms |
49628 KB |
Output is correct |
| 10 |
Correct |
19 ms |
49632 KB |
Output is correct |
| 11 |
Correct |
19 ms |
49628 KB |
Output is correct |
| 12 |
Correct |
21 ms |
49696 KB |
Output is correct |
| 13 |
Correct |
73 ms |
50052 KB |
Output is correct |
| 14 |
Correct |
59 ms |
49776 KB |
Output is correct |
| 15 |
Correct |
19 ms |
49700 KB |
Output is correct |
| 16 |
Correct |
19 ms |
49700 KB |
Output is correct |
| 17 |
Correct |
19 ms |
49672 KB |
Output is correct |
| 18 |
Correct |
21 ms |
49696 KB |
Output is correct |
| 19 |
Correct |
21 ms |
49696 KB |
Output is correct |
| 20 |
Correct |
21 ms |
49700 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5086 ms |
63356 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
49076 KB |
Output is correct |
| 2 |
Correct |
19 ms |
49440 KB |
Output is correct |
| 3 |
Correct |
100 ms |
49740 KB |
Output is correct |
| 4 |
Correct |
22 ms |
49436 KB |
Output is correct |
| 5 |
Correct |
18 ms |
49700 KB |
Output is correct |
| 6 |
Correct |
21 ms |
49956 KB |
Output is correct |
| 7 |
Correct |
20 ms |
49700 KB |
Output is correct |
| 8 |
Correct |
18 ms |
49632 KB |
Output is correct |
| 9 |
Correct |
19 ms |
49628 KB |
Output is correct |
| 10 |
Correct |
19 ms |
49632 KB |
Output is correct |
| 11 |
Correct |
19 ms |
49628 KB |
Output is correct |
| 12 |
Correct |
21 ms |
49696 KB |
Output is correct |
| 13 |
Correct |
73 ms |
50052 KB |
Output is correct |
| 14 |
Correct |
59 ms |
49776 KB |
Output is correct |
| 15 |
Correct |
19 ms |
49700 KB |
Output is correct |
| 16 |
Correct |
19 ms |
49700 KB |
Output is correct |
| 17 |
Correct |
19 ms |
49672 KB |
Output is correct |
| 18 |
Correct |
21 ms |
49696 KB |
Output is correct |
| 19 |
Correct |
21 ms |
49696 KB |
Output is correct |
| 20 |
Correct |
21 ms |
49700 KB |
Output is correct |
| 21 |
Execution timed out |
5086 ms |
63356 KB |
Time limit exceeded |
| 22 |
Halted |
0 ms |
0 KB |
- |
