QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #194772 | #7520. Monster Generator | ucup-team296# | TL | 0ms | 3772kb | C++14 | 7.3kb | 2023-09-30 22:19:18 | 2023-09-30 22:19:18 |
Judging History
你现在查看的是测评时间为 2023-09-30 22:19:18 的历史记录
- [2023-11-04 16:34:13]
- hack成功，自动添加数据
- (//qoj.ac/hack/422)
- [2023-11-04 16:28:16]
- hack成功，自动添加数据
- (//qoj.ac/hack/420)
- [2023-09-30 22:19:18]
- 提交
answer
#include <bits/stdc++.h>
#define long long long int
#define DEBUG
using namespace std;
// @author: pashka
bool lss(long a1, int a2, long b1, int b2) {
return a1 < b1 || (a1 == b1 && a2 < b2);
}
int main() {
ios::sync_with_stdio(false);
int n;
long m;
cin >> n >> m;
vector<long> a(n), da(n), b(n), db(n);
for (int i = 0; i < n; i++) {
cin >> a[i] >> da[i] >> b[i] >> db[i];
}
// for (int t = 0; t <= m; t++) {
// vector<long> aa(n);
// vector<long> bb(n);
// for (int i = 0; i< n; i++) {
// aa[i] = a[i] + da[i] * t;
// bb[i] = b[i] + db[i] * t;
// }
// vector<int> r;
// {
// vector<pair<long, int>> d;
// for (int i = 0; i < n; i++) {
// if (aa[i] < bb[i]) {
// d.emplace_back(aa[i], i);
// }
// }
// sort(d.begin(), d.end());
// for (auto p : d) {
// r.push_back(p.second);
// }
// }
// {
// vector<pair<long, int>> d;
// for (int i = 0; i < n; i++) {
// if (aa[i] >= bb[i]) {
// d.emplace_back(bb[i], i);
// }
// }
// sort(d.rbegin(), d.rend());
// for (auto p : d) {
// r.push_back(p.second);
// }
// }
// cout << t << ": ";
// for (auto x : r) cout << x << " ";
// cout << "\n";
// }
vector<long> e = {0, m + 1};
for (int t = 0; t < 2; t++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i == j) continue;
if (lss(a[i], i, a[j], j) &&
!lss(da[i], i, da[j], j)) {
long l = 0;
long r = 1;
while (lss(a[i] + r * da[i], i, a[j] + r * da[j], j)) {
r *= 2;
}
while (r > l + 1) {
long m = l + (r - l) / 2;
if (lss(a[i] + m * da[i], i, a[j] + m * da[j], j)) {
l = m;
} else {
r = m;
}
}
if (r < m)
e.push_back(r);
}
}
}
swap(a, b);
swap(da, db);
}
for (int i = 0; i < n; i++) {
if (lss(a[i], 0, b[i], 0) &&
!lss(da[i], 0, db[i], 0)) {
long l = 0;
long r = 1;
while (lss(a[i] + r * da[i], 0, b[i] + r * db[i], 0)) {
r *= 2;
}
while (r > l + 1) {
long m = l + (r - l) / 2;
if (lss(a[i] + m * da[i], 0, b[i] + m * db[i], 0)) {
l = m;
} else {
r = m;
}
}
if (r < m)
e.push_back(r);
}
}
sort(e.begin(), e.end());
e.erase(unique(e.begin(), e.end()), e.end());
// for (auto x: e) {
// cout << x << "\n";
// }
long res = 0;
for (int ii = 0; ii < (int)e.size() - 1; ii++) {
long tl = e[ii];
long tr = e[ii + 1];
vector<long> aa(n);
vector<long> bb(n);
for (int i = 0; i< n; i++) {
aa[i] = a[i] + da[i] * tl;
bb[i] = b[i] + db[i] * tl;
}
vector<int> r;
{
vector<pair<long, int>> d;
for (int i = 0; i < n; i++) {
if (aa[i] < bb[i]) {
d.emplace_back(aa[i], i);
}
}
sort(d.begin(), d.end());
for (auto p : d) {
r.push_back(p.second);
}
}
{
vector<pair<long, int>> d;
for (int i = 0; i < n; i++) {
if (aa[i] >= bb[i]) {
d.emplace_back(bb[i], i);
}
}
sort(d.rbegin(), d.rend());
for (auto p : d) {
r.push_back(p.second);
}
}
vector<pair<long, long>> g;
g.push_back({0, 0});
pair<long, long> cur = {0, 0};
for (int i : r) {
cur.first -= a[i];
cur.second -= da[i];
// cout << cur.first << " " << cur.second << "\n";
g.push_back({cur.first, -cur.second});
cur.first += b[i];
cur.second += db[i];
}
sort(g.begin(), g.end());
vector<pair<long, long>> st;
// for (auto p : g) {
// cout << p.first << "," << p.second << " ";
// }
// cout << "\n";
for (auto p : g) {
while (st.size() >= 2) {
pair<long, long> a = st[st.size() - 2];
pair<long, long> b = st[st.size() - 1];
long dx1 = b.first - a.first;
long dy1 = b.second - a.second;
long dx2 = p.first - a.first;
long dy2 = p.second - a.second;
if (dx1 * dy2 - dx2 * dy1 >= 0) {
st.pop_back();
} else {
break;
}
}
st.push_back(p);
}
while (st.size() >= 2) {
pair<long, long> a = st[st.size() - 2];
pair<long, long> b = st[st.size() - 1];
if (b.second <= a.second) {
st.pop_back();
} else {
break;
}
}
g = st;
// for (auto p : g) {
// cout << p.first << "," << p.second << " ";
// }
// cout << "\n";
int k = g.size();
vector<pair<long, int>> tt;
tt.push_back({tl, 0});
for (int i = 0; i < k - 1; i++) {
long a1 = g[i].first;
long b1 = g[i].second;
long a2 = g[i + 1].first;
long b2 = g[i + 1].second;
long l = 0;
long r = 1;
while (a2 - b2 * r > a1 - b1 * r) r *= 2;
while (r > l + 1) {
long m = l + (r - l) / 2;
if (a2 - b2 * m <= a1 - b1 * m) {
r = m;
} else {
l = m;
}
}
r = max(r, tl);
r = min(r, tr);
tt.push_back({r, i + 1});
}
tt.push_back({tr, k});
for (int i = 0; i < (int)tt.size() - 1; i++) {
// cout << "! " << tt[i].first << " " << tt[i].second << "\n";
auto p = g[tt[i].second];
long d = (tt[i + 1].first - tt[i].first);
res += (-p.first) * d;
res += p.second * tt[i].first * d;
res += p.second * (d * (d - 1) / 2);
// for (int t = tt[i].first; t < tt[i + 1].first; t++) {
// long s = - p.first + t * p.second;
// res += s;
// cout << t << " " << s << "\n";
// }
}
// cout << tl << ": ";
// for (auto x : r) cout << x << " ";
// cout << "\n";
}
cout << (uint64_t)res << "\n";
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3544kb
input:
3 5 3 1 5 2 4 2 1 3 1 9 100 1
output:
113
result:
ok single line: '113'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3512kb
input:
3 100000000 3 1 5 2 4 2 1 3 1 9 100 1
output:
35000000549999998
result:
ok single line: '35000000549999998'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3772kb
input:
10 1000000000000000000 776874380544333 197 471391764744275 33 159838820333814 107 677112662750393 41 962335658276824 48 255593531071176 11 127404116579775 209 268525254990127 34 647620110614714 76 897947476313307 13 146196843402516 221 772928712898807 39 637929916804442 2 716937021892338 15 64200226...
output:
17883317185357051350
result:
ok single line: '17883317185357051350'
Test #4:
score: -100
Time Limit Exceeded
input:
10 1000000000000 519946 5 967590 4 367668 9 772494 6 635694 5 932710 1 260259 2 627580 1 84994 3 52124 6 447095 4 705749 6 427312 2 977458 7 540121 1 292993 5 556831 6 321679 4 567919 4 609512 4