oj.uz

Submission #625200

# Submission time Handle Problem Language Result Execution time Memory
625200 2022-08-09T15:12:27 Z lovrot XORanges (eJOI19_xoranges) C++11
55 / 100
 236 ms 65536 KB 
#include <bits/stdc++.h> 
#include <unistd.h>

#define X first
#define Y second
#define ll long long
#define pii pair<int, int>
#define pb push_back
#define vec vector
#define pri(i, poc, n, pov) for(int i = (int) poc; i < (int) n; i += (int) pov)
#define od(i, poc, n, pov) for(int i = (int) poc; i > (int) n; i -= (int) pov)

using namespace std;

const int LOG = 19;
const int OFF = (1 << LOG);
const int N = 1e6;

struct node{ 
	int sum[2] = {0, 0};
} tour[32][N];

int n, q; 

void update(int t, int x, int val){
	x += OFF; 
	tour[t][x].sum[x % 2] = val;
	x >>= 1;
	while(x){ 
		pri(i, 0, 2, 1)
			tour[t][x].sum[i] = tour[t][x * 2].sum[i] + tour[t][x * 2 + 1].sum[i];
		x >>= 1;
	}
}

int query(int t, int b, int l, int r, int lo = 0, int hi = OFF, int x = 1){ 
	if(r <= lo || hi <= l) return 0;
	if(l <= lo && hi <= r) return tour[t][x].sum[b];
	int mi = (lo + hi) / 2;
	return query(t, b, l, r, lo, mi, x * 2) + query(t, b, l, r, mi, hi, x * 2 + 1);
}

int main(){ 
	ios_base::sync_with_stdio(false); 
	cin.tie(0);
	cout.tie(0);

	cin >> n >> q;

	pri(i, 0, n, 1){
		int x;
		cin >> x;
		pri(j, 0, 32, 1){
			bool b = (x  & (1 << j)) > 0; 
			update(j, i, b);
		}
	}

	pri(i, 0, q, 1){ 
		int t, x, y;
		cin >> t >> x >> y;
		if(t == 1){ 
			pri(j, 0, 32, 1){
				bool b = (y  & (1 << j)) > 0; 
				update(j, x - 1, b);
			}		
		} else { 
			int ans = 0; 
			x--;
			y--;
			int p = (y - x + 1) % 2;
			if(!p){ 
				cout << 0 << "\n";
				continue;
			}
			pri(j, 0, 32, 1){ 
				int res = query(j, x % 2, x, y + 1);
				ans += (1 << j) * (res % 2);
			}
			cout << ans << "\n";
		}
	}
	return 0;
}

Subtask #1
12.0 / 12.0

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

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2516 KB Output is correct
2 Correct 3 ms 2428 KB Output is correct
3 Correct 4 ms 2516 KB Output is correct
4 Correct 3 ms 2460 KB Output is correct
5 Correct 4 ms 2516 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2260 KB Output is correct
2 Correct 2 ms 2260 KB Output is correct
3 Correct 1 ms 2260 KB Output is correct
4 Correct 1 ms 2260 KB Output is correct
5 Correct 2 ms 2260 KB Output is correct
6 Correct 3 ms 2516 KB Output is correct
7 Correct 3 ms 2428 KB Output is correct
8 Correct 4 ms 2516 KB Output is correct
9 Correct 3 ms 2460 KB Output is correct
10 Correct 4 ms 2516 KB Output is correct
11 Correct 23 ms 4820 KB Output is correct
12 Correct 22 ms 4820 KB Output is correct
13 Correct 25 ms 4820 KB Output is correct
14 Correct 28 ms 4820 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 236 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2260 KB Output is correct
2 Correct 2 ms 2260 KB Output is correct
3 Correct 1 ms 2260 KB Output is correct
4 Correct 1 ms 2260 KB Output is correct
5 Correct 2 ms 2260 KB Output is correct
6 Correct 3 ms 2516 KB Output is correct
7 Correct 3 ms 2428 KB Output is correct
8 Correct 4 ms 2516 KB Output is correct
9 Correct 3 ms 2460 KB Output is correct
10 Correct 4 ms 2516 KB Output is correct
11 Correct 23 ms 4820 KB Output is correct
12 Correct 22 ms 4820 KB Output is correct
13 Correct 25 ms 4820 KB Output is correct
14 Correct 28 ms 4820 KB Output is correct
15 Runtime error 236 ms 65536 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -