oj.uz

Submission #1100114

# Submission time Handle Problem Language Result Execution time Memory
1100114 2024-10-12T18:14:41 Z cot XORanges (eJOI19_xoranges) C++14
100 / 100
 354 ms 16228 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <map>
#define int long long
#define ff first
#define ss second
#define pb push_back
#define pp pop_back
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define r0 return 0
using namespace std;
const int N = 5 * 1e5 + 5, M = 501, MOD = 998244353;
string s;
int tr[4 * N],a[N],n,m,k,l,q,x,r,tr2[4 * N];
void update(int node, int l ,int r ,int ind , int val) {
    if (ind > r or ind < l) return;
    if (l == r) {
        tr[node] = val;
        return;
    }
    int mid = ( l + r )/ 2;
    update (node * 2, l, mid ,ind , val);
    update (node * 2 + 1 , mid + 1 , r ,ind , val);
    tr[node] = tr[node * 2] xor tr[node * 2 + 1];
}
int getans (int node, int l ,int r ,int st ,int end) {
    if (end < l or st > r) return 0;
    if (st <= l and r <= end) return tr[node];
    int mid = (l + r) / 2;
    return getans(node * 2, l , mid , st, end) xor getans (node * 2 + 1 , mid + 1 , r ,st , end);
}
void update2(int node, int l ,int r ,int ind , int val) {
    if (ind > r or ind < l) return;
    if (l == r) {
        tr2[node] = val;
        return;
    }
    int mid = ( l + r )/ 2;
    update2 (node * 2, l, mid ,ind , val);
    update2 (node * 2 + 1 , mid + 1 , r ,ind , val);
    tr2[node] = tr2[node * 2] xor tr2[node * 2 + 1];
}
int getans2 (int node, int l ,int r ,int st ,int end) {
    if (end < l or st > r) return 0;
    if (st <= l and r <= end) return tr2[node];
    int mid = (l + r) / 2;
    return getans2(node * 2, l , mid , st, end) xor getans2(node * 2 + 1 , mid + 1 , r ,st , end);
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        if (i % 2 == 1) update(1,1,n,i,a[i]);
        if (i % 2 == 0) update2(1,1,n,i,a[i]);
    }
    for (int i = 1; i <= q; i++) {
        cin >> x >> l >> r;
        if (x == 1){
            if (l % 2 == 1) update(1,1,n,l,r);
            if (l % 2 == 0) update2(1,1,n,l,r);
        } else {
            int check1 = r - l + 1;
            if (check1 % 2 == 0) {
                cout << 0 << endl;
//                cout << "CHECK" << endl;
            } else if (l % 2 == 0){
                int ans = getans2(1,1,n,l,r);
                cout << ans << endl;
            } else if (l % 2 == 1) {
                int ans = getans (1,1,n,l,r);
                cout << ans << endl;
            }
        }
    }
    
    return 0;
}

Subtask #1
12.0 / 12.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 5 ms 604 KB Output is correct
12 Correct 5 ms 604 KB Output is correct
13 Correct 7 ms 604 KB Output is correct
14 Correct 7 ms 784 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 354 ms 14164 KB Output is correct
2 Correct 339 ms 16228 KB Output is correct
3 Correct 338 ms 16208 KB Output is correct
4 Correct 300 ms 15700 KB Output is correct
5 Correct 300 ms 15868 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 5 ms 604 KB Output is correct
12 Correct 5 ms 604 KB Output is correct
13 Correct 7 ms 604 KB Output is correct
14 Correct 7 ms 784 KB Output is correct
15 Correct 354 ms 14164 KB Output is correct
16 Correct 339 ms 16228 KB Output is correct
17 Correct 338 ms 16208 KB Output is correct
18 Correct 300 ms 15700 KB Output is correct
19 Correct 300 ms 15868 KB Output is correct
20 Correct 216 ms 15952 KB Output is correct
21 Correct 238 ms 15956 KB Output is correct
22 Correct 245 ms 15764 KB Output is correct
23 Correct 316 ms 15920 KB Output is correct
24 Correct 310 ms 15864 KB Output is correct