QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#310923#8014. 新本格魔法少女SSH_automaton0 4ms44656kbC++144.3kb2024-01-21 19:43:262024-01-21 19:43:27

Judging History

This is the latest submission verdict.

  • [2024-01-21 19:43:27]
  • Judged
  • Verdict: 0
  • Time: 4ms
  • Memory: 44656kb
Show
  • [2024-01-21 19:43:26]
  • Submitted

answer

#include <bits/stdc++.h>

using namespace std;

#define TL(tl) while(1.0 * clock() / CLOCKS_PER_SEC < tl)
#define fi first
#define se second

typedef long long ll;
typedef pair<int, ll> pii;
const int N = 5e5 + 5;
const int B = 5, SB = N / B + 15;
int n, m, q, op[N], L[N], R[N], V[N], QL[N];
ll ans[N];
vector<int> ask[N];

int nl[SB], nr[SB], nbel[N], nc;
int ml[SB], mr[SB], mbel[N], mc;

namespace blo1 {
int a[N], b[SB], s[N], t[SB], u[SB];
inline void upd(int l, int r, int v, int tim) {
	int p = nbel[l], q = nbel[r];
	for (int i = p; i <= q; ++i) u[i] = tim;
	if (p == q) {
		for (int i = l; i <= r; ++i) a[i] = v, s[i] = tim;
	} else {
		for (int i = nr[p]; i >= l; --i) a[i] = v, s[i] = tim;
		for (int i = nl[q]; i <= r; ++i) a[i] = v, s[i] = tim;
		for (int i = p + 1; i < q; ++i) b[i] = v, t[i] = tim;
	}
}
inline pii ask_pos(int x) {
	int p = nbel[x];
	return max(pii(s[x], a[x]), pii(t[p], b[p]));
}
inline pii ask_blo(int p) {
	return max(pii(u[p], 0), pii(t[p], (ll)b[p] * (nr[p] - nl[p] + 1)));
}
}

namespace blo2 {
ll a[N], b[SB];
inline void upd(const pii &U) { a[U.fi] += U.se, b[mbel[U.fi]] += U.se; }
inline ll ask(int x) {
	int p = mbel[x]; ll res = 0;
	for (int i = mc; i > p; --i) res += b[i];
	for (int i = mr[p]; i >= x; --i) res += a[i];
	return res;
}
}

inline void work1() {
	for (int t = 1; t <= m; ++t) {
		if (op[t] == 1) {
			blo1::upd(L[t], R[t], V[t], t);
		} else {
			int l = L[t], r = R[t], p = nbel[l], q = nbel[r];
			if (p == q) {
				for (int i = l; i <= r; ++i) blo2::upd(blo1::ask_pos(i));
			} else {
				for (int i = nr[p]; i >= l; --i) blo2::upd(blo1::ask_pos(i));
				for (int i = nl[q]; i <= r; ++i) blo2::upd(blo1::ask_pos(i));
				for (int i = p + 1; i < q; ++i) blo2::upd(blo1::ask_blo(i));
			}
		}
		for (int i : ask[t]) ans[i] += blo2::ask(QL[i]);
	}
}

namespace blo3 {
ll a[N], b[SB];
inline ll ask(int x) { return a[x] + b[mbel[x]]; }
inline void upd(int x, ll v) {
	int p = mbel[x];
	for (int i = 1; i < p; ++i) b[i] += v;
	for (int i = ml[p]; i <= x; ++i) a[i] += v;
}
inline void clear() {
	for (int i = 1; i <= m; ++i) a[i] = 0;
	for (int i = 1; i <= mc; ++i) b[i] = 0;
}
}

int tl[N], tr[N], cnt; ll tv[N];

namespace blo4 {
int a[N], tim, tag;
ll sum;
inline void pushdown(int p) {
	for (int i = nl[p]; i <= nr[p]; ++i) a[i] = tag;
	tag = -1;
}
inline void upd_seg(int l, int r, int v, int t) {
	int p = nbel[l];
	if (tag == -1) tl[++cnt] = tim, tr[cnt] = t - 1, tv[cnt] = sum;
	else pushdown(p);
	tim = t;
	for (int i = l; i <= r; ++i) sum += v - a[i], a[i] = v;
}
inline void upd_blo(int p, int v, int t) {
	if (tag == -1) tl[++cnt] = tim, tr[cnt] = t - 1, tv[cnt] = sum;
	tag = v, tim = t, sum = (ll)v * (nr[p] - nl[p] + 1);
}
}

