QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#128099#5022. 【模板】线段树pandapythoner#0 2509ms10596kbC++202.3kb2023-07-20 15:51:532024-07-04 00:47:22

Judging History

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

  • [2024-07-04 00:47:22]
  • 评测
  • 测评结果：0
  • 用时：2509ms
  • 内存：10596kb
查看
  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-20 15:51:53]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define flt double
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()

mt19937 rnd(234);
const ll inf = 1e18;

struct ask {
    int t, l, r;
};

int n, q;
vector<ll> a;
vector<ask> asks;
vector<ll> rs;

void solve_slow() {
    rs.clear();
    rs.reserve(q + n);
    auto b = a;
    for (auto [t, l, r] : asks) {
        if (t == 1) {
            for (int i = r; i > l; i -= 1) {
                b[i] ^= b[i - 1];
            }
        } else {
            rs.push_back(b[l]);
        }
    }
    for (int i = 0; i < n; i += 1) {
        rs.push_back(b[i]);
    }
}


void solve_d(){
    rs.clear();
    rs.reserve(q + n);
    auto b = a;
    int cnt = 0;
    for (auto [t, l, r] : asks) {
        if (t == 1) {
            cnt += 1;
        } else {
            
        }
    }
    for(int j = 0; (1 << j) <= cnt; j += 1){
        if((cnt >> j) & 1){
            for(int i = n; i >= (1 << j); i -= 1){
                b[i] ^= b[i - (1 << j)];
            }
        }
    }
    for (int i = 0; i < n; i += 1) {
        rs.push_back(b[i]);
    }
}


bool is_d(){
    for(auto [t, l, r]: asks){
        if(t == 1){
            if(l != 0 || r != n - 1){
                return false;
            }
        }
    }
    return true;
}


int32_t main() {
    if (1) {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
    }
    int t;
    cin >> t;
    while (t--) {
        cin >> n >> q;
        a.resize(n);
        for (int i = 0; i < n; i += 1) {
            cin >> a[i];
        }
        asks.resize(q);
        for (int i = 0; i < q; i += 1) {
            int t;
            cin >> t;
            if (t == 1) {
                int l, r;
                cin >> l >> r;
                --l;
                --r;
                asks[i] = ask{t, l, r};
            } else {
                int pos;
                cin >> pos;
                --pos;
                asks[i] = ask{t, pos, 0};
            }
        }
        if(is_d()){
            solve_d();
        } else{
            solve_slow();
        }
        for (auto x : rs) {
            cout << x << "\n";
        }
    }
    return 0;
}
源文件, 语言: C++20

詳細信息

Subtask #1:

score: 0
Wrong Answer

Test #1:

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

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
Wrong Answer
time: 1ms
memory: 3604kb

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:

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
844762646...

result:

wrong answer 1st numbers differ - expected: '1015342581', found: '898798734'

Subtask #2:

score: 0
Wrong Answer

Test #6:

score: 0
Wrong Answer
time: 2509ms
memory: 10596kb

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 Output contains longer sequence [length = 550078], but answer contains 300080 elements

Subtask #3:

score: 0
Time Limit Exceeded

Test #10:

score: 0
Time Limit Exceeded

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
0
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
1
1
1
1
1
1
0
1
1
1
1
1
0
1
1
0
...

result:

Subtask #4:

score: 0
Wrong Answer

Test #14:

score: 0
Wrong Answer
time: 66ms
memory: 10200kb

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:

309331355
433864889
1036906976
890579305
78425531
882836608
601960742
81982419
594442808
198555617
563889846
997433190
1022752394
25536352
782232730
344553173
981220289
296456523
320002663
121356743
535851733
97803394
600353933
66606776
1019813362
246066672
220901702
1048300305
671702139
317588227
9...

result:

wrong answer 1st numbers differ - expected: '611117059', found: '309331355'

Subtask #5:

score: 0
Runtime Error

Test #18:

score: 0
Runtime Error

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:

Subtask #6:

score: 0
Skipped

Dependency #5:

0%

Subtask #7:

score: 0
Skipped

Dependency #5:

0%

Subtask #8:

score: 0
Skipped

Dependency #1:

0%
English 繁體中文 简体中文

伺服器時間: 2025-02-01 21:57:42 | 開源專案