oj.uz

Submission #625198

# Submission time Handle Problem Language Result Execution time Memory
625198 2022-08-09T15:08:23 Z lovrot XORanges (eJOI19_xoranges) C++11
55 / 100
 476 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);

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

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 2 ms 2132 KB Output is correct
2 Correct 2 ms 2132 KB Output is correct
3 Correct 2 ms 2132 KB Output is correct
4 Correct 2 ms 2132 KB Output is correct
5 Correct 2 ms 2132 KB Output is correct

Subtask #2
18.0 / 18.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2132 KB Output is correct
2 Correct 2 ms 2132 KB Output is correct
3 Correct 2 ms 2132 KB Output is correct
4 Correct 2 ms 2132 KB Output is correct
5 Correct 2 ms 2132 KB Output is correct
6 Correct 5 ms 2260 KB Output is correct
7 Correct 5 ms 2260 KB Output is correct
8 Correct 5 ms 2384 KB Output is correct
9 Correct 5 ms 2260 KB Output is correct
10 Correct 5 ms 2260 KB Output is correct
11 Correct 45 ms 4648 KB Output is correct
12 Correct 43 ms 4564 KB Output is correct
13 Correct 45 ms 4636 KB Output is correct
14 Correct 47 ms 4640 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 476 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 2 ms 2132 KB Output is correct
2 Correct 2 ms 2132 KB Output is correct
3 Correct 2 ms 2132 KB Output is correct
4 Correct 2 ms 2132 KB Output is correct
5 Correct 2 ms 2132 KB Output is correct
6 Correct 5 ms 2260 KB Output is correct
7 Correct 5 ms 2260 KB Output is correct
8 Correct 5 ms 2384 KB Output is correct
9 Correct 5 ms 2260 KB Output is correct
10 Correct 5 ms 2260 KB Output is correct
11 Correct 45 ms 4648 KB Output is correct
12 Correct 43 ms 4564 KB Output is correct
13 Correct 45 ms 4636 KB Output is correct
14 Correct 47 ms 4640 KB Output is correct
15 Runtime error 476 ms 65536 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -