QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#488112#6156. 冰火战士pavement0 3633ms242908kbC++172.9kb2024-07-23 16:51:312024-07-23 16:51:31

Judging History

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

  • [2024-07-23 16:51:31]
  • 评测
  • 测评结果:0
  • 用时:3633ms
  • 内存:242908kb
  • [2024-07-23 16:51:31]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define mp make_pair
#define mt make_tuple

using ll = long long;
using ii = pair<int, int>;
using ll2 = pair<ll, ll>;
using iii = tuple<int, int, int>;

int Q, t1, s[2000005], t[2000005], x[2000005], y[2000005], k[2000005], idx[2000005];
iii c[2000005];

struct node {
	node *left, *right;
	int S, E;
	ll sum0, sum1;
	node(int _s, int _e) : S(_s), E(_e), sum0(0), sum1(0) {
		if (S == E) {
			return;
		}
		int M = (S + E) / 2;
		left = new node(S, M);
		right = new node(M + 1, E);
	}
	void upd(int p, int t, int x) {
		if (S == E) {
			if (t == 0) {
				sum0 += x;
			} else {
				sum1 += x;
			}
			return;
		}
		int M = (S + E) / 2;
		if (p <= M) {
			left->upd(p, t, x);
		} else {
			right->upd(p, t, x);
		}
		sum0 = left->sum0 + right->sum0;
		sum1 = left->sum1 + right->sum1;
	}
	void del(int p) {
		if (S == E) {
			sum0 = sum1 = 0;
			return;
		}
		int M = (S + E) / 2;
		if (p <= M) {
			left->del(p);
		} else {
			right->del(p);
		}
		sum0 = left->sum0 + right->sum0;
		sum1 = left->sum1 + right->sum1;
	}
	int get(ll pf = 0, ll sf = 0) {
		if (S == E) {
			if (pf + sum0 < sf + sum1) {
				return S;
			}
			return -1;
		}
		if (pf + left->sum0 < sf + right->sum1) {
			return max(left->E, right->get(pf + left->sum0, sf));
		} else {
			return left->get(pf, sf + right->sum1);
		}
	}
	ll2 qry(int l, int r) {
		if (l > E || r < S) {
			return mp(0, 0);
		}
		if (l <= S && E <= r) {
			return mp(sum0, sum1);
		}
		auto lq = left->qry(l, r), rq = right->qry(l, r);
		return mp(lq.first + rq.first, lq.second + rq.second);
	}
} *root;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> Q;
	for (int i = 1; i <= Q; i++) {
		cin >> s[i];
		if (s[i] == 1) {
			cin >> t[i] >> x[i] >> y[i];
			c[++t1] = mt(x[i], t[i], i);
		} else {
			cin >> k[i];
		}
	}
	sort(c + 1, c + 1 + t1);
	root = new node(1, t1);
	for (int i = 1; i <= Q; i++) {
		if (s[i] == 1) {
			idx[i] = lower_bound(c + 1, c + 1 + t1, mt(x[i], t[i], i)) - c;
			root->upd(idx[i], t[i], y[i]);
			//~ cout << "+ " << idx[i] << '\n';
		} else {
			root->del(idx[k[i]]);
		}
		pair<ll, int> val;
		int tmp = root->get();
		//~ cout << "TMP " << tmp << '\n';
		for (int temp_d : {tmp - 1, tmp, tmp + 1}) {
			if (!(1 <= temp_d && temp_d <= t1)) {
				continue;
			}
			int temp = get<0>(c[temp_d]);
			auto sums = root->qry(1, temp_d);
			//~ cout << "! " << root->sum0 << ' ' << root->sum1 << '\n';
			//~ cout << "@ " << temp << ' ' << temp_d << ' ' << sums.first << ' ' << sums.second << '\n';
			ll sum0 = sums.first;
			ll sum1 = root->sum1 - sums.second;
			ll cur = min(sum0, sum1);
			val = max(val, mp(cur, temp));
		}
		if (val.first == 0) {
			cout << "Peace\n";
		} else {
			cout << val.second << ' ' << val.first * 2 << '\n';
		}
	}
}

详细


Pretests


Final Tests

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 15928kb

input:

100
1 0 218 8134
2 1
1 0 322 4393
1 1 582 4233
1 0 426 4960
1 0 563 3003
1 1 71 7234
1 1 979 934
1 1 691 7228
1 1 723 1288
1 0 243 717
1 1 440 1860
1 1 128 76
1 0 230 4481
1 0 608 5824
2 3
1 0 107 6946
1 1 948 1161
1 1 108 5000
1 0 155 5615
2 15
1 1 927 6672
1 0 812 3669
1 1 95 7297
1 1 28 1482
2 6
...

output:

Peace
Peace
Peace
322 8466
322 8466
322 8466
322 8466
426 10334
563 24712
563 24712
563 26146
563 26146
563 26146
429 29102
429 29102
563 26322
426 31086
426 33408
426 33408
230 33408
230 33408
429 45438
429 45438
429 45438
429 45438
429 45438
429 45438
344 46752
344 46752
344 46752
344 46752
344 46...

