QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#398028 | #8590. Problem Setter | Talaodi | 26 | 68ms | 11652kb | C++23 | 5.1kb | 2024-04-24 21:20:51 | 2024-04-24 21:20:51 |
Judging History
answer
#include <bits/stdc++.h>
namespace IO {
template <class Stream>
void write_int128(Stream& out, __int128 v) {
if (v >= 10) {
write_int128(out, v / 10);
}
out << (int) (v % 10);
}
template <class Stream>
Stream& fmtbase(Stream& out, const char* format) {
for (; *format; format++) {
if (*format == '{' && *(format + 1) == '}') {
throw std::invalid_argument("Error Number of Parameters!");
}
out << *format;
}
return out;
}
template <class Stream, class... Nxt>
Stream& fmtbase(Stream& out, const char* format, const __int128& value, const Nxt&... nxt) {
for (; *format; format++) {
if (*format == '{' && *(format + 1) == '}') {
write_int128(out, value);
return fmtbase(out, format + 2, nxt...);
}
out << *format;
}
throw std::invalid_argument("Error Number of Parameters!");
}
template <class Stream, class Fst, class... Nxt>
Stream& fmtbase(Stream& out, const char* format, const Fst& value, const Nxt&... nxt) {
for (; *format; format++) {
if (*format == '{' && *(format + 1) == '}') {
out << value;
return fmtbase(out, format + 2, nxt...);
}
out << *format;
}
throw std::invalid_argument("Error Number of Parameters!");
}
template <class... Ps>
std::string to_string(const char* format, const Ps&... ps) {
std::stringstream ss;
fmtbase(ss, format, ps...);
return ss.str();
}
template <class... Ps>
std::ostream& fmtout(const char* format, const Ps&... ps) {
return fmtbase(std::cout, format, ps...);
}
template <class... Ps>
std::ostream& fmterr(const char* format, const Ps&... ps) {
return fmtbase(std::cerr, format, ps...);
}
std::istream& allin() {
return std::cin;
}
template <class Fst, class ... Nxt>
std::istream& allin(Fst& fst, Nxt&... nxt) {
std::cin >> fst;
return allin(nxt...);
}
template <class Iter>
std::istream& rangin(Iter begin, Iter end) {
while (begin != end) {
std::cin >> *begin;
begin++;
}
return std::cin;
}
namespace Fast {
bool sync = false;
char buf[1 << 23];
char *p1 = buf, *p2 = buf;
void sync_with_ios(bool s) {
sync = s;
}
inline char getchar() {
if (sync) {
return (char) std::cin.get();
}
else {
return (p1 == p2) && (p2 = (p1 = buf) + fread(buf, 1, 1 << 22, stdin)), p1 == p2 ? EOF : *p1++;
}
}
void read() { }
template <class T, class... U>
void read(T& x, U&... us) {
x = 0;
T pos = 1;
char c = getchar();
while (!isdigit(c)) {
if (c == '-') {
pos = -1;
}
c = getchar();
}
while (isdigit(c)) {
x = 10 * x + c - '0';
c = getchar();
}
x *= pos;
read(us...);
}
template <class T>
void write(const T& t) {
if (t > 10) {
write(t / 10);
}
std::cout << (int) (t % 10);
}
}
}
namespace Solve {
#define int long long
using namespace IO;
using ll = long long;
using ul = unsigned long long;
using db = double;
using ld = long double;
using ui = unsigned;
using ib = __int128;
using ub = __uint128_t;
int const INF = std::numeric_limits<int>::max();
int const NINF = std::numeric_limits<int>::min();
ll const LINF = std::numeric_limits<ll>::max();
ll const LNINF = std::numeric_limits<ll>::min();
ld const EPS = 1e-8;
std::mt19937_64 mt;
ll rnd(ll l, ll r) {
return std::uniform_int_distribution<ll>(l, r)(mt);
}
template <class T>
inline int isz(const T& v) {
return v.size();
}
template <class T>
inline T& ckmx(T& a, T b) {
return a < b ? (a = b) : a;
}
template <class T>
inline T& ckmi(T& a, T b) {
return b < a ? (a = b) : a;
}
int const N = 2e5 + 10;
struct Val {
int v, w;
bool operator<(const Val& rhs) const {
return v < rhs.v;
}
};
int n, m;
Val ps[N + 1];
Val cs[N + 1];
void main() {
std::cin >> n >> m;
for (int i = 1; i <= n; i++) {
std::cin >> cs[i].v >> cs[i].w;
}
for (int i = 1; i <= m; i++) {
std::cin >> ps[i].v >> ps[i].w;
}
std::sort(ps + 1, ps + n + 1);
std::sort(cs + 1, cs + m + 1);
std::priority_queue<int> mx;
int p = 0;
int ans = 0;
for (int i = 1; i <= n; i++) {
while (p + 1 <= m && cs[p + 1].v <= ps[i].v) {
p++;
mx.push(cs[p].w);
}
if (isz(mx) && mx.top() - ps[i].w > 0) {
ans += mx.top();
ans -= ps[i].w;
}
}
fmtout("{}\n", ans);
}
void init() {
}
void clear() {
}
}
signed main() {
#ifndef ONLINE_JUDGE
auto input_file = freopen("d.in", "r", stdin);
auto output_file = freopen("d.out", "w", stdout);
#endif
auto seed = std::chrono::high_resolution_clock::now().time_since_epoch().count();
IO::fmterr("seed: {}\n", seed);
Solve::mt.seed(seed);
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
int t = 1;
// std::cin >> t;
Solve::init();
for (int id = 1; id <= t; id++) {
Solve::main();
Solve::clear();
}
#ifndef ONLINE_JUDGE
std::cout.flush();
fclose(input_file);
fclose(output_file);
#endif
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3900kb
input:
1000 1 570339 324084 75781 292531 427864 843267 928484 613828 883296 385343 733451 782070 756314 89477 786410 133722 455015 841750 146307 536680 992681 107898 657731 633895 764691 258779 142935 640379 445046 717170 227758 578083 526095 660806 859673 757597 898726 4088 719881 887973 850810 674331 752...
output:
0
result:
wrong answer 1st lines differ - expected: '575102', found: '0'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 26
Accepted
Test #24:
score: 26
Accepted
time: 60ms
memory: 11600kb
input:
200000 200000 443848 257048 353855 430518 112240 460358 489050 850745 18217 643349 796031 335731 553602 81823 556808 39341 963397 797473 713023 273372 888193 500234 801660 980841 416233 163140 649254 659678 434013 461662 805451 259446 107168 839690 438518 100393 584335 435627 735040 11809 906814 672...
output:
199985649927
result:
ok single line: '199985649927'
Test #25:
score: 26
Accepted
time: 64ms
memory: 11524kb
input:
200000 200000 333130 577648 41080 822997 187466 358241 16874 51949 553684 775680 888225 58652 283594 632965 971667 522676 73986 76332 905359 631172 633389 994061 934283 902840 110896 341628 432967 332824 239445 649641 689728 484799 124192 63092 153968 530823 906578 363019 287528 659642 141227 738119...
output:
199982798008
result:
ok single line: '199982798008'
Test #26:
score: 26
Accepted
time: 55ms
memory: 11652kb
input:
200000 200000 611734 279091 714031 285014 27470 340840 153223 730480 928132 593181 347393 404865 272959 638606 963277 818505 269192 633347 90450 816938 355398 27411 731512 872519 490897 450482 160071 49026 246985 835302 147838 296619 230153 623742 138143 771274 65730 553610 625075 37550 630552 39770...
output:
199983714403
result:
ok single line: '199983714403'
Test #27:
score: 26
Accepted
time: 68ms
memory: 11632kb
input:
200000 200000 730837 46140 409083 509621 325651 932449 863659 658681 757387 809828 264223 76652 183168 539497 509871 264882 932759 497239 432560 969985 175115 36367 282045 503058 914403 6069 352721 594493 481605 484947 379039 160881 102071 906584 728660 618381 667626 563020 930844 363389 766516 9447...
output:
199987103986
result:
ok single line: '199987103986'
Test #28:
score: 26
Accepted
time: 64ms
memory: 11624kb
input:
200000 200000 202263 268030 52175 729770 426294 608774 109305 63522 351625 711645 622711 334732 426748 820206 632533 560753 792623 713969 842108 25680 971646 622533 497870 219646 22559 492708 526446 145330 881333 95276 221073 611609 62925 526673 624216 350190 181800 873313 947674 307624 231389 48826...
output:
199987840885
result:
ok single line: '199987840885'
Test #29:
score: 26
Accepted
time: 68ms
memory: 11640kb
input:
200000 200000 723340 41402 840645 717625 669541 388205 755135 669311 963721 828311 538102 363770 484744 891772 737592 103694 809381 122715 575127 784624 977291 839505 112953 134765 933841 162362 381951 621353 148706 561324 533734 59704 381455 223728 258576 207336 29208 141318 603634 286254 244493 54...
output:
199985653996
result:
ok single line: '199985653996'
Test #30:
score: 26
Accepted
time: 64ms
memory: 11600kb
input:
200000 200000 670051 306615 577156 738705 640566 327037 936176 603057 377798 629461 44518 941417 876796 417153 492716 458444 986122 810302 412582 446900 959063 522002 354960 172247 492090 726069 106849 65061 618188 876374 420913 19582 899919 146348 161662 912188 713528 710206 969970 994962 661873 63...
output:
199990956643
result:
ok single line: '199990956643'
Test #31:
score: 26
Accepted
time: 60ms
memory: 11636kb
input:
200000 200000 421634 601120 410450 522375 143766 763196 728302 935843 172686 793444 822230 957006 189007 876154 803510 38425 667537 878764 332374 1089 2229 254789 387954 758908 206210 773509 334292 338719 277064 692407 80497 143585 110340 865160 708089 186694 841274 60229 305213 651600 613528 654675...
output:
199990875965
result:
ok single line: '199990875965'
Test #32:
score: 26
Accepted
time: 60ms
memory: 11628kb
input:
200000 200000 524169 350466 154101 375584 300748 321070 55639 671269 806555 754278 115597 483518 761276 677287 690370 393218 471252 262379 356602 458614 22209 490102 86239 393933 530300 751999 542125 691747 138733 469124 351600 743057 409699 884219 485557 382905 880614 748819 425515 964318 894775 22...
output:
199988650170
result:
ok single line: '199988650170'
Test #33:
score: 26
Accepted
time: 60ms
memory: 11520kb
input:
200000 200000 346532 83446 963647 129601 948421 492041 368489 226646 387685 53098 520613 707840 907096 156254 356463 314449 989590 400608 594784 275269 671467 366763 316115 727090 79435 730997 63228 991553 16437 617043 700774 614918 543703 573042 822631 527951 986185 10523 664730 584245 95750 758299...
output:
199995955822
result:
ok single line: '199995955822'
Subtask #4:
score: 0
Skipped
Dependency #1:
0%