QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#398028#8590. Problem SetterTalaodi26 68ms11652kbC++235.1kb2024-04-24 21:20:512024-04-24 21:20:51

Judging History

你现在查看的是最新测评结果

  • [2024-04-24 21:20:51]
  • 评测
  • 测评结果:26
  • 用时:68ms
  • 内存:11652kb
  • [2024-04-24 21:20:51]
  • 提交

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%