oj.uz

Submission #947550

# Submission time Handle Problem Language Result Execution time Memory
947550 2024-03-16T11:35:46 Z asdfghjk XORanges (eJOI19_xoranges) C++17
100 / 100
 94 ms 11360 KB 
/// tree bends in youth
/// 24.01.2024
/// success is doing same thing in every single day!!!
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define all(x) x.begin(), x.end()
#define F first
#define S second
using namespace std;
const ll N = 2e5 + 5;
const ll maxn =1e6 + 5;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;
const ll LG = 18;
int a[N];
pair<int,int> t[4 * N];
void build(int v,int l,int r){
    if(l == r){
        t[v].F=  a[((l - 1) * 2) + 1];
        t[v].S = a[(l * 2)];
        return;
    }
    int mid = (l + r) / 2;
    build(v+v,l,mid);
    build(v+v+1,mid+1,r);
    t[v].F =(t[v+v].F ^ t[v+v+1].F);
    t[v].S =(t[v+v].S ^ t[v+v+1].S);
}
void upd(int v,int l,int r,int pos,int val,bool s){
    if(l == r){
        if(s)t[v].F = val;
        else t[v].S = val;
        return;
    }
    int mid = (l + r ) / 2;
    if(pos <= mid)upd(v+v,l,mid,pos,val,s);
    else upd(v+v+1,mid+1,r,pos,val,s);
    t[v].F =(t[v+v].F ^ t[v+v+1].F);
    t[v].S =(t[v+v].S ^ t[v+v+1].S);
}
int get(int v,int l,int r,int ql,int qr,bool s){
    if(ql <= l && r <= qr){
        if(s)return t[v].F;
        else return t[v].S;
    }
    if(qr < l || r < ql)return 0;
    int mid = (l + r) / 2;
    return ((get(v+v,l,mid,ql,qr,s)) ^ (get(v+v+1,mid+1,r,ql,qr,s)));
}
void solve(){
    int n,q;cin >> n >> q;
    for(int i = 1;i <= n;i++){
        cin >> a[i];
    }
    build(1,1,((n + 1) / 2));
    while(q--){
        int tp;cin >> tp;
        if(tp == 1){
            int i,j;cin >> i >> j;
            upd(1,1,((n + 1) / 2),((i + 1) / 2),j,(i % 2));
        }
        else{
            int l,r;cin >> l >> r;
            if((r - l + 1) % 2 == 0){
                cout << "0\n";
            }
            else{
                bool ok = (l % 2);
                l = (l + 1) / 2;
                r=  (r + 1) / 2;
                int x =  get(1,1,((n + 1) / 2),l,r,ok);
                cout <<x << '\n';
            }
        }
    }
}
main (){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

//    freopen("haybales.in","r",stdin);
//    freopen("haybales.out","w",stdout);
    ll abd= 1;
//    cin >> abd;
    for(ll i = 1;i <= abd;i++){
//        cout << "Case " << i << ":\n";
        solve();
    }
}

Compilation message

xoranges.cpp:78:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   78 | main (){
      | ^~~~

Subtask #1
12.0 / 12.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
25.0 / 25.0

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

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 11068 KB Output is correct
2 Correct 90 ms 11348 KB Output is correct
3 Correct 90 ms 11360 KB Output is correct
4 Correct 83 ms 10960 KB Output is correct
5 Correct 82 ms 10996 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2392 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 3 ms 2392 KB Output is correct
12 Correct 2 ms 2396 KB Output is correct
13 Correct 2 ms 2396 KB Output is correct
14 Correct 2 ms 2396 KB Output is correct
15 Correct 94 ms 11068 KB Output is correct
16 Correct 90 ms 11348 KB Output is correct
17 Correct 90 ms 11360 KB Output is correct
18 Correct 83 ms 10960 KB Output is correct
19 Correct 82 ms 10996 KB Output is correct
20 Correct 91 ms 11264 KB Output is correct
21 Correct 90 ms 11276 KB Output is correct
22 Correct 92 ms 11064 KB Output is correct
23 Correct 83 ms 11092 KB Output is correct
24 Correct 89 ms 11144 KB Output is correct