QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#524222#5022. 【模板】线段树Max_s_xaM41 515ms9600kbC++174.1kb2024-08-19 13:20:042024-08-19 13:20:05

Judging History

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

  • [2024-08-19 13:20:05]
  • 评测
  • 测评结果:41
  • 用时:515ms
  • 内存:9600kb
  • [2024-08-19 13:20:04]
  • 提交

answer

#include <iostream>

typedef long long ll;
typedef double lf;

// #define DEBUG 1
struct IO
{
    #define MAXSIZE (1 << 20)
    #define isdigit(x) (x >= '0' && x <= '9')
    char buf[MAXSIZE], *p1, *p2;
    char pbuf[MAXSIZE], *pp;
    #if DEBUG
    #else
    IO() : p1(buf), p2(buf), pp(pbuf) {}
    ~IO() {fwrite(pbuf, 1, pp - pbuf, stdout);}
    #endif
    #define gc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin), p1 == p2) ? ' ' : *p1++)
    #define blank(x) (x == ' ' || x == '\n' || x == '\r' || x == '\t')

    template <typename T>
    void Read(T &x)
    {
        #if DEBUG
        std::cin >> x;
        #else
        bool sign = 0; char ch = gc(); x = 0;
        for (; !isdigit(ch); ch = gc())
            if (ch == '-') sign = 1;
        for (; isdigit(ch); ch = gc()) x = x * 10 + (ch ^ 48);
        if (sign) x = -x;
        #endif
    }
    void Read(char *s)
    {
        #if DEBUG
        std::cin >> s;
        #else
        char ch = gc();
        for (; blank(ch); ch = gc());
        for (; !blank(ch); ch = gc()) *s++ = ch;
        *s = 0;
        #endif
    }
    void Read(char &c) {for (c = gc(); blank(c); c = gc());}

    void Push(const char &c)
    {
        #if DEBUG
        putchar(c);
        #else
        if (pp - pbuf == MAXSIZE) fwrite(pbuf, 1, MAXSIZE, stdout), pp = pbuf;
        *pp++ = c;
        #endif
    }
    template <typename T>
    void Write(T x)
    {
        if (x < 0) x = -x, Push('-');
        static T sta[35];
        int top = 0;
        do sta[top++] = x % 10, x /= 10; while (x);
        while (top) Push(sta[--top] ^ 48);
    }
    template <typename T>
    void Write(T x, char lst) {Write(x), Push(lst);}
} IO;
#define Read(x) IO.Read(x)
#define Write(x, y) IO.Write(x, y)
#define Put(x) IO.Push(x)

using namespace std;

const int MAXN = 25e4 + 10, MAXM = 1e5 + 10;
const int B = 256, MAXB = 1e3 + 10;

int n, q;

int a[MAXN], b[MAXN], c[MAXN];
int bel[MAXN], L[MAXB], mid[MAXB], R[MAXB];
int tag[MAXB];

inline void Cpy1(int x) { for (int i = L[x]; i <= mid[x]; i++) c[i] = b[i]; for (int i = mid[x] + 1; i <= R[x]; i++) c[i] = a[i]; }
inline void Cpy2(int x) { for (int i = L[x]; i <= mid[x]; i++) b[i] = c[i]; for (int i = mid[x] + 1; i <= R[x]; i++) a[i] = c[i]; }
inline void Pushdown(int x)
{
    Cpy1(x);
    for (int i = 1; i <= tag[x]; i <<= 1)
        if (tag[x] & i)
            for (int j = R[x] - i; j >= L[x]; j--)
                c[j + i] ^= c[j];
    tag[x] = 0;
}
inline void Update(int x, int l, int r)
{
    if (x == 1) return;
    l = max(l, L[x]), r = min(r, R[x]);
    Pushdown(x);
    for (int i = r - 1; i >= l; i--) c[i + 1] ^= c[i];
    Cpy2(x);
}
inline void Rebuild()
{
    for (int x = 2; x <= bel[n]; x++)
    {
        Pushdown(x);
        for (int i = mid[x] + 1; i <= R[x]; i++) a[i] = c[i];
        if (x == 2) for (int i = L[x]; i <= mid[x]; i++) a[i] = c[i];
    }
    for (int i = 1; i <= n; i++) b[i] = a[i];
}
inline int Query(int k)
{
    int x = (bel[k] == 1 ? 2 : bel[k]), res = 0;
    Cpy1(x);
    for (int i = 0; i <= tag[x] && k - i >= L[x]; i++)
        if ((tag[x] & i) == i) res ^= c[k - i];
    return res;
}