result:

wrong answer 4th lines differ - expected: '582 8466', found: '322 8466'

Test #2:

score: 0
Wrong Answer
time: 4ms
memory: 14848kb

input:

10000
1 1 617 3010
1 1 618 1611
1 1 618 8241
1 1 619 2442
1 1 620 7838
1 0 620 213
1 0 620 9615
1 1 620 5337
1 0 621 1309
1 0 622 1864
1 1 622 5158
1 1 622 348
1 0 622 3882
1 1 622 824
1 0 622 5246
1 1 622 761
1 1 623 2455
1 1 624 4419
1 1 624 8757
1 1 624 2328
1 1 625 9786
1 1 626 6994
1 1 626 2378...

output:

Peace
Peace
Peace
Peace
Peace
620 426
620 15676
620 19656
620 19656
620 19656
620 19656
620 19656
620 19656
620 19656
620 19656
620 19656
620 19656
622 27930
622 44258
622 44258
623 44258
624 44258
624 44258
624 44258
624 44258
626 45794
626 45794
626 45794
626 45794
627 45794
627 45794
627 45794
62...

result:

wrong answer 21st lines differ - expected: '624 44258', found: '623 44258'

Test #3:

score: 0
Wrong Answer
time: 3ms
memory: 15060kb

input:

10000
1 1 867 9673
1 0 868 374
1 0 868 8754
1 0 868 5112
1 1 868 866
1 0 869 5341
1 0 870 6811
1 1 870 3136
1 1 870 1543
1 1 871 6525
1 1 871 1674
1 1 872 1838
1 1 873 7148
1 1 873 3262
1 1 873 1301
1 0 873 7434
1 1 874 5359
1 0 874 2808
1 0 874 2510
1 0 874 2152
1 1 875 5263
1 1 876 7616
1 0 876 85...

output:

Peace
Peace
Peace
Peace
868 1732
868 1732
868 1732
868 8004
868 11090
868 24140
868 27488
869 29432
870 43728
870 50252
870 52784
870 52784
870 52784
870 52784
870 52784
870 52784
870 52784
873 59898
873 59898
873 64396
873 67652
873 67652
873 67652
874 82592
874 82592
876 99688
876 99688
876 99688
...

result:

wrong answer 12th lines differ - expected: '870 29432', found: '869 29432'

Test #4:

score: 0
Wrong Answer
time: 251ms
memory: 40740kb

input:

200000
1 0 68501 4107
1 0 114713 4264
1 0 79273 9390
1 0 59365 5025
1 1 154543 9706
1 1 195251 2745
1 1 105643 632
1 0 23703 8863
1 0 95321 2975
1 1 197593 2537
1 0 198906 3676
1 1 187265 2227
1 1 94557 9531
1 1 30342 3049
1 0 138225 2469
1 1 196601 8832
1 0 120056 743
1 0 10889 4446
1 0 3473 455
1 ...

output:

Peace
Peace
Peace
Peace
79273 19412
79273 24902
79273 26166
59365 26166
59365 26166
68501 31240
68501 31240
68501 35694
79273 54756
79273 54756
79273 54756
94553 54770
94553 54770
94553 63662
94553 64572
79273 72420
68501 72420
79273 89468
68501 89468
79273 102226
79273 102226
79273 102226
79273 102...

result:

wrong answer 5th lines differ - expected: '154543 19412', found: '79273 19412'

Test #5:

score: 0
Wrong Answer
time: 248ms
memory: 39992kb

input:

200000
1 0 183981 1897
1 0 75105 2383
2 1
1 1 122913 2305
2 4
1 0 166063 5502
1 0 104001 4089
1 1 14 6405
1 0 115017 891
1 0 45734 9976
2 7
1 0 82385 570
1 1 33811 2907
1 0 118337 3336
1 0 80880 3103
1 0 49711 9838
1 0 70429 4710
1 1 95279 1936
1 0 135871 1761
1 0 187701 580
1 1 77073 5299
1 1 14062...

output:

Peace
Peace
Peace
75105 4610
Peace
Peace
Peace
Peace
Peace
Peace
Peace
Peace
Peace
Peace
Peace
Peace
Peace
45734 3872
45734 3872
45734 3872
45734 14470
45734 17256
45734 17256
45734 17256
45734 17256
45734 17256
45734 17256
45734 17256
45734 17256
54045 19952
54045 19952
54045 19952
58914 19952
4573...

result:

wrong answer 4th lines differ - expected: '122913 4610', found: '75105 4610'

Test #6:

score: 0
Wrong Answer
time: 249ms
memory: 42148kb

input:

