QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#639811 | #1751. Automatic Accountant | oxford01# | WA | 67ms | 12104kb | C++20 | 2.7kb | 2024-10-13 22:53:06 | 2024-10-13 22:53:07 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (auto i = a; i < (b); ++i)
#define repr(i, a, b) for (auto i = (a) - 1; i >= (b); --i)
#define pb push_back
#define eb emplace_back
#define all(x) begin(x), end(x)
#define sz(x) int((x).size())
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vll = vector<ll>;
using vpii = vector<pii>;
template<class T>
inline bool cmax(T &a, const T& b) {
return a < b ? a = b, 1 : 0;
}
template<class T>
inline bool cmin(T &a, const T &b) {
return b < a ? a = b, 1 : 0;
}
const int inf = 0x3f3f3f3f;
const ll linf = 1e18;
const double dinf = numeric_limits<double>::infinity();
struct SegmentTree {
typedef int T;
static constexpr T unit = INT_MIN;
T f(T a, T b) { return max(a, b); }
vector<T> s; int n;
SegmentTree(int n = 0, T def = unit) : s(2*n, def), n(n) {}
void update(int pos, T val) {
for (s[pos += n] = val; pos /= 2; )
s[pos] = f(s[pos*2], s[pos*2+1]);
}
T get(int b, int e) {
T ra = unit, rb = unit;
for (b += n, e+= n; b < e; b /= 2, e/= 2) {
if (b%2) ra = f(ra, s[b++]);
if (e%2) rb = f(s[--e], rb);
}
return f(ra, rb);
}
};
/*struct SegmentTree {
vi t;
int n;
SegmentTree(int n) {
t = vi(4*n, INT_MIN);
}
void update(int v, int tl, int tr, int pos, int x) {
if ()
}
int get(int v, int tl, int tr, int l, int r) {
}
};*/
int main() {
cin.tie(0)->sync_with_stdio(0);
cin.exceptions(cin.failbit);
int s;
cin >> s;
vpii ab(s);
map<int, vpii> a;
for (int i = 0; i< s; i++) {
cin >> ab[i].first >> ab[i].second;
a[ab[i].second].pb({ab[i].first, i});
}
int c;
cin >> c;
vpii coins(c);
for (int i = 0; i< c; i++) {
cin >> coins[i].second >> coins[i].first; // Its swapped Importnant
}
sort(all(coins));
SegmentTree tree(s); // MAx tree
int res = 0;
int prev = 0;
for (int i = 0; i < c; i++) {
for (int j = prev; j <= coins[i].first; j++) {
for (auto x : a[j]) {
tree.update(x.second, x.first);
}
}
prev = coins[i].first+1;
int lo = 0, hi = s-1, ans = s-1, mid;
while (lo <= hi) {
mid = (lo+hi)/2;
bool check = tree.get(0, mid+1) >= coins[i].second;
if (check) {
ans = mid;
hi = mid - 1;
} else
lo = mid + 1;
}
res += ans+1;
}
cout << res << endl;
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3784kb
input:
1000 536 243 561 59 685 484 59 909 90 456 205 685 313 978 614 29 484 610 394 893 998 877 731 595 266 588 153 356 169 602 604 324 971 194 965 378 737 456 910 649 226 559 472 713 24 884 467 110 199 915 129 792 103 775 266 740 499 689 605 322 778 534 320 458 607 625 351 896 543 924 658 412 393 642 89 5...
output:
34010
result:
ok single line: '34010'
Test #2:
score: 0
Accepted
time: 19ms
memory: 4888kb
input:
50000 425 40 487 864 387 101 298 69 613 779 697 748 259 619 490 799 544 967 559 280 968 243 408 210 963 195 764 720 621 469 362 572 253 653 547 326 832 233 600 111 284 287 135 925 398 919 730 156 620 327 156 887 390 406 488 267 159 126 788 476 886 896 344 386 324 30 76 207 674 505 248 924 324 995 17...
output:
2225901
result:
ok single line: '2225901'
Test #3:
score: -100
Wrong Answer
time: 67ms
memory: 12104kb
input:
100000 344 70883 664 5149 547 56373 734 77762 942 85742 576 16116 697 36821 483 86461 842 33224 171 80225 261 66481 150 98557 96 74605 871 7563 688 62312 276 14306 327 28166 879 41516 342 91811 795 47532 21 54376 557 34066 609 42833 385 58831 166 76728 775 62803 431 97310 181 87000 335 34912 999 841...
output:
657493213
result:
wrong answer 1st lines differ - expected: '4952460509', found: '657493213'