Untitled
unknown
plain_text
a year ago
13 kB
6
Indexable
#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
#include <stdio.h>
extern void init(int N, int mSubscriber[]);
extern int subscribe(int mId, int mNum);
extern int unsubscribe(int mId, int mNum);
extern int count(int sId, int eId);
extern int calculate(int sId, int eId);
/////////////////////////////////////////////////////////////////////////
#define MAX_N 200000
#define CMD_INIT 100
#define CMD_SUBSCRIBE 200
#define CMD_UNSUBSCRIBE 300
#define CMD_COUNT 400
#define CMD_CALCULATE 500
static int mSubscriber[MAX_N];
static bool run() {
int q;
scanf("%d", &q);
int n, mId, mNum, sId, eId;
int cmd, ans, ret = 0;
bool okay = false;
for (int i = 0; i < q; ++i) {
scanf("%d", &cmd);
switch (cmd) {
case CMD_INIT:
okay = true;
scanf("%d", &n);
for (int j = 0; j < n; ++j) {
scanf("%d", &mSubscriber[j]);
}
init(n, mSubscriber);
break;
case CMD_SUBSCRIBE:
scanf("%d %d %d", &mId, &mNum, &ans);
ret = subscribe(mId, mNum);
if (ans != ret)
okay = false;
break;
case CMD_UNSUBSCRIBE:
scanf("%d %d %d", &mId, &mNum, &ans);
ret = unsubscribe(mId, mNum);
if (ans != ret)
okay = false;
break;
case CMD_COUNT:
scanf("%d %d %d", &sId, &eId, &ans);
ret = count(sId, eId);
if (ans != ret)
okay = false;
break;
case CMD_CALCULATE:
scanf("%d %d %d", &sId, &eId, &ans);
ret = calculate(sId, eId);
if (ans != ret)
okay = false;
break;
default:
okay = false;
break;
}
}
return okay;
}
int main() {
setbuf(stdout, NULL);
freopen("input.txt", "r", stdin);
int T, MARK;
scanf("%d %d", &T, &MARK);
for (int tc = 1; tc <= T; tc++) {
int score = run() ? MARK : 0;
printf("#%d %d\n", tc, score);
}
return 0;
}
///
#define N_global 200000
#define SUM 0
#define MAX 1
#define MIN 2
#define g(a, b) a>b ? a : b
#define l(a, b) a<b ? a : b
int st[3][4*N_global];
int d[N_global+2];
int n;
void update_st(int id)
{
st[SUM][id] = st[SUM][2*id] + st[SUM][2*id + 1];
st[MAX][id] = g(st[MAX][2*id], st[MAX][2*id + 1]);
st[MIN][id] = l(st[MIN][2*id], st[MIN][2*id + 1]);
}
void build (int id, int l, int r)
{
if (l == r)
{
st[SUM][id] = st[MAX][id] = st[MIN][id] = d[l];
}
else
{
int mid = (l+r)/2;
build(2*id, l, mid);
build(2*id + 1, mid+1, r);
update_st(id);
}
}
void update(int id, int l, int r, int i)
{
if (l == r)
{
st[SUM][id] = st[MAX][id] = st[MIN][id] = d[i];
}
else
{
int mid = (l+r)/2;
if (l <= i && i <= mid)
{
update(2*id, l, mid, i);
}
else
{
update(2*id + 1, mid+1, r, i);
}
update_st(id);
}
}
int get (int id, int m, int l, int r, int u, int v)
{
if (u > r || v < l)
{
return m == MIN ? N_global : 0;
}
if (u <= l && v >= r)
{
return st[m][id];
}
int mid = (l+r)/2;
int v1 = get(2*id, m, l, mid, u, v);
int v2 = get(2*id+1, m, mid+1, r, u, v);
return m == SUM ? v1 + v2 : m == MAX ? g(v1, v2) : l(v1, v2);
}
void init(int N, int a[])
{
n = N;
for (int i = 0; i <= n; i++)
{
d[i+1] = a[i];
}
build(1, 1, n);
}
int subscribe(int mId, int mNum)
{
d[mId] += mNum;
update(1, 1, n, mId);
return d[mId];
}
int unsubscribe(int mId, int mNum)
{
return subscribe(mId, -mNum);
}
int count(int sId, int eId)
{
return get(1, SUM, 1, n, sId, eId);
}
int calculate(int sId, int eId)
{
return get(1, MAX, 1, n, sId, eId) - get(1, MIN, 1, n, sId, eId);
}
///
25 100
9
100 10
50
35
100
20
45
210
30
400
750
70
400 1 5 250
200 3 20 120
400 1 5 270
300 8 100 300
400 7 9 1080
200 9 200 950
200 4 50 70
500 1 10 920
100
100 100
2346
2607
3776
6925
3574
5179
460
9193
1794
8311
168
245
3198
6083
1572
929
8586
2847
4528
781
5942
3563
8076
7305
7954
8711
2808
757
1646
8355
7076
2001
9754
6735
784
1757
4790
8315
6108
2457
6930
8423
4552
4677
6110
4003
4020
5713
2042
8431
7328
509
8758
4283
9228
9673
6706
3287
3624
3029
5358
8291
4276
8033
9098
9311
6080
2317
4198
3771
8588
4281
5058
1367
3192
1941
6318
9891
9412
8417
8458
1631
6176
9805
1606
6555
6364
4633
6802
5671
376
7125
6862
5363
6996
8881
3386
3951
6624
2013
500 7 94 9723
500 2 91 9723
500 9 92 9723
200 76 4017 5958
500 7 92 9723
400 6 91 451386
500 7 98 9723
500 2 95 9723
300 95 2836 4160
200 58 2687 5974
500 9 94 9723
300 46 631 3372
500 1 100 9723
200 32 9521 11522
300 71 1756 6832
300 66 3815 5496
200 77 1886 8204
400 10 97 478429
300 71 6064 768
400 2 95 493606
300 45 1282 4828
300 14 675 5408
300 17 5274 3312
200 80 445 8862
400 5 92 457127
400 6 91 446428
400 7 100 489614
500 2 91 11354
500 9 96 11354
300 2 967 1640
300 67 1844 4236
400 6 91 444584
400 7 100 487770
400 8 91 438945
500 9 96 11354
400 10 91 427958
400 9 94 449102
400 10 93 441945
400 1 96 495236
200 10 631 8942
400 7 100 488401
300 36 1681 76
200 59 9584 13208
400 4 99 509969
400 7 100 496304
300 96 3477 5404
400 7 98 484190
300 90 5167 504
500 7 100 13132
400 8 91 442312
300 57 78 6628
200 92 8721 15846
200 47 4032 8052
300 88 3017 1616
400 5 98 497434
200 74 6259 7626
400 5 94 486792
300 94 2155 3208
200 25 5618 13572
300 58 3447 2527
200 81 4638 13096
300 78 2159 7732
400 9 96 480445
300 8 1321 7872
200 3 1304 5080
300 26 7251 1460
500 7 94 15770
400 8 93 468294
500 7 98 15770
200 2 2887 4527
300 97 2878 508
500 4 95 15770
300 43 2064 2488
300 66 2395 3101
300 61 318 5040
200 8 9233 17105
500 7 100 17029
500 6 93 17029
400 7 92 466348
200 48 5413 11126
200 39 3828 9936
400 4 97 511409
300 57 4402 2226
400 4 91 471019
500 7 94 17029
200 10 5615 14557
300 33 5878 3876
400 8 93 477326
300 31 4584 2492
200 22 3507 7070
200 49 5418 7460
300 8 1661 15444
300 11 12 156
500 4 91 15368
200 89 6030 12832
400 4 97 515442
300 91 208 168
400 8 95 493184
300 33 1218 2658
200
100 500
5703
1816
485
2254
8835
388
8273
4458
4095
3824
6925
9398
5771
7388
3257
9778
6215
4648
4853
7486
467
9636
513
8778
2959
9536
3085
8486
5851
5100
361
7218
3639
1032
6005
3566
6163
5556
4433
7050
6543
7632
7149
8278
8875
2924
7033
4882
5863
632
5509
1470
3923
3924
1793
6746
527
9168
2669
1446
1195
8204
4825
2946
3863
9800
1845
318
9667
1140
2353
1914
6927
6048
5997
6550
6683
9292
1065
6850
903
4360
3125
1102
2659
9588
4833
2314
3167
7328
9005
1766
267
8332
3337
898
2423
6856
8869
2990
2819
7716
2337
1610
1151
1056
6397
2950
5243
1212
1385
7394
1591
152
3669
5166
6147
7284
5073
6378
1871
5168
2893
4662
6939
9404
1593
9298
7431
3864
853
8670
2035
7908
369
3482
6239
272
2429
9174
3547
1804
7001
6658
3895
7960
6965
2702
1395
4308
2689
6378
9695
5008
8989
1958
8027
7388
4617
6562
8119
3656
21
7406
7619
9092
5409
9658
3983
9776
6621
6230
6235
6236
2601
2274
7607
5256
341
4766
8355
9060
4481
8186
4463
2096
5805
3846
4235
300
3113
5890
2135
8344
8805
2206
2819
4340
1153
9754
8239
1280
3469
4438
2779
1724
8553
5714
8231
3384
1333
5374
3571
5636
1985
5162
8767
9200
9357
4422
5563
8204
3465
7970
9191
1208
7141
1742
3827
8772
7921
4522
3983
7664
509
726
1003
4828
3609
530
8743
3912
5925
5150
6531
6532
7009
9098
9967
2016
3165
3446
2251
5916
1385
1922
6471
5752
2469
7646
723
9556
8065
9498
959
2032
893
1334
9915
5916
3145
7762
7831
8632
3013
382
611
3588
6097
9274
7487
3760
4605
6342
1131
7596
4617
706
3223
2056
3381
4510
2883
8612
5969
4058
975
4064
2573
1814
523
5644
4569
9586
5303
5912
6293
318
8483
6100
5121
8810
1871
1520
2205
2438
1979
5804
3881
5714
3463
424
1381
9886
9923
3556
2641
6010
6959
960
7357
678
5019
8476
4617
5666
5735
1640
3317
3518
3059
6356
9281
2906
2079
5312
4701
3078
4811
7852
4633
8530
5975
2328
2773
6990
4403
7700
7473
650
3903
6496
1853
5750
1243
5516
8409
4098
2119
5576
5493
8798
6547
1396
9457
7898
8191
2672
8333
8918
8939
7692
8953
6466
7959
4872
5013
5646
5475
5460
5537
1706
7919
4672
1933
7814
3627
5324
7689
6818
5863
408
5381
3342
8691
308
2209
6666
5999
1360
4141
870
7563
6732
953
7026
7735
3624
2117
4990
2531
596
4881
9450
9887
3360
9213
614
6843
9452
2585
7842
9495
6344
9397
4590
4883
1524
2481
5114
2415
9360
2429
5510
475
2076
425
6146
5687
3432
5605
3470
7907
5268
1937
9882
2751
4304
8221
7206
5803
4204
6201
7730
1255
6520
7813
9294
4403
932
5489
8394
9119
4880
9245
8726
3115
9228
6489
3602
615
6664
1797
2494
4179
3684
6113
9194
4223
5824
989
6310
7419
7932
6377
9122
9559
8888
2053
3518
400 12 485 2353957
500 9 452 9946
200 14 8459 15847
300 135 112 257
200 50 3435 4067
300 225 2146 7045
300 328 3749 2261
300 497 5050 4509
500 28 457 9946
500 25 500 9946
200 194 2199 10543
400 13 458 2199027
500 24 467 10522
300 319 296 3585
300 312 8033 777
200 259 1184 3653
300 350 7531 321
200 189 1858 6093
500 10 457 15826
400 45 458 1999318
200 422 5279 5875
500 23 460 10522
500 14 453 15826
500 33 466 10522
400 16 477 2285163
300 197 598 2221
300 62 4599 3605
200 97 8366 10789
300 352 5313 3217
200 459 4864 13085
200 490 5579 11403
500 13 478 15826
200 240 693 1223
300 17 5946 269
300 318 3211 2593
200 157 9058 17085
400 28 479 2242186
200 235 8660 9169
300 478 4443 4785
200 253 3826 6077
300 488 3205 5989
300 359 2932 4541
300 478 191 4594
300 77 3938 2745
200 332 5253 5931
400 39 478 2188955
300 306 5775 137
400 37 458 2066891
300 160 245 6317
300 359 3444 1097
300 118 4271 3013
400 25 494 2323679
300 140 1321 7853
400 29 454 2071508
200 446 2467 4543
400 37 474 2162405
200 108 3117 6067
400 19 462 2182063
400 44 455 2001731
200 321 6894 10357
400 14 485 2346306
300 391 2064 3473
400 34 497 2306545
500 43 482 17064
400 50 459 1998728
200 283 36 4641
300 126 127 9277
300 371 708 4785
400 40 483 2198248
200 477 4822 7937
500 2 481 17064
400 31 452 2056997
200 298 1747 5811
200 345 2074 4153
300 460 2717 4489
300 51 3644 1865
400 26 487 2287031
500 31 498 17064
500 50 479 17064
500 1 484 17064
200 50 9755 13822
200 457 6578 9329
500 10 469 17064
200 355 5188 7961
500 18 483 17064
300 137 1078 5161
200 76 6825 13375
400 27 480 2279217
400 24 489 2336248
400 49 464 2059664
400 6 467 2317272
300 219 4892 4465
400 20 479 2310098
400 41 460 2084150
400 42 485 2215986
300 459 4704 8381
200 286 1403 8999
500 45 490 17064
400 36 499 2331007
500 27 482 17064
200 266 1951 3983
400 11 470 2304621
500 42 483 17064
500 17 488 17064
200 162 4467 8123
200 77 5914 8659
300 188 1989 1857
300 195 3652 5153
400 14 471 2292756
200 253 2758 8835
200 36 7369 10935
200 323 2328 3709
400 6 483 2420405
400 17 492 2393775
200 152 4381 10759
400 13 500 2482627
400 24 453 2149604
300 427 8508 705
200 490 1943 13346
300 115 884 2785
500 18 467 17064
200 461 7510 13313
300 488 5641 348
300 457 6782 2547
400 14 457 2216600
500 49 488 17064
400 38 457 2080698
500 19 468 17064
300 122 3439 1729
500 21 484 17064
300 88 825 1489
300 147 6344 621
200 366 6211 11727
500 39 474 17064
500 42 489 17064
300 227 6892 249
300 310 5859 241
400 33 464 2139946
400 34 467 2151895
300 299 828 1745
300 168 6689 2969
400 11 478 2351252
200 414 8139 14871
400 13 470 2284684
400 2 471 2340924
500 21 496 17064
200 198 6191 10531
200 309 9942 18425
300 432 2841 5001
500 15 482 18404
500 4 483 18404
300 161 7914 205
400 22 481 2306776
500 37 460 18404
300 50 9207 4615
300 117 3838 2309
500 46 475 18404
400 45 476 2134556
200 42 6059 13691
500 35 476 18404
400 4 477 2385316
200 423 2964 7845
500 44 497 18404
500 29 462 18404
200 468 7977 17271
500 35 452 18404
400 4 459 2268336
500 29 464 18404
400 24 499 2397029
200 391 9628 13101
400 36 497 2333666
500 27 486 18404
500 26 485 18404
200 147 4720 5341
200 86 4091 13679
500 23 498 18404
300 212 3941 1433
200 35 836 6841
500 28 461 18404
400 39 460 2091644
400 12 491 2431676
500 11 466 18404
300 490 6883 6463
300 193 746 1389
200 400 9821 16639
300 253 3326 5509
300 90 351 6977
200 413 1110 8673
200 96 1593 2491
200 463 7128 13329
200 174 4931 11167
500 37 458 18404
200 40 9069 16119
400 41 474 2197845
400 28 471 2257186
200 117 1518 3827
200 404 7249 10591
500 31 460 18404
200 110 123 1335Editor is loading...
Leave a Comment