int main()
{
    #if DEBUG
    #else
    ios::sync_with_stdio(0), cin.tie(0);
    #endif
    int T, _n;
    Read(T), Read(n), Read(q), _n = n;
    for (int i = 1; i <= n; i++) Read(a[i]), b[i] = a[i];
    if (n < B + 1) n = B + 1;
    for (int i = 1; i <= n; i++) bel[i] = (i - 1) / B + 1;
    for (int i = 2; i <= bel[n]; i++) L[i] = (i - 2) * B + 1, mid[i] = (i - 1) * B, R[i] = min(n, i * B);

    int _ = 0, op, l, r;
    while (q--)
    {
        Read(op), Read(l);
        if (op == 1)
        {
            Read(r);
            for (int i = bel[l]; i <= bel[r] + 1 && i <= bel[n]; i++)
                if (i <= bel[l] - 1 || i >= bel[r]) Update(i, l, r);
                else tag[i]++;
            if (++_ == B) Rebuild(), _ = 0;
        }
        else cout << Query(l) << '\n';
    }
    Rebuild();
    for (int i = 1; i <= _n; i++) cout << a[i] << '\n';
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 8
Accepted
time: 1ms
memory: 7748kb

input:

1
6 6
1 1 5 1 9 4
2 5
1 2 5
2 4
1 3 6
2 6
1 1 6

output:

9
4
12
1
0
5
4
12
0

result:

ok 9 numbers

Test #2:

score: 8
Accepted
time: 1ms
memory: 7708kb

input:

1
999 997
898798734 979577086 45974352 1013270193 1053191143 533594258 372426673 947830633 122319874 368651315 866424479 109724831 427664962 558099346 764830489 326451620 322471751 525780385 746941281 670254345 586958579 979544209 743892216 436404384 291681381 979530194 998929567 367716728 909076993...

output:

1015342581
962986689
965094083
871356796
835210392
172023195
63088572
606096781
569607283
436055720
154605892
663158209
154605892
776365236
281312240
62398687
182713417
604764772
816533315
793514230
325061861
806973284
91749226
283750235
198953311
170342298
432592070
809908556
683302450
40932811
669...

result:

ok 1996 numbers

Test #3:

score: 0
Wrong Answer
time: 1ms
memory: 7672kb

input:

1
999 997
89872218 906651903 120274311 490547919 291584020 755757065 24942887 707247173 763024744 68250332 114193028 999245166 140381610 171802205 399965713 299821903 907998064 906075056 427270276 335420206 708713870 492555323 359637714 197212814 35225369 1011322274 912003632 633998134 1026276199 85...

output:

89872218
860962725
880411170
692529389
237795334
135318079
789613645
880636905
491524014
744263612
632572083
198347057
472463308
846502731
73827652
233355071
604279240
967548524
351092622
393347346
862816119
756989299
471664753
6557396
610343503
67908103
947083411
517006588
483455034
739256725
17118...

result:

wrong answer 3rd numbers differ - expected: '120274311', found: '880411170'

Subtask #2:

score: 0
Wrong Answer

Test #6:

score: 0
Wrong Answer
time: 346ms
memory: 8560kb

input:

2
249998 99999
1048488450 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

wrong answer 2686th numbers differ - expected: '1048488450', found: '0'

Subtask #3:

score: 0
Wrong Answer

Test #10:

score: 0
Wrong Answer
time: 339ms
memory: 8524kb

input:

3
250000 99999
1 1 1 1 1 0 1 0 1 1 0 1 0 1 1 1 1 1 1 0 1 0 1 0 1 1 1 0 0 0 0 0 1 0 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 1 1 0 0 0 1 0 1 0 0 1 0 0 1 1 1 0 0 0 1 1 1 1 1 1 0 0 1 1 1 1 0 0 0 0 1 1 0 0 1 1 0 1 1 0 1 1 0 1 1 1 0 0 1 1 0 0 1 1 1 0 1 1 1 1 1 0 1 0 1 0 0 1 0 1 1 1 0 1 1 0 1 1 0 1 0 0 1 1...

output:

0
0
0
0
1
0
1
0
0
0
0
0
1
0
0
1
0
0
0
0
1
1
0
1
1
0
1
0
1
1
1
0
1
1
1
0
1
1
1
1
1
1
1
0
1
0
0
0
1
1
0
1
0
0
1
1
0
1
0
0
0
0
1
1
1
0
1
1
0
0
0
1
1
0
1
0
1
1
0
1
0
1
1
0
1
1
0
0
1
0
1
0
1
0
1
1
1
1
0
0
0
1
1
0
0
1
1
1
1
0
1
1
1
1
1
0
1
0
1
1
0
1
1
1
0
0
1
1
1
0
0
0
1
0
0
0
1
1
1
1
0
1
1
1
1
1
0
1
1
0
...

result:

wrong answer 106th numbers differ - expected: '0', found: '1'

Subtask #4:

score: 13
Accepted

Test #14:

score: 13
Accepted
time: 130ms
memory: 8568kb

input:

4
249996 99997
309331355 195839266 912372930 57974187 363345291 954954162 650621300 389049294 821214285 263720748 231045308 844370953 768579771 664766522 681320982 124177317 32442094 297873605 743179832 1073656106 443742270 235746807 1054294813 974443618 422427461 307448375 1018255356 20105813 36821...

output:

611117059
866091251
300188933
0
478915924
1053588351
453142424
897441996
60971719
748656483
600408393
0
303761852
983037069
883016404
332332552
1069626159
860304528
851235295
561276840
389049294
681320982
484263000
351914192
620106464
667080579
733146026
375466744
0
347632358
737240082
321494160
0
3...

result:

ok 299980 numbers

Test #15:

score: 13
Accepted
time: 30ms
memory: 8572kb

input:

4
249996 99997
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
707358968
0
0
0
165359261
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
301087804
0
0
0
0
...

result:

ok 348991 numbers

Test #16:

score: 13
Accepted
time: 217ms
memory: 9600kb

input:

4
249996 100000
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

output:

0
0
0
0
0
0
0
0
412012733
460047966
0
0
0
94984489
0
0
0
0
1010860949
0
0
0
336953687
0
0
0
0
0
655564155
25780913
662736870
0
0
0
0
0
679917886
0
998313118
0
0
0
0
0
171168202
20014081
336953687
0
0
0
0
1018313742
0
997397452
0
849015355
0
16108473
0
0
0
504340154
0
397006673
0
0
0
0
0
0
290851883
...

result:

ok 250950 numbers

Test #17:

score: 13
Accepted
time: 131ms
memory: 8572kb

input:

4
249999 99998
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
956381802
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1021925694
922314342
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0...

result:

ok 300062 numbers

Subtask #5:

score: 12
Accepted

Test #18:

score: 12
Accepted
time: 228ms
memory: 9180kb

input:

5
249997 99997
860563869 428592873 58576739 761578583 47999879 294581118 988847649 569566599 640106250 440172702 178219106 966598261 763325707 846927552 877923116 145156535 246778542 25949847 507939778 116507169 555239769 259969305 328955819 171606729 535970481 121608060 4437163 370976515 713807003 ...

output:

860563869
717285236
452329866
773393204
485721677
965902221
831024341
890990738
455498944
92913689
556500009
102303365
264515518
445496274
654612933
988537886
165104807
364103659
952755344
576499197
775866335
1003839403
606880290
1006459039
1005979559
588810854
592470517
765610807
123827263
86327854...

result:

ok 249997 numbers

Test #19:

score: 12
Accepted
time: 221ms
memory: 8592kb

input:

5
249998 100000
1055401468 532211763 131695513 214363867 831955115 452049333 729606869 69161863 428100767 90941242 729034740 90774107 332674212 930394013 601735907 104187221 1017052616 31513597 868964816 1054507185 926990168 75998133 1039482150 781325037 680316641 471310435 780674964 330142918 10271...

output:

1055401468
532211763
131695513
214363867
831955115
452049333
729606869
69161863
428100767
90941242
729034740
90774107
332674212
930394013
601735907
104187221
1017052616
31513597
868964816
1054507185
926990168
75998133
1039482150
781325037
680316641
471310435
780674964
330142918
1027184688
750941669
...

result:

ok 249998 numbers

Test #20:

score: 12
Accepted
time: 151ms
memory: 9096kb

input:

5
249999 65535
206222027 1038492265 248834236 84032585 981309757 273118313 589015947 1002433231 482381717 342803573 48417408 196676553 50772773 199061806 637191822 974252922 289297532 48985206 415073252 593023329 9193325 632026989 55397875 918843456 476033799 664362612 383124333 926156312 133237149 ...

output:

206222027
833392802
1064859678
981091415
515434
272673027
861602440
149219399
337930194
4891559
44591399
152134382
169335243
30058725
607153771
505513233
253743469
234136859
357115647
907147166
916304115
322324382
276499053
650082861
987810090
494507870
196056115
1016828459
996842422
602075803
53081...

result:

ok 249999 numbers

Subtask #6:

score: 16
Accepted

Dependency #5:

100%
Accepted

Test #21:

score: 16
Accepted
time: 50ms
memory: 8568kb

input:

6
249999 99998
234899190 294042590 622374272 592723113 719234312 350081074 842293736 684699037 330659123 145765638 707972395 212219898 665588169 1002656251 377046330 569400576 515159132 246671859 367313733 436193585 1056439739 889727758 441186237 802117710 672761337 1013893805 760105556 959623512 10...

output:

416342969
682608684
897388094
564167584
723521403
277032360
571217154
804968920
345689708
20430886
2669323
397914023
682539746
743678615
902811241
79705781
117866215
29290630
463835109
948618157
996425135
333840809
879030503
756069154
651860206
62844241
563208222
473841643
306068071
945671265
755499...

result:

ok 340922 numbers

Test #22:

score: 16
Accepted
time: 211ms
memory: 8920kb

input:

6
249999 100000
440794180 373448998 924631752 1029747555 1025197824 772227211 39885098 362601933 28836613 109487897 1065155159 170512808 1054469991 504110707 412993411 172546234 861597564 320825471 551313957 607675657 108258007 713412450 183442416 266654936 968422736 230720896 824830683 653610670 10...

output:

98475211
195528780
696822840
514087003
829956911
329558613
774154603
206369270
459595700
862203687
923064620
893978487
446169540
162819606
623685563
362210402
266466497
536712664
619196444
636251427
621982108
29822991
825999568
1023819390
976493671
1002043855
522408337
819431256
487829199
839724281
...

result:

ok 258991 numbers

Test #23:

score: 16
Accepted
time: 106ms
memory: 9336kb

input:

6
249997 99996
858874420 647336645 792849435 487078011 572740439 880018128 888095353 792485726 562377029 925278515 769802546 863097170 1024187886 86325040 278572503 296068408 305389187 156383560 564344122 985485618 352643959 100128572 51313514 939087520 196935800 175799309 561623994 704660004 265677...

output:

432854594
738728738
262426424
538231132
618966731
444275244
553066863
973600567
229016163
137911233
474170208
151027732
489894673
52703384
860246793
29393762
677235209
677602352
528898618
55456646
169243833
468519972
485795189
732890985
359625381
702665297
407151543
225249034
52286602
259376944
8254...

result:

ok 316451 numbers

Test #24:

score: 16
Accepted
time: 107ms
memory: 8532kb

input:

6
249996 99998
397969543 991721013 639702540 604481296 351426688 333740122 724850461 729736402 79245133 118976945 532880690 120525599 614643743 490724539 699303708 215416342 87908710 952073016 139568877 646769946 252759252 177392171 163619316 265404108 1038973785 470689235 333983939 483290379 506253...

output:

754257332
1052657251
965428426
49222948
557704117
889334077
162967177
294432927
874425580
892648866
412985497
714268964
951853077
64552159
353730625
303006842
751382734
843554529
77391004
575486290
608292876
351321372
429291997
40738032
302573118
696246768
219586525
303187951
464261520
207417065
940...

result:

ok 317038 numbers

Test #25:

score: 16
Accepted
time: 104ms
memory: 8572kb

input:

6
249998 99999
74522082 95255299 47435923 65293311 383519294 730856524 280602586 438150212 797041603 855416036 351530040 132807245 542585310 141165127 621841979 482556601 64204348 505740339 462640304 741843044 862320843 658389156 400859300 211413099 262112183 559589336 1020279140 419610155 7952237 8...

output:

1045894056
630057317
929438146
334646479
346277018
348756210
981696510
903965260
25853408
1064725614
1002783967
676558112
133571240
729988430
561338032
29334387
773547167
92854356
301810906
127798863
1067419577
48822296
572267332
888557141
411790443
782015691
296921318
861559634
526869577
249098463
...

result:

ok 317041 numbers

Test #26:

score: 16
Accepted
time: 104ms
memory: 9456kb

input:

6
249998 99997
577746632 849120672 736337072 70635835 1013824888 1021260621 541416538 1005818681 278158852 893179416 959378713 834506551 88091311 524975252 624021199 343226213 405214456 366338193 747080860 620032308 395804065 67500831 684949729 1024468310 633953451 714771601 102914368 82038716 10389...

output:

706515843
840382939
308759114
794493220
26217834
598937432
701146310
358149620
300917798
445590452
213060422
925053200
288408262
554925044
132231526
588760212
774258858
113417756
82987278
149295032
3610090
265306580
883044706
257188428
671846846
258199312
489653506
965163452
87049738
359044380
45775...

result:

ok 317039 numbers

Test #27:

score: 16
Accepted
time: 144ms
memory: 8636kb

input:

6
249998 100000
634924332 130071305 345967772 29577538 897204306 852816395 507355338 816369280 1058372196 1039530725 225035235 1001646366 706532591 139562806 151046291 666098137 464965567 848982745 999568327 925760429 152064227 621233133 401251501 876360663 529097894 195375821 289367217 751641045 35...

output:

383000531
1017346284
325626122
695917821
705132789
90722032
97893415
308759240
431359599
438441373
960506652
214053236
399084533
84622208
861963168
521868009
577802595
647595327
871097082
250561060
341202823
652714801
1020990292
104653506
713664830
1043687822
871264432
403461930
921298687
780777098
...

result:

ok 300095 numbers

Subtask #7:

score: 0
Wrong Answer

Dependency #5:

100%
Accepted

Test #28:

score: 0
Wrong Answer
time: 515ms
memory: 8652kb

input:

7
249999 99998
1028875149 290751586 85260062 527433830 11253389 381520904 163374626 882045937 328797576 362761070 107207247 721987314 848366187 492948114 913994419 980121735 553555299 238308272 517289115 493658637 535863518 18389830 59694996 328276770 970756488 409396240 782649706 568544673 92874299...

output:

1028875149
290751586
85260062
527433830
11253389
381520904
163374626
882045937
328797576
362761070
107207247
721987314
848366187
492948114
913994419
980121735
553555299
238308272
517289115
493658637
535863518
18389830
59694996
328276770
970756488
409396240
782649706
568544673
928742990
968618764
843...

result:

wrong answer 2nd numbers differ - expected: '738715631', found: '290751586'

Subtask #8:

score: 0
Skipped

Dependency #1:

0%