inline void work2(int p) {
	cnt = 0, blo4::tim = blo4::sum = 0, blo4::tag = -1;
	blo3::clear();
	for (int t = 1; t <= m; ++t) {
		if (op[t] == 1) {
			int l = L[t], r = R[t], v = V[t];
			int pl = nbel[l], pr = nbel[r];
			if (p == pl || p == pr) blo4::upd_seg(max(l, nl[p]), min(r, nr[p]), v, t);
			else if (p > pl && p < pr) blo4::upd_blo(p, v, t);
		}
	}
	blo4::upd_blo(p, 0, m + 1);
	int cur = 0;
	ll sum = 0;
	for (int t = 1; t <= m; ++t) {
		while (cur < cnt && t >= tl[cur + 1]) blo3::upd(tl[cur], sum), sum = 0, ++cur;
		if (op[t] == 2 && t <= tr[cur] && p > nbel[L[t]] && p < nbel[R[t]]) sum += tv[cur];
		for (int i : ask[t])
			if (QL[i] <= tl[cur])
				ans[i] += blo3::ask(QL[i]) + sum;
	}
}

int main() {
//	freopen("mfsn.in", "r", stdin);
//	freopen("mfsn.out", "w", stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m >> q;
	if (max({n, m, q}) > 100) return 0;
	for (int i = 1; i <= m; ++i) {
		cin >> op[i] >> L[i] >> R[i];
		if (op[i] == 1) cin >> V[i];
	}
	for (int i = 1; i <= q; ++i) {
		int QR;
		cin >> QL[i] >> QR;
		ask[QR].push_back(i);
	}
	nc = (n - 1) / B + 1, mc = (m - 1) / B + 1;
	for (int i = 1; i <= nc; ++i) {
		nl[i] = nr[i - 1] + 1;
		nr[i] = min(n, nr[i - 1] + B);
		for (int j = nl[i]; j <= nr[i]; ++j) nbel[j] = i;
	}
	for (int i = 1; i <= mc; ++i) {
		ml[i] = mr[i - 1] + 1;
		mr[i] = min(m, mr[i - 1] + B);
		for (int j = ml[i]; j <= mr[i]; ++j) mbel[j] = i;
	}
	work1();
	for (int p = 1; p <= nc; ++p) work2(p);
	for (int i = 1; i <= q; ++i) cout << ans[i] << '\n';
	return 0;
}
源文件, 语言: C++14

詳細信息

Test #1:

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

input:

100 100 100
2 80 86
2 15 49
1 11 100 25
2 22 36
2 37 100
1 14 16 49
2 74 90
2 28 76
1 43 45 78
1 54 56 27
1 73 75 29
2 34 81
2 51 90
1 13 14 52
1 72 73 2
2 18 58
2 44 58
1 83 85 30
1 86 88 69
1 29 31 25
1 92 94 19
1 48 49 16
1 55 57 91
1 98 100 42
2 13 96
2 50 83
1 23 25 39
1 84 85 55
1 43 45 5
1 90...

output:

12195
25035
6013
13211
9908
24622
4827
0
2823
2469
441
247
17231
0
9337
3251
31690
2462
20463
7188
23109
31401
8148
9049
15122
17800
12110
24572
0
16228
26672
3232
5170
24431
1370
255
15049
33513
1241
35434
704
4257
0
33364
38343
38947
18868
20463
10731
819
9653
48343
18997
12195
19820
16223
2069
69...

result:

wrong answer 1st numbers differ - expected: '8086', found: '12195'

Test #2:

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

input:

100 100 100
1 56 92 5
1 5 9 91
1 70 92 77
1 45 52 90
1 37 38 36
1 9 10 1
2 1 72
1 79 80 86
2 40 98
1 96 97 89
2 46 78
2 41 58
1 57 58 65
1 73 74 44
1 20 21 54
1 95 96 61
1 23 24 40
1 60 61 48
1 17 18 65
1 43 44 68
1 44 45 7
1 28 29 4
1 10 11 37
1 14 15 44
1 69 70 18
1 33 34 52
1 15 16 67
1 62 63 64
...

output:

0
1807
7352
7352
0
0
7352
0
0
5447
11863
0
10134
0
0
403
3016
0
5605
0
0
3016
7183
0
403
4685
0
7844
0
0
10392
0
3807
0
10267
0
1448
2664
0
7183
0
0
5106
5910
1053
5447
1448
14233
4647
0
7183
0
7316
7352
3016
10392
5325
0
1807
3016
0
2101
6001
6166
7352
0
0
904
0
5106
5605
2321
7254
403
0
0
10267
35...

result:

wrong answer 2nd numbers differ - expected: '700', found: '1807'

Test #3:

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

input:

5000 5000 5000
1 4070 5000 3145
2 1139 3698
1 798 799 3999
1 2423 2424 2414
1 836 838 518
1 3605 3607 2831
1 525 526 2041
1 4734 4736 1862
2 2408 3821
1 1394 1395 1129
2 601 3026
2 728 4428
1 567 569 4843
2 4235 4835
1 3568 3569 1157
1 3043 3045 4342
1 1813 1815 1888
1 2992 2993 4810
1 1862 1864 112...

output:

result:

wrong answer Answer contains longer sequence [length = 5000], but output contains 0 elements

Test #4:

score: 0
Wrong Answer
time: 2ms
memory: 15892kb

input:

5000 5000 5000
1 3198 5000 2085
1 2688 2781 3934
1 663 664 1655
1 472 473 4369
1 822 823 75
2 798 2403
1 518 519 4434
1 4022 4023 3962
1 121 122 1996
1 568 569 2710
1 2908 2909 418
1 429 430 4757
1 1361 1362 4590
1 4439 4440 4849
1 3104 3105 2808
1 78 79 1549
1 2111 2112 2281
1 3405 3406 4240
1 2739...

output:

result:

wrong answer Answer contains longer sequence [length = 5000], but output contains 0 elements

Test #5:

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

input:

4997 5000 4997
1 924 4997 4123
1 1508 1568 759
1 1148 1190 3389
1 908 952 122
1 4976 4997 4100
1 4578 4637 1736
1 2780 2821 3570
1 2830 2874 1796
1 351 391 1
1 762 801 3091
1 2060 2105 398
1 4572 4618 615
1 941 971 853
1 4395 4397 4934
1 4573 4574 4506
1 3697 3698 83
2 112 2024
1 310 311 1941
1 2116...

output:

result:

wrong answer Answer contains longer sequence [length = 4997], but output contains 0 elements

Test #6:

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

input:

4997 4999 4996
2 4368 4799
2 2119 4764
2 4434 4464
1 2035 4706 4296
1 519 522 2387
2 3 2084
1 4748 4755 461
2 2812 4626
1 4801 4805 2427
1 611 615 2155
2 772 2397
2 1443 2197
2 392 792
1 3032 3036 2776
2 3148 4757
1 3661 3678 3968
1 3901 3921 2378
1 143 164 531
1 3337 3360 3189
2 679 2911
1 1436 145...

output:

result:

wrong answer Answer contains longer sequence [length = 4996], but output contains 0 elements

Test #7:

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

input:

499998 499998 500000
2 45317 481911
2 205023 267850
2 229212 496395
2 311928 408362
2 60781 309919
2 5271 471569
2 428188 498422
2 92261 439291
2 169892 354633
2 154209 351949
2 39872 442239
2 17793 200874
2 111458 165313
2 35630 448969
2 144408 434923
2 150127 486605
2 87239 425125
2 221549 283735
...

output:

result:

wrong answer Answer contains longer sequence [length = 500000], but output contains 0 elements

Test #8:

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

input:

499996 500000 499996
2 416226 432058
2 352324 435508
2 284349 418508
2 331919 481387
2 123642 260653
2 443789 449866
2 304455 480845
2 25402 269023
2 88509 334117
2 91159 399658
2 354630 412055
2 27378 126849
2 43994 304769
2 352338 413477
2 441505 499446
2 230203 287653
2 386 34219
2 77130 483544
2...

output:

result:

wrong answer Answer contains longer sequence [length = 499996], but output contains 0 elements

Test #9:

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

input:

499999 499997 499996
1 242721 499999 95404
2 46103 133768
2 374074 441419
1 24121 24525 460791
1 296358 334367 213389
1 333891 339996 192126
2 271641 289312
1 159292 235107 359363
2 281766 283959
2 68186 255669
2 112532 201134
2 281439 287449
2 265345 398433
1 495720 499897 85179
2 336233 383598
1 3...

output:

result:

wrong answer Answer contains longer sequence [length = 499996], but output contains 0 elements

Test #10:

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

input:

499996 499998 499996
2 127334 135648
2 250092 494065
2 202618 237080
1 365995 485247 159366
1 461761 461763 167619
1 161295 165395 156081
2 118953 278863
1 31995 32188 13920
2 211226 376698
2 125014 312511
1 248692 248694 369316
2 23909 438451
1 90793 222688 109394
1 405548 405549 283104
2 54420 263...

output:

result:

wrong answer Answer contains longer sequence [length = 499996], but output contains 0 elements

Test #11:

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

input:

499999 499996 500000
1 263967 499999 193060
1 473673 473677 256364
1 112817 112820 147747
2 47560 75007
1 19751 19754 272463
1 147343 147345 432368
1 385248 385251 111981
1 98114 98117 384182
1 186894 186898 304739
1 13283 13285 1641
1 127923 127925 168790
2 59949 123247
2 76677 91972
1 138037 13803...

output:

result:

wrong answer Answer contains longer sequence [length = 500000], but output contains 0 elements

