QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#444292 | #8648. Tower | green_gold_dog# | 0 | 83ms | 14144kb | C++23 | 9.5kb | 2024-06-15 18:08:10 | 2024-06-15 18:08:10 |
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, 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 - max(l, 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);
m[b1 + 2].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 + 2].emplace_back(1, q, 0);
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);
vector<ll> qqq(q);
for (ll i = 0; i < q; i++) {
ll x;
cin >> x;
qqq[i] = 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);
if ((now - lst) != 1 && pbad != 0) {
exit(1);
}
lst = now;
st.add(0, pbad, cph);
ll bsuff = d;
deque<pair<ll, ll>> nzs;
ll npbad;
sort(op.begin(), op.end());
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);
}
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;
} else {
//ans[i] = qqq[i];
}
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: 5
Accepted
time: 83ms
memory: 14144kb
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 1545376776 -1 1355518146 -1 -1 1538578776 1124179254 736677313 275840218 -1 314646902 120181124 592802647 1470145222 1194355416 630012616 541479470 1380556431 748297307 1579324340 83071935 -1 547672724 766967273 940718126 967114418 448357717 -1 208077708 264694996 68332763 -1 699361243 1542138...
result:
ok 200000 lines
Test #2:
score: 5
Accepted
time: 73ms
memory: 14064kb
input:
2000 200000 500 45649 229891 123 232 663 994 1023 1041 1065 1065 1523 1542 1962 1983 2044 2066 2449 2453 2589 2591 2788 2810 3207 3418 3666 3685 3944 3945 4256 4320 4699 4706 4915 4950 5196 5207 5271 5545 5705 5707 5867 6034 6273 6328 6364 6380 6764 6787 6974 7007 7363 7365 7632 7648 7754 7924 7954 ...
output:
-1 -1 1044862158 349767467 -1 -1 -1 -1 534260754 853076992 514160380 514034955 -1 -1 680989150 557376047 -1 410302211 -1 -1 14156128 -1 -1 656642980 -1 335413929 465525211 1047741337 1007928386 -1 183280077 -1 842399625 553981561 -1 -1 486838795 823208939 597570650 68518820 -1 -1 36379839 -1 4959492...
result:
ok 200000 lines
Test #3:
score: 0
Wrong Answer
time: 70ms
memory: 13936kb
input:
2000 200000 500 11 228852 288 470 648 922 1193 1288 1509 1516 1792 1915 2023 2061 2443 2477 2512 2693 2735 2860 3176 3196 3260 3363 3622 3658 3939 3988 4177 4223 4470 4541 4640 4789 4812 4850 5167 5246 5443 5594 5692 5804 5875 5982 6265 6286 6416 6609 6816 6833 6928 7130 7298 7305 7401 7403 7778 781...
output:
66891862 2290159 208666860 103080772 86816154 203629080 136748845 -1 128736319 171561783 116133641 171104607 114077361 -1 179118134 -1 177745847 -1 3435497 158280843 -1 81779122 -1 -1 -1 118194706 -1 121403628 176144983 72847327 184160908 139495223 180954538 -1 201568169 163316346 45822034 -1 167668...
result:
wrong answer 1st lines differ - expected: '61754766', found: '66891862'
Subtask #2:
score: 0
Runtime Error
Test #29:
score: 0
Runtime Error
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:
result:
Subtask #3:
score: 0
Runtime Error
Test #44:
score: 0
Runtime Error
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:
result:
Subtask #4:
score: 0
Skipped
Dependency #1:
0%