QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #444140 | #8648. Tower | green_gold_dog# | 0 | 1197ms | 137420kb | C++23 | 9.2kb | 2024-06-15 17:29:20 | 2024-06-15 17:29:20 |
Judging History
answer
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,sse,sse2,sse3,ssse3,sse4,abm,popcnt,mmx")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
typedef long double ldb;
typedef complex<double> cd;
constexpr ll INF64 = 2'000'000'000'000'000'000, INF32 = 1'000'000'000'000, MOD = 1'000'000'007;
constexpr db PI = acos(-1);
constexpr bool IS_FILE = false, IS_TEST_CASES = false;
random_device rd;
mt19937 rnd32(rd());
mt19937_64 rnd64(rd());
template<typename T>
bool assign_max(T& a, T b) {
if (b > a) {
a = b;
return true;
}
return false;
}
template<typename T>
bool assign_min(T& a, T b) {
if (b < a) {
a = b;
return true;
}
return false;
}
template<typename T>
T square(T a) {
return a * a;
}
template<>
struct std::hash<pair<ll, ll>> {
ll operator() (pair<ll, ll> p) const {
return ((__int128)p.first * MOD + p.second) % INF64;
}
};
struct Node {
ll tree, ms, madd, maddp;
ll l, r;
Node *nl = nullptr, *nr = nullptr;
Node(ll l, ll r): l(l), r(r) {
tree = 0;
ms = -1;
madd = 0;
maddp = 0;
}
void make_sons() {
if (nl != nullptr) {
return;
}
ll mid = (l + r) / 2;
nl = new Node(l, mid);
nr = new Node(mid, r);
}
void set(ll x) {
if (x == -1) {
return;
}
tree = x * (r - l);
madd = 0;
maddp = 0;
ms = x;
}
void add(ll x) {
tree += x * (r - l);
madd += x;
}
void addp(ll x) {
tree += x * (r - l) * (r - l - 1) / 2;
maddp += x;
}
void push() {
make_sons();
ll mid = (l + r) / 2;
nl->set(ms);
nr->set(ms);
ms = -1;
nl->add(madd);
nr->add(madd);
madd = 0;
nr->add(maddp * (mid - l));
nl->addp(maddp);
nr->addp(maddp);
maddp = 0;
}
ll get(ll x) {
if (x < l || r <= x) {
return 0;
}
if (r - l == 1) {
return tree;
}
push();
return nl->get(x) + nr->get(x);
}
void set(ll ql, ll qr, ll x) {
if (ql <= l && r <= qr) {
set(x);
return;
}
if (qr <= l || r <= ql) {
return;
}
push();
nl->set(ql, qr, x);
nr->set(ql, qr, x);
tree = nl->tree + nr->tree;
}
void add(ll ql, ll qr, ll x) {
if (ql <= l && r <= qr) {
add(x);
return;
}
if (qr <= l || r <= ql) {
return;
}
push();
nl->add(ql, qr, x);
nr->add(ql, qr, x);
tree = nl->tree + nr->tree;
}
void addp(ll ql, ll qr, ll x, ll st) {
if (ql <= l && r <= qr) {
add(st);
addp(x);
return;
}
if (qr <= l || r <= ql) {
return;
}
push();
ll mid = (l + r) / 2;
nl->addp(ql, qr, x, st);
if (ql <= mid) {
st += (mid - ql) * x;
}
nr->addp(ql, qr, x, st);
tree = nl->tree + nr->tree;
}
};
struct segment_tree {
Node *root;
segment_tree(ll n) {
root = new Node(0, n);
}
ll get(ll x) {
return root->get(x);
}
void set(ll l, ll r, ll x) {
root->set(l, r, x);
}
void add(ll l, ll r, ll x) {
root->add(l, r, x);
}
void addp(ll l, ll r, ll x, ll st = 0) {
root->addp(l, r, x, st);
}
};
void solve() {
ll n, q, d, a, b;
cin >> n >> q >> d >> a >> b;
ll cp = min(a * d, b);
ll cph = b - cp;
vector<pair<ll, ll>> segs(n);
map<ll, vector<tuple<ll, ll, ll>>> m;
for (ll i = 0; i < n; i++) {
cin >> segs[i].first >> segs[i].second;
ll b1 = segs[i].first / d, b2 = segs[i].second / d;
if (b1 == b2) {
m[b1].emplace_back(0, segs[i].first % d, segs[i].second % d);
m[b1 + 1].emplace_back(1, q, 0);
}
if (b1 + 1 == b2) {
m[b1].emplace_back(0, segs[i].first % d, d - 1);
m[b2].emplace_back(0, 0, segs[i].second % d);
m[b2 + 1].emplace_back(1, q, 0);
}
if (b1 + 1 < b2) {
m[b1].emplace_back(0, segs[i].first % d, d - 1);
m[b1 + 1].emplace_back(0, 0, d - 1);
}
}
vector<ll> ans(q + 1, -1);
for (ll i = 0; i < q; i++) {
ll x;
cin >> x;
m[x / d].emplace_back(1, i, x % d);
}
ll lst = 0;
segment_tree st(d);
st.set(0, 1, 0);
st.set(1, d, INF64);
deque<pair<ll, ll>> zs;
m[0].emplace_back(1, q, 0);
zs.emplace_back(1, d - 1);
ll last = INF64;
ll pbad = 0;
while (!m.empty()) {
auto[now, op] = *m.begin();
m.erase(m.begin());
st.add(0, d, (now - lst) * cp);
lst = now;
st.add(0, pbad, cph);
ll bsuff = d;
deque<pair<ll, ll>> nzs;
ll npbad;
for (auto[t, l, r] : op) {
if (t != 0) {
continue;
}
assign_min(bsuff, r + 1);
assign_max(npbad, l);
st.set(l, r + 1, INF64);
nzs.emplace_back(l, r);
}
st.add(max(pbad, bsuff), d, cph);
pbad = npbad;
deque<pair<ll, ll>> nnzs = nzs;
vector<pair<ll, ll>> rseg;
while (!zs.empty()) {
auto[l, r] = zs.front();
zs.pop_front();
while (!nnzs.empty() && nnzs.front().first <= r) {
auto[nl, nr] = nnzs.front();
nnzs.pop_front();
if (nr < l) {
continue;
}
if (nl > l) {
rseg.emplace_back(l, nl - 1);
l = nl;
}
if (nr > r) {
nnzs.emplace_front(r + 1, nr);
}
l = nr + 1;
}
if (l <= r) {
rseg.emplace_back(l, r);
}
}
for (auto[l, r] : rseg) {
ll fe = (l == 0 ? last : st.get(l - 1));
if (fe >= INF64) {
nzs.emplace_back(l, r);
} else {
st.set(l, r + 1, fe + a);
st.addp(l, r + 1, a);
}
}
sort(nzs.begin(), nzs.end());
for (auto[t, l, r] : op) {
if (t != 1) {
continue;
}
ans[l] = st.get(r);
}
zs = nzs;
last = st.get(d - 1);
}
for (ll i = 0; i < q; i++) {
if (ans[i] >= INF64) {
ans[i] = -1;
}
cout << ans[i] << '\n';
}
}
int main() {
if (IS_FILE) {
freopen("", "r", stdin);
freopen("", "w", stdout);
}
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
ll t = 1;
if (IS_TEST_CASES) {
cin >> t;
}
for (ll i = 0; i < t; i++) {
solve();
}
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 55ms
memory: 12408kb
input:
2000 200000 500 66309 387245 91 122 793 1029 1127 1131 1304 1611 2007 2039 2601 2701 2906 3052 3253 3263 3495 3609 4157 4225 4283 4283 4757 4766 4786 4847 4885 5086 5326 5342 5607 5750 5847 5877 6093 6230 6548 6793 7206 7308 7413 7419 7752 7780 8244 8410 8501 8515 9335 9447 9512 9514 9602 9906 10076...
output:
-1 -1 2246130288 -1 1974313734 -1 -1 2236878855 1664531295 1094546986 429014008 -1 487647083 180389696 898221901 2150873416 1749626982 948494743 813346370 2040795144 1108355177 2313829133 139766130 -1 793944350 1127025143 1374180059 1404886436 630972703 -1 337778112 417404623 132984038 -1 1042709245...
result:
wrong answer 3rd lines differ - expected: '1545376776', found: '2246130288'
Subtask #2:
score: 0
Wrong Answer
Test #29:
score: 0
Wrong Answer
time: 12ms
memory: 10404kb
input:
1938 1960 999999 47694 9291 2883622 3085639 3674880 3745876 9982198101 9982517489 19960889157 19960925795 19962228551 19962276101 19964301694 19964730442 19964826417 19965369252 19965984922 19966442459 19968019821 19968213820 19968334967 19968392242 19968426638 19968840337 19969017519 19969109591 19...
output:
8771926113177 5310748335870 -1 -1 -1 2873280850044 524061365538 -1 10983180868659 1339589629662 3895830395751 373852803558 170752265931 6434630804652 9424452538887 11253493049022 5665717059078 5339114872188 -1 10018277655258 7611438998631 -1 -1 1706496465270 9253519434723 -1 10233531061224 -1 -1 875...
result:
wrong answer 1st lines differ - expected: '2629532778036', found: '8771926113177'
Subtask #3:
score: 0
Wrong Answer
Test #44:
score: 0
Wrong Answer
time: 1197ms
memory: 137420kb
input:
198085 196577 999999 1 999999 562622 895604 1799586 1975565 2518299 2941986 4934097 5403130 5755102 5996130 6036200 6112534 6391882 6431514 6451793 6555786 6613625 6621089 7130933 7204522 7335426 7522555 7748545 7784568 8184979 8494887 9066856 9178094 9303615 9384897 9716200 9719420 11693951 1183563...
output:
28229178585 142666273521 -1 -1 168323013709 346712570343 775849752494 -1 817524637237 785977908781 437217024291 -1 764730769628 869624466103 -1 749753507523 738927396018 189214053818 426198251776 -1 901067561792 459862347612 815386067886 -1 909122362432 547192818504 814705543740 -1 601143245622 -1 4...
result:
wrong answer 1st lines differ - expected: '27793636591', found: '28229178585'
Subtask #4:
score: 0
Skipped
Dependency #1:
0%