Test #12:

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

input:

499999 499995 499997
1 163879 499999 440480
2 420164 470414
1 443882 499999 62525
1 313171 499999 294789
1 469407 469540 44668
2 25119 191405
2 172689 455667
2 110136 338451
2 218391 398188
1 486533 486654 93435
2 95706 256203
2 196989 304612
2 326480 401308
2 54460 198784
1 271793 271898 320340
2 9...

output:

result:

wrong answer Answer contains longer sequence [length = 499997], but output contains 0 elements

Test #13:

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

input:

200000 200000 200000
2 31803 80740
2 112818 127167
1 131322 154428 90611
2 11014 192282
2 41925 115417
2 5816 159028
2 111819 126655
2 37293 172866
2 27835 145099
2 124446 162824
2 104521 118016
2 40376 127391
1 195318 195319 149596
2 41040 179839
2 61847 94626
2 69878 181705
2 28968 179132
2 132543...

output:

result:

wrong answer Answer contains longer sequence [length = 200000], but output contains 0 elements

Test #14:

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

input:

199995 199998 199998
1 159195 199995 13044
2 86976 157151
1 64762 102114 152625
1 61813 63647 178420
1 82889 85481 125381
1 51586 54321 77506
2 45182 109756
1 181575 184132 133556
2 28331 132281
2 17325 40861
2 42257 191103
2 147228 198059
2 75171 155696
1 139100 140799 154126
1 188327 190311 76827
...

output:

result:

wrong answer Answer contains longer sequence [length = 199998], but output contains 0 elements

Test #15:

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

input:

199999 199996 200000
1 179926 199999 32711
1 1042 1044 112146
2 26640 43359
1 178347 178351 169789
2 32064 164957
2 81951 117742
1 179853 179856 73377
2 66862 193241
2 10596 28181
2 49117 162750
1 13331 13333 43998
2 26996 197910
1 161366 161369 84391
2 127515 184183
1 66412 66416 97202
2 49708 5634...

output:

result:

wrong answer Answer contains longer sequence [length = 200000], but output contains 0 elements

Test #16:

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

input:

200000 200000 200000
1 59821 200000 173244
1 190307 190309 110936
1 112341 112342 4761
1 124738 124740 84834
1 3047 3049 102534
2 114052 180833
2 72832 109679
2 84797 91295
1 191583 191584 141834
1 185318 185320 87703
1 117000 117002 109533
1 80539 80540 105603
1 24207 24209 111543
1 83298 83299 140...

output:

result:

wrong answer Answer contains longer sequence [length = 200000], but output contains 0 elements

Test #17:

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

input:

500000 500000 500000
2 430331 460074
1 364723 500000 100669
1 250319 250342 82754
1 438542 441692 403146
1 463281 463283 433598
2 257762 468063
2 48944 155558
2 353640 481169
1 84674 84675 290827
2 146697 229831
2 468564 488452
2 5108 66751
1 23182 45112 201883
2 282890 447793
1 32871 33375 376198
1...

output:

result:

wrong answer Answer contains longer sequence [length = 500000], but output contains 0 elements

Test #18:

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

input:

500000 499995 499999
2 227886 411572
2 211683 333769
1 250096 500000 235662
1 426728 426927 304290
2 57626 245045
2 274989 390864
2 128937 178776
1 131741 131862 102941
1 98436 98438 22052
1 166478 166479 223278
1 450334 450336 468682
1 235946 235947 469845
1 472838 472839 386149
1 94197 94199 37254...

output:

result:

wrong answer Answer contains longer sequence [length = 499999], but output contains 0 elements

Test #19:

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

input:

500000 500000 500000
1 483553 500000 33628
1 469113 469115 99122
2 331771 461807
2 132277 227909
1 409018 409020 67790
2 239961 327023
2 71363 250145
2 194504 394975
2 112739 357223
2 29586 226312
1 365927 365929 56596
2 37108 464107
2 260079 467849
1 132248 132250 77986
2 192853 237448
2 361959 386...

output:

result:

wrong answer Answer contains longer sequence [length = 500000], but output contains 0 elements

Test #20:

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

input:

499999 499999 499996
2 212908 238055
1 460268 499999 317714
2 420753 465452
1 184130 194219 347230
1 24358 31202 484414
2 261874 280744
1 382916 389593 121902
2 998 230297
1 83691 94553 138191
2 357537 469176
1 478043 489289 9664
2 49390 163924
1 496313 499999 485644
2 307553 482205
1 148359 158827 ...

output:

result:

wrong answer Answer contains longer sequence [length = 499996], but output contains 0 elements
English 繁體中文 简体中文

伺服器時間: 2025-02-06 22:08:36 | 開源專案