oj.uz

Submission #477823

# Submission time Handle Problem Language Result Execution time Memory
477823 2021-10-04T03:35:52 Z chungdinh XORanges (eJOI19_xoranges) C++14
100 / 100
 550 ms 11088 KB 
#include <iostream>
#include <vector>
#include <bitset>
#include <queue>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <stack>
#include <set>
#include <map>
#include <cassert>
#include <bits/stdc++.h>

using namespace std;

#define pb push_back

#define ll long long
#define ii pair<int,int>
#define pll pair<long long, long long>
#define fi first
#define se second
#define r first
#define c second

#define all(x) x.begin(), x.end()

ostream& operator << (ostream& os, pair<int, int> a) {
    return os << a.first << " : " << a.second;
}

#define endl '\n'
#define db(val) "["#val" = "<<(val)<<"] "
#define cntbit(x) __builtin_popcount(x)

const int N = 3e5 + 5;
const int iINF = 1e9;
const ll MOD = 1e9 + 7;
const ll MOD2 = 998244353;
const ll INF = 1e18;

int n, q;

ll L1[N], L2[N];
ll get(ll bit[N], int v) {
    ll res = 0;
    for (; v >= 1; v -= v & -v) res ^= bit[v];
    return res;
}
ll point(ll bit[N], int v) {return get(bit, v) ^ get(bit, v - 1);}
ll range(ll bit[N], int l, int r) {return get(bit, r) ^ get(bit, l - 1);}
void upd(ll bit[N], int v, ll val) {
    ll old = point(bit, v);
    for (; v <= n; v += v & -v) {
        bit[v] ^= old;
        bit[v] ^= val;
    }
}

void query1(int v, ll val) {
    if (v & 1) upd(L1, v, val);
    else upd(L2, v, val);
}

ll query2(int l, int r) {
    int len = r - l + 1;

    if (len & 1) {
        if (l & 1) return range(L1, l, r);
        else return range(L2, l, r);
    } else return 0;
}

int main() {
    #ifdef CHUNGDINH
    freopen("main.inp","r",stdin);
    //freopen("main.out","w",stdout);
    #endif

    memset(L1, 0ll, sizeof L1);
    memset(L2, 0ll, sizeof L2);

    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        ll tt; cin >> tt;
        if (i & 1) upd(L1, i, tt); else upd(L2, i, tt);
    }

    while (q--) {
        int k; cin >> k;

        if (k == 1) {
            int v, val; cin >> v >> val;
            query1(v, val);
        } else {
            int l, r; cin >> l >> r;
            cout << query2(l, r) << endl;
        }
    }
}

/*
Array bounds *
long long vs int
Garbage value
Sometimes, VNOI views "arrays out of bounds" as "wrong answer"
*/

Subtask #1
12.0 / 12.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 5068 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Correct 4 ms 4940 KB Output is correct
7 Correct 4 ms 4940 KB Output is correct
8 Correct 3 ms 4940 KB Output is correct
9 Correct 4 ms 4940 KB Output is correct
10 Correct 3 ms 4940 KB Output is correct
11 Correct 12 ms 4940 KB Output is correct
12 Correct 12 ms 4940 KB Output is correct
13 Correct 16 ms 4928 KB Output is correct
14 Correct 15 ms 5028 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 550 ms 8688 KB Output is correct
2 Correct 542 ms 10960 KB Output is correct
3 Correct 540 ms 11088 KB Output is correct
4 Correct 531 ms 10584 KB Output is correct
5 Correct 535 ms 10952 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 5068 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Correct 4 ms 4940 KB Output is correct
7 Correct 4 ms 4940 KB Output is correct
8 Correct 3 ms 4940 KB Output is correct
9 Correct 4 ms 4940 KB Output is correct
10 Correct 3 ms 4940 KB Output is correct
11 Correct 12 ms 4940 KB Output is correct
12 Correct 12 ms 4940 KB Output is correct
13 Correct 16 ms 4928 KB Output is correct
14 Correct 15 ms 5028 KB Output is correct
15 Correct 550 ms 8688 KB Output is correct
16 Correct 542 ms 10960 KB Output is correct
17 Correct 540 ms 11088 KB Output is correct
18 Correct 531 ms 10584 KB Output is correct
19 Correct 535 ms 10952 KB Output is correct
20 Correct 411 ms 10660 KB Output is correct
21 Correct 504 ms 10824 KB Output is correct
22 Correct 449 ms 10744 KB Output is correct
23 Correct 519 ms 10652 KB Output is correct
24 Correct 505 ms 10724 KB Output is correct