oj.uz

Submission #785825

# Submission time Handle Problem Language Result Execution time Memory
785825 2023-07-17T15:53:42 Z Bula XORanges (eJOI19_xoranges) C++17
100 / 100
 555 ms 51716 KB 
#include <bits/stdc++.h>
using namespace std;
 	
#define ll long long
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define f first
#define s second
#define pi pair<int,int>
#define pii pair< pair<int,int> , pair<int,int> >  
#define int ll
const ll mod=1e9+7,N=2e5+1;
vector<int> a(N);
vector< vector<int> > t(4 * N, vector<int> (2));
 
 
int combine(int a,int b){
	return a^b;
}
 
//
//void build(int v, int tl, int tr) {
//    if (tl == tr) {
//        t[v] = a[tl];
//    } else {
//        int tm = (tl + tr) / 2;
//        build(v*2, tl, tm);
//        build(v*2+1, tm+1, tr);
//        t[v]=combine(t[v*2],t[v*2+1]);
//    }
//}
 
int get(int v, int tl, int tr, int l, int r, int p) {
    if (l > r) 
        return 0;
    if (l == tl && r == tr) {
        return t[v][p];
    }
    int tm = (tl + tr) / 2;
    return combine(get(v*2, tl, tm, l, min(r, tm), p),get(v*2+1, tm+1, tr, max(l, tm+1), r, p));
}
 
void up(int v, int tl, int tr, int pos, int new_val, int p) {
    if (tl == tr) {
        t[v][p] = new_val;
    } else {
        int tm = (tl + tr) / 2;
        if (pos <= tm)
            up(v*2, tl, tm, pos, new_val, p);
        else
            up(v*2+1, tm+1, tr, pos, new_val, p);
		t[v][p] = combine(t[v*2][p],t[v*2+1][p]);
    }
}

 
main(){
 
    int tt=1;//cin>>tt;
    while(tt--){
    	int n,m;
    	cin>>n>>m;
    	for(int i=1;i<=n;i++){
    		int x;
    		cin>>x;
    		up(1, 1, n, i, x, i % 2);
		}
		
		for(int i=1;i<=m;i++){
			int x;
			cin>>x;
			if(x == 1){
				int pos,k;
				cin >> pos >> k;
				up(1, 1, n, pos, k, pos % 2);
			}else{
				int l,r;
				cin >> l >> r;
				if((r-l+1)%2==0) cout << 0 << endl;
				else{
					cout << get(1, 1, n, l, r, l % 2) << endl;
				}
			}
		}
    }
}

Compilation message

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

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 45652 KB Output is correct
2 Correct 44 ms 45628 KB Output is correct
3 Correct 36 ms 45668 KB Output is correct
4 Correct 37 ms 45636 KB Output is correct
5 Correct 42 ms 45772 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 45652 KB Output is correct
2 Correct 39 ms 45692 KB Output is correct
3 Correct 50 ms 45616 KB Output is correct
4 Correct 39 ms 45660 KB Output is correct
5 Correct 37 ms 45708 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 45652 KB Output is correct
2 Correct 44 ms 45628 KB Output is correct
3 Correct 36 ms 45668 KB Output is correct
4 Correct 37 ms 45636 KB Output is correct
5 Correct 42 ms 45772 KB Output is correct
6 Correct 36 ms 45652 KB Output is correct
7 Correct 39 ms 45692 KB Output is correct
8 Correct 50 ms 45616 KB Output is correct
9 Correct 39 ms 45660 KB Output is correct
10 Correct 37 ms 45708 KB Output is correct
11 Correct 43 ms 45780 KB Output is correct
12 Correct 45 ms 45844 KB Output is correct
13 Correct 48 ms 45796 KB Output is correct
14 Correct 47 ms 45744 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 555 ms 51680 KB Output is correct
2 Correct 515 ms 51700 KB Output is correct
3 Correct 545 ms 51716 KB Output is correct
4 Correct 461 ms 51532 KB Output is correct
5 Correct 448 ms 51404 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 45652 KB Output is correct
2 Correct 44 ms 45628 KB Output is correct
3 Correct 36 ms 45668 KB Output is correct
4 Correct 37 ms 45636 KB Output is correct
5 Correct 42 ms 45772 KB Output is correct
6 Correct 36 ms 45652 KB Output is correct
7 Correct 39 ms 45692 KB Output is correct
8 Correct 50 ms 45616 KB Output is correct
9 Correct 39 ms 45660 KB Output is correct
10 Correct 37 ms 45708 KB Output is correct
11 Correct 43 ms 45780 KB Output is correct
12 Correct 45 ms 45844 KB Output is correct
13 Correct 48 ms 45796 KB Output is correct
14 Correct 47 ms 45744 KB Output is correct
15 Correct 555 ms 51680 KB Output is correct
16 Correct 515 ms 51700 KB Output is correct
17 Correct 545 ms 51716 KB Output is correct
18 Correct 461 ms 51532 KB Output is correct
19 Correct 448 ms 51404 KB Output is correct
20 Correct 416 ms 51548 KB Output is correct
21 Correct 407 ms 51480 KB Output is correct
22 Correct 411 ms 51388 KB Output is correct
23 Correct 496 ms 51532 KB Output is correct
24 Correct 442 ms 51376 KB Output is correct