oj.uz

Submission #970753

# Submission time Handle Problem Language Result Execution time Memory
970753 2024-04-27T08:09:08 Z Ludissey XORanges (eJOI19_xoranges) C++14
38 / 100
 68 ms 9580 KB 
#include <bits/stdc++.h>
#define int long long
#define sz(a) (int)a.size()
#define all(x) (x).begin(), (x).end()
using namespace std;

struct FenwickTree{
    vector<int> bit;
    int n;
    FenwickTree(int vn){
        this->n=vn;
        bit.resize(vn,0);
    }
    FenwickTree(vector<int> const &a) : FenwickTree(sz(a)) {
        for (int i = 0; i < sz(a); i++) add(i, 0, a[i]);
    }
    int sum(int r){
        int ret=0;
        for (; r>=0; r=(r&(r+1))-1) ret=ret^bit[r];
        return ret;
    }
    int sum(int l, int r){
        return sum(l-1)^sum(r);
    }
    void add(int r, int prev, int delta){
        for (; r<n; r=(r|(r+1))) {
            bit[r]=bit[r]^prev;
            bit[r]=bit[r]^delta;
        }
    }
};



signed main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int n,q; cin >> n>>q;
    vector<int> uneven(n/2);
    vector<int> even((n+1)/2);
    for (int i = 0; i < n; i++)
    {
        int a; cin >> a;
        if(i%2) uneven[i/2]=a;
        else even[i/2]=a;
    }
    FenwickTree evn(even);
    FenwickTree unevn(uneven);

    for (int i = 0; i < q; i++)
    {
        int t,a,b; cin >> t >> a >> b;
        if(t==1){
            a--;
            if(a%2==0) evn.add(a/2, even[a/2], b);
            else unevn.add(a/2, uneven[a/2], b);
        }else{
            a--; b--;
            if((b-a+1)%2==0) cout << "0\n";
            else {
                if(a%2==0) cout << evn.sum(a/2, b/2) << "\n";
                else cout << unevn.sum(a/2, b/2) << "\n";
            }
        }
    }
    return 0;
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 9404 KB Output is correct
2 Correct 65 ms 9556 KB Output is correct
3 Correct 66 ms 9580 KB Output is correct
4 Correct 62 ms 9296 KB Output is correct
5 Correct 67 ms 9324 KB Output is correct

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -