oj.uz

Submission #430347

# Submission time Handle Problem Language Result Execution time Memory
430347 2021-06-16T13:03:51 Z Urvuk3 XORanges (eJOI19_xoranges) C++17
100 / 100
 203 ms 16068 KB 
#include <bits/stdc++.h>

using namespace std;

#define ll long long
const int MAXN=1e6;
#define fi first
#define se second
#define pll pair<ll,ll>
#define pii pair<int,int>
#define mid (l+r)/2
#define sz(a) int((a).size())
#define all(a) a.begin(),a.end()
#define mod 1000000007LL
#define endl "\n"
#define PRINT(x) cout<<#x<<'-'<<x<<endl

ll n, m, k, q, l, r, x, y, z, res=0, tmp=0;
string s,t;
ll a[MAXN],seg[MAXN*4][2];

void build(int node, int l, int r){
    if(l==r){
        seg[node][l%2]=a[l];
        return;
    }
    build(2*node,l,mid); build(2*node+1,mid+1,r);
    seg[node][0]=seg[2*node][0]^seg[2*node+1][0];
    seg[node][1]=seg[2*node][1]^seg[2*node+1][1];
}

void update(int node, int l, int r, int idx, int val){
    if(l==r){
        seg[node][l%2]=val;
        return;
    }
    if(idx<=mid) update(2*node,l,mid,idx,val);
    else update(2*node+1,mid+1,r,idx,val);
    seg[node][0]=seg[2*node][0]^seg[2*node+1][0];
    seg[node][1]=seg[2*node][1]^seg[2*node+1][1];
}

int query(int node,int l,int r,int L,int R,int parnost){
    if(L<=l && r<=R) return seg[node][parnost];
    int rez=0;
    if(L<=mid) rez^=query(2*node,l,mid,L,R,parnost);
    if(R>mid) rez^=query(2*node+1,mid+1,r,L,R,parnost);
    return rez;
}

void solve(){
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    build(1,1,n);
    while(q--){
        int tip;
        cin>>tip;
        if(tip==1){
            int pos;
            cin>>pos>>x;
            update(1,1,n,pos,x);
        }
        else{
            int l,r;
            cin>>l>>r;
            if(l%2!=r%2){
                cout<<0<<endl;
            }
            else cout<<query(1,1,n,l,r,l%2)<<endl;
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    int t;
    //cin>>t;
    t=1;
    while(t--){
        solve();
    }
    return 0;
}

Subtask #1
12.0 / 12.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 4 ms 716 KB Output is correct
12 Correct 4 ms 716 KB Output is correct
13 Correct 5 ms 716 KB Output is correct
14 Correct 4 ms 716 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 11204 KB Output is correct
2 Correct 203 ms 16024 KB Output is correct
3 Correct 184 ms 16068 KB Output is correct
4 Correct 155 ms 15700 KB Output is correct
5 Correct 156 ms 15692 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 4 ms 716 KB Output is correct
12 Correct 4 ms 716 KB Output is correct
13 Correct 5 ms 716 KB Output is correct
14 Correct 4 ms 716 KB Output is correct
15 Correct 181 ms 11204 KB Output is correct
16 Correct 203 ms 16024 KB Output is correct
17 Correct 184 ms 16068 KB Output is correct
18 Correct 155 ms 15700 KB Output is correct
19 Correct 156 ms 15692 KB Output is correct
20 Correct 196 ms 15980 KB Output is correct
21 Correct 192 ms 15800 KB Output is correct
22 Correct 178 ms 15900 KB Output is correct
23 Correct 178 ms 15776 KB Output is correct
24 Correct 173 ms 15736 KB Output is correct