oj.uz

Submission #821811

# Submission time Handle Problem Language Result Execution time Memory
821811 2023-08-11T17:33:45 Z synthesis XORanges (eJOI19_xoranges) C++17
100 / 100
 338 ms 20368 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fi first
#define se second
#define pii pair<int, int>
#define pb push_back
#define vi vector<int>
#define all(x) x.begin(), x.end()

using namespace std;
using namespace __gnu_pbds;
using ll = long long int;
using ull = unsigned long long int;
using ld = long double;

constexpr ll mod = 1e9 + 7;
constexpr ll INF = LONG_LONG_MAX;

int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

struct SegTree {
    int n;
    vector<ll> t;
    void build(vector<ll>& a, int v, int tl, int tr, bool type) {
        if (tl == 0 && tr == n - 1) {
            t.resize(4*n + 1);
        }
        if (tl == tr) {
            if (type) {
                t.at(v) = (tl&1 ? 0:a.at(tl));
            }
            else {
                t.at(v) = (tl&1 ? a.at(tl):0);
            }
        }
        else {
            int tm = (tl + tr)/2;
            build(a, v*2, tl, tm, type); 
            build(a, v*2 + 1, tm + 1, tr, type);
            t.at(v) = t.at(v*2)^t.at(v*2 + 1);
        }
        return;
    }
    ll query(int v, int tl, int tr, int l, int r) {
        if (l > r) {
            return 0;
        }
        if (l == tl && r == tr) {
            return t.at(v);
        }
        int tm = (tl + tr)/2;
        return query(v*2, tl, tm, l, min(r, tm))^query(v*2 + 1, tm + 1, tr, max(l, tm + 1), r);
    }
    void update(int v, int tl, int tr, int pos, int val, bool type) {
        if (tl == tr) {
            if (type) {
                t.at(v) = (tl&1 ? 0:val);
            }
            else {
                t.at(v) = (tl&1 ? val:0);
            }
        }
        else {
            int tm = (tl + tr)/2;
            if (pos <= tm) {
                update(v*2, tl, tm, pos, val, type);
            }
            else {
                update(v*2 + 1, tm + 1, tr, pos, val, type);
            }
            t.at(v) = t.at(v*2)^t.at(v*2 + 1);
        }
        return;
    } 
};

int main()
{
    //tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update> q;
    /*freopen("problemname.in", "r", stdin);
    freopen("problemname.out", "w", stdout);*/
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n, q, type, x;
    ll y;
    cin >> n >> q;
    vector<ll> a(n);
    for(ll& v:a) {
        cin >> v;
    }
    SegTree odd, even;
    odd.n = n, even.n = n;
    odd.build(a, 1, 0, n - 1, true);
    even.build(a, 1, 0, n - 1, false);
    while(q--) {
        cin >> type >> x >> y;
        if (type == 1) {
            --x;
            odd.update(1, 0, n - 1, x, y, true);
            even.update(1, 0, n - 1, x, y, false);
        }
        else {
            --x, --y;
            if ((y - x + 1)&1) {
                cout << (x&1 ? even.query(1, 0, n - 1, x, y):odd.query(1, 0, n - 1, x, y)) << endl;
            }
            else {
                cout << 0 << endl;
            }
        }
    }
    return 0;
}

Subtask #1
12.0 / 12.0

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

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 1 ms 328 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 5 ms 724 KB Output is correct
12 Correct 5 ms 724 KB Output is correct
13 Correct 10 ms 724 KB Output is correct
14 Correct 9 ms 852 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 318 ms 20368 KB Output is correct
2 Correct 312 ms 20364 KB Output is correct
3 Correct 338 ms 20368 KB Output is correct
4 Correct 290 ms 20080 KB Output is correct
5 Correct 304 ms 20064 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 1 ms 328 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 5 ms 724 KB Output is correct
12 Correct 5 ms 724 KB Output is correct
13 Correct 10 ms 724 KB Output is correct
14 Correct 9 ms 852 KB Output is correct
15 Correct 318 ms 20368 KB Output is correct
16 Correct 312 ms 20364 KB Output is correct
17 Correct 338 ms 20368 KB Output is correct
18 Correct 290 ms 20080 KB Output is correct
19 Correct 304 ms 20064 KB Output is correct
20 Correct 217 ms 20164 KB Output is correct
21 Correct 260 ms 20148 KB Output is correct
22 Correct 220 ms 20168 KB Output is correct
23 Correct 283 ms 20040 KB Output is correct
24 Correct 289 ms 20052 KB Output is correct