oj.uz

Submission #638562

# Submission time Handle Problem Language Result Execution time Memory
638562 2022-09-06T11:41:23 Z ShirleyM XORanges (eJOI19_xoranges) C++14
100 / 100
 359 ms 12064 KB 
#include <bits/stdc++.h>
using namespace std;
#define int int64_t
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef vector<bool> vb;
typedef vector<vb> vvb;
#define x first
#define y second
#define pb push_back
#define loop(i,s,e) for(int i=s;i<e;i++)
#define loopr(i,s,e) for(int i=e-1;i>=s;i--)
#define chkmax(a,b) a=max(a,b)
#define chkmin(a,b) a=min(a,b)
#define all(a) a.begin(),a.end()
#define fast {ios_base::sync_with_stdio(false); cin.tie(0);}
const int inf = 1e18;
const int INF = 1e9;
const int mod = 1e9+7;

struct seg{
    vi a; int sz;
    bool odd;

    seg(int n, bool odd) : odd(odd){
        for(sz=1;sz<n;sz<<=1);
        a.resize(2*sz);
    }

    void update(int ind, int val){
        if((odd && ind%2) || (!odd && ind%2==0)){
            ind+=sz; a[ind] = val;
            for(ind>>=1;ind;ind>>=1)
                a[ind] = a[2*ind]^a[2*ind+1];
        }
    }

    int query(int l, int r){
        int ans=0;
        l+=sz; r+=sz;
        while(l<=r){
            if(l%2) ans^=a[l++];
            if(r%2==0) ans^=a[r--];
            l>>=1; r>>=1;
        }
        return ans;
    }
};

int32_t main() {
    fast;
    int n,q; cin >> n >> q;
    seg odd(n, 1), even(n, 0);
    loop(i,0,n){
        int a; cin >> a;
        odd.update(i,a);
        even.update(i,a);
    }
    loop(i,0,q){
        int op; cin >> op;
        if(op==1){
            int ind, val; cin >> ind >> val;
            ind--;
            odd.update(ind,val);
            even.update(ind,val);
        }
        else{
            int l,r; cin >> l >> r; l--; r--;
            int ans = 0;
            if((r-l+1)%2) {
                if (l % 2) ans = odd.query(l, r);
                else ans = even.query(l, r);
            }
            cout << ans << 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 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 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 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 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 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 5 ms 596 KB Output is correct
12 Correct 5 ms 596 KB Output is correct
13 Correct 9 ms 596 KB Output is correct
14 Correct 8 ms 596 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 326 ms 9660 KB Output is correct
2 Correct 331 ms 12064 KB Output is correct
3 Correct 330 ms 11968 KB Output is correct
4 Correct 359 ms 11924 KB Output is correct
5 Correct 319 ms 12016 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 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 5 ms 596 KB Output is correct
12 Correct 5 ms 596 KB Output is correct
13 Correct 9 ms 596 KB Output is correct
14 Correct 8 ms 596 KB Output is correct
15 Correct 326 ms 9660 KB Output is correct
16 Correct 331 ms 12064 KB Output is correct
17 Correct 330 ms 11968 KB Output is correct
18 Correct 359 ms 11924 KB Output is correct
19 Correct 319 ms 12016 KB Output is correct
20 Correct 225 ms 11452 KB Output is correct
21 Correct 228 ms 11376 KB Output is correct
22 Correct 220 ms 11448 KB Output is correct
23 Correct 305 ms 11944 KB Output is correct
24 Correct 311 ms 11912 KB Output is correct