200000
1 0 100908 5091
1 1 50240 5983
1 0 198465 1950
1 1 147925 610
1 1 107569 9345
1 0 126728 6141
1 1 157465 2742
1 0 14879 3002
2 1
1 0 174194 5987
1 0 156741 2887
1 1 159685 3784
1 0 172136 4317
1 0 170361 871
1 1 117603 1002
1 0 142251 1949
1 1 187581 9460
1 1 100500 523
1 0 167172 7820
1 0 71...

output:

Peace
Peace
Peace
100908 1220
107569 10182
107569 10182
107569 10182
107569 16186
126728 6704
126728 6704
126728 6704
126728 14272
126728 14272
126728 14272
126728 14272
126728 14272
157465 27958
157465 27958
157465 27958
157465 29166
156741 31972
156741 31972
157465 34430
157465 34430
157465 34430
...

result:

wrong answer 4th lines differ - expected: '147925 1220', found: '100908 1220'

Test #7:

score: 0
Wrong Answer
time: 3633ms
memory: 242764kb

input:

2000000
1 0 1217091 107
1 0 1765937 30
2 1
2 2
1 0 758967 946
1 1 1726929 789
1 0 1866918 861
1 0 841825 869
1 0 1734601 47
1 1 877281 397
1 0 1619742 549
2 5
1 1 590165 542
1 0 332203 963
2 8
1 1 1526271 702
1 0 914523 449
1 0 1711581 229
1 1 1939244 63
1 1 645419 616
1 1 1526125 930
1 0 639503 193...

output:

Peace
Peace
Peace
Peace
Peace
758967 1578
758967 1578
758967 1578
758967 1578
841825 2372
841825 2372
877281 1738
877281 1738
841825 2372
877281 1926
1526269 1926
1526269 2824
1526269 2824
1526269 2824
1526269 2824
1526269 2824
1526125 3210
914523 4968
1190421 5100
1190421 5100
1190421 5100
1190421 ...

result:

wrong answer 6th lines differ - expected: '1726929 1578', found: '758967 1578'

Test #8:

score: 0
Wrong Answer
time: 3580ms
memory: 242652kb

input:

2000000
1 0 1846771 368
1 1 1884221 616
1 0 1582901 883
1 1 890448 498
1 0 1169093 113
1 1 858334 764
1 0 317696 641
1 0 1152391 874
1 1 1548506 552
1 0 1716021 263
1 1 1206791 754
1 1 101157 555
1 1 1229682 332
1 1 5411 776
1 0 560553 469
1 0 503881 718
1 1 1454571 850
2 4
1 1 1255962 189
1 1 46296...

output:

Peace
1884221 736
1582901 1232
1582901 1232
1582901 1232
1582901 1232
890447 1282
890447 1282
1152391 2336
1152391 2336
1206788 3256
1206788 3256
1206788 3256
1206788 3256
1206788 4194
1152391 4508
1206788 5630
1206788 5630
1206788 5630
1206788 5630
1206788 5630
1206788 6202
1152391 6586
1152391 658...

result:

wrong answer 3rd lines differ - expected: '1884221 1232', found: '1582901 1232'

Test #9:

score: 0
Wrong Answer
time: 3582ms
memory: 242908kb

input:

2000000
1 0 933589 540
1 0 1332805 804
1 1 726913 60
1 0 582566 540
1 0 1541647 266
1 0 61185 227
1 0 44006 722
2 1
1 1 1100826 318
1 1 1583347 709
1 1 488319 941
2 10
1 0 1929473 528
2 13
1 1 1077416 855
1 0 1182411 885
1 0 1667425 768
1 1 1383821 403
1 0 187972 894
1 1 1583116 592
1 1 242066 187
2...

output:

Peace
Peace
Peace
582566 120
582566 120
61185 120
44006 120
44006 120
44006 756
582566 2174
582566 2174
488317 1898
488317 1898
488317 1898
582566 2466
582566 2466
582566 2466
1077416 2978
488317 3686
582566 4456
582566 4456
582566 4456
1077416 4766
1077416 4766
1077416 4766
651473 5090
726913 6300
...

result:

wrong answer 4th lines differ - expected: '726913 120', found: '582566 120'

Test #10:

score: 0
Wrong Answer
time: 3547ms
memory: 242624kb

input:

2000000
1 0 267659481 924
1 1 211034569 948
1 1 760144421 564
1 1 657639999 860
1 0 180151690 350
2 4
1 1 99406176 793
2 3
1 1 81357121 972
1 0 260132781 642
1 0 7161061 191
1 1 245955169 633
1 1 387566565 485
1 1 72982881 592
1 1 141574651 711
1 1 88299089 143
1 0 355273696 723
1 1 19210825 454
1 0...

output:

Peace
Peace
267659481 1128
657639207 1848
657639207 2548
267659481 1128
267659481 1128
211034513 700
211034513 700
211034513 700
211034513 1082
245954398 1082
245954398 1082
245954398 1082
245954398 1082
245954398 1082
245954398 1082
245954398 1082
211034513 3016
211034513 3942
211034513 3942
211034...

result:

wrong answer 3rd lines differ - expected: '760144421 1128', found: '267659481 1128'