oj.uz

Submission #441415

# Submission time Handle Problem Language Result Execution time Memory
441415 2021-07-05T07:11:15 Z RaresFelix XORanges (eJOI19_xoranges) C++17
100 / 100
 178 ms 11204 KB 
#include <bits/stdc++.h>
#define MAXN 817171
#ifdef AICI
#define cin fi
#endif // AICI
using namespace std;
#ifdef AICI
ifstream fi("a.in");
#endif // AICI
int A[MAXN], n, q;

struct AINT
{
	int V[MAXN];
	void _u(int u, int s, int d, int p, int v)
	{
		if(d < p || p < s)return;
		if(s==d){
			V[u] = v;
			return;
		}
		_u(u*2, s, (s+d)/2, p, v);
		_u(u*2+1, (s+d)/2+1, d, p, v);
		V[u] = V[u*2] ^ V[u*2+1];
	}
	int _q(int u, int s, int d, int l, int r)
	{
		if(d < l || r < s)return 0;
		if(l <= s && d <= r)return V[u];
		return _q(u*2, s, (s+d)/2, l, r) ^ _q(u*2+1, (s+d)/2+1, d, l, r);
	}
	void setup(int delta)
	{
		for(int i = 1; i + delta <= n; i += 2)
			_u(1, 1, n, i+delta, A[i+delta]);
	}
} Pare, Impare;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.precision(10);
    cout << fixed;
	cin >> n >> q;
	for(int i = 1; i <= n; ++i)
		cin >> A[i];
	Pare.setup(1);
	Impare.setup(0);
	int tip, a, b;
	for(int i = 1; i <= q; ++i){
		cin >> tip >> a >> b;
		if(tip == 1) {
			A[a] = b;
			if(a%2)Impare._u(1, 1, n, a, b);
			else Pare._u(1, 1, n, a, b);
		} else {
			if((a^b)&1){
				cout << "0\n";
			} else {
				if(a&1) cout << Impare._q(1, 1, n, a, b);
				else cout << Pare._q(1, 1, n, a, b);
				cout << "\n";
			}
		}
	}
    return 0;
}

Subtask #1
12.0 / 12.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
25.0 / 25.0

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

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 9140 KB Output is correct
2 Correct 175 ms 11136 KB Output is correct
3 Correct 171 ms 11204 KB Output is correct
4 Correct 152 ms 10884 KB Output is correct
5 Correct 152 ms 10864 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 4 ms 460 KB Output is correct
12 Correct 4 ms 460 KB Output is correct
13 Correct 4 ms 460 KB Output is correct
14 Correct 4 ms 460 KB Output is correct
15 Correct 178 ms 9140 KB Output is correct
16 Correct 175 ms 11136 KB Output is correct
17 Correct 171 ms 11204 KB Output is correct
18 Correct 152 ms 10884 KB Output is correct
19 Correct 152 ms 10864 KB Output is correct
20 Correct 174 ms 10868 KB Output is correct
21 Correct 178 ms 10880 KB Output is correct
22 Correct 169 ms 10940 KB Output is correct
23 Correct 156 ms 10976 KB Output is correct
24 Correct 154 ms 10820 KB Output is correct