| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 217093 |
2020-03-29T00:34:45 Z |
keko37 |
Harvest (JOI20_harvest) |
C++14 |
|
511 ms |
71160 KB |
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long llint;
const int MAXN = 200005;
const int LOG = 20;
llint n, m, L, C, q, cnt, nodes;
llint man[MAXN * 2], app[MAXN];
llint qind[MAXN], qtime[MAXN], qsol[MAXN];
llint par[MAXN], w[MAXN], is[MAXN], bio[MAXN];
vector <int> queries[MAXN], ring[MAXN], child[MAXN], dist[MAXN];
tree <llint, null_type , less_equal<llint> , rb_tree_tag, tree_order_statistics_node_update> st[MAXN], fen;
llint st_ofs[MAXN];
int lef[MAXN * LOG], rig[MAXN * LOG], tour[MAXN * LOG], root[MAXN];
void dfs (int x) {
bio[x] = 1;
if (bio[par[x]] == 0) {
dfs(par[x]);
} else if (bio[par[x]] == 1) {
int start = x;
do {
ring[cnt].push_back(x);
is[x] = 1;
x = par[x];
} while (x != start);
cnt++;
}
bio[x] = 2;
}
void build_graph () {
for (int i = 0; i < m; i++) {
int ind = lower_bound(man, man + 2*n, app[i] + L) - man - 1;
st[ind % n].insert(app[i] + L - man[ind]);
}
int Cq = C % L;
for (int i = 0; i < n; i++) {
int ind = upper_bound(man, man + 2*n, man[i + n] - Cq) - man - 1;
par[i] = ind % n;
w[i] = C + man[i + n] - man[ind] - Cq;
}
for (int i = 0; i < n; i++) {
if (bio[i] == 0) dfs(i);
}
for (int i = 0; i < n; i++) {
if (!is[i]) child[par[i]].push_back(i);
}
}
void subtree (int x) {
for (auto sus : child[x]) {
subtree(sus);
if (st[sus].size() > st[x].size()) {
swap(st[sus], st[x]);
swap(st_ofs[sus], st_ofs[x]);
}
for (auto val : st[sus]) {
st[x].insert(val + st_ofs[sus] - st_ofs[x]);
}
st[sus].clear();
}
if (!is[x]) {
for (auto u : queries[x]) {
qsol[u] = st[x].order_of_key(qtime[u] - st_ofs[x] + 1);
}
st_ofs[x] += w[x];
}
}
int build (int len) {
int curr = ++nodes;
if (len == 1) return curr;
lef[curr] = build(len / 2);
rig[curr] = build(len / 2);
return curr;
}
int update (int x, int pos, int lo, int hi) {
int curr = ++nodes;
if (lo == hi) {
tour[curr] = tour[x] + 1;
return curr;
}
if (pos <= (lo + hi) / 2) {
lef[curr] = update(lef[x], pos, lo, (lo + hi) / 2);
rig[curr] = rig[x];
} else {
lef[curr] = lef[x];
rig[curr] = update(rig[x], pos, (lo + hi) / 2 + 1, hi);
}
tour[curr] = tour[lef[curr]] + tour[rig[curr]];
return curr;
}
int upit (int x, int from, int to, int lo, int hi) {
if (from <= lo && hi <= to) return tour[x];
if (hi < from || to < lo) return 0;
return upit(lef[x], from, to, lo, (lo + hi) / 2) + upit(rig[x], from, to, (lo + hi) / 2 + 1, hi);
}
void solve_comp (int comp) {
vector <llint> d;
llint D = 0;
for (int i = (int)ring[comp].size() - 1; i >= 0; i--) {
int r = ring[comp][i];
subtree(r);
if (i + 1 != ring[comp].size()) D += w[r];
for (auto len : st[r]) {
d.push_back(len + st_ofs[r] + D);
dist[r].push_back(len + st_ofs[r] + D);
}
}
D += w[ring[comp].back()];
sort(d.begin(), d.end());
vector <llint> sum(d.size()), ost(d.size());
for (int i = 0; i < d.size(); i++) {
sum[i] = d[i] / D;
if (i > 0) sum[i] += sum[i - 1];
ost[i] = d[i] % D;
}
sort(ost.begin(), ost.end());
ost.erase(unique(ost.begin(), ost.end()), ost.end());
int len = 1;
while (len < ost.size()) len *= 2;
root[0] = build(len);
for (int i = 0; i < d.size(); i++) {
int pos = lower_bound(ost.begin(), ost.end(), d[i] % D) - ost.begin();
root[i + 1] = update(root[i], pos, 0, len - 1);
}
fen.clear();
llint ofs = 0;
for (int i = 0; i < ring[comp].size(); i++) {
int r = (i == 0 ? ring[comp].back() : ring[comp][i - 1]);
if (i != 0) {
for (auto path : dist[r]) {
int pos = lower_bound(d.begin(), d.end(), path) - d.begin();
fen.insert(pos);
}
}
for (auto u : queries[r]) {
llint t = qtime[u] - ofs;
int pos = upper_bound(d.begin(), d.end(), t) - d.begin() - 1;
if (pos >= 0) {
qsol[u] += (pos + 1) * (t / D + 1) - sum[pos];
int ostQ = upper_bound(ost.begin(), ost.end(), t % D) - ost.begin();
qsol[u] -= upit(root[pos + 1], min(max(ostQ, 0), len - 1), len - 1, 0, len - 1);
}
pos = upper_bound(d.begin(), d.end(), t + D) - d.begin() - 1;
qsol[u] += fen.order_of_key(pos + 1);
}
ofs += w[r];
}
}
int main () {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m >> L >> C;
for (int i = 0; i < n; i++) {
cin >> man[i];
man[i + n] = man[i] + L;
}
for (int i = 0; i < m; i++) {
cin >> app[i];
}
cin >> q;
for (int i = 0; i < q; i++) {
cin >> qind[i] >> qtime[i];
qind[i]--;
queries[qind[i]].push_back(i);
}
build_graph();
for (int i = 0; i < cnt; i++) solve_comp(i);
for (int i = 0; i < q; i++) {
cout << qsol[i] << '\n';
}
return 0;
}
Compilation message
harvest.cpp: In function 'void solve_comp(int)':
harvest.cpp:117:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (i + 1 != ring[comp].size()) D += w[r];
~~~~~~^~~~~~~~~~~~~~~~~~~~
harvest.cpp:127:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < d.size(); i++) {
~~^~~~~~~~~~
harvest.cpp:136:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (len < ost.size()) len *= 2;
~~~~^~~~~~~~~~~~
harvest.cpp:138:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < d.size(); i++) {
~~^~~~~~~~~~
harvest.cpp:145:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < ring[comp].size(); i++) {
~~^~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
41 ms |
38264 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
177 ms |
51944 KB |
Output is correct |
| 2 |
Correct |
511 ms |
70136 KB |
Output is correct |
| 3 |
Incorrect |
252 ms |
71160 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
41 ms |
38264 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
