oj.uz

답안 #464054

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
464054 2021-08-12T10:17:26 Z Alen777 XORanges (eJOI19_xoranges) C++17
55 / 100
 14 ms 1200 KB 
#include <iostream>
#include <string>
#include <iomanip>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;

#define ll long long
#define ull unsigned ll
#define pb push_back
#define mpr make_pair
#define lb lower_bound
#define ld long double
#define ub upper_bound

const int N = 100002;

int a[N];
ll t1[4 * N], t2[4 * N];
vector<int> vec;

void build(int tl, int tr, int v) {
	if (tl == tr) {
		t1[v] = a[tl];
	}
	else {
		int m = (tl + tr) / 2;
		build(tl, m, v * 2);
		build(m + 1, tr, v * 2 + 1);
		t1[v] = t1[v * 2] ^ t1[v * 2 + 1];
	}
}

void build1(int tl, int tr, int v) {
	if (tl == tr) {
		t2[v] = vec[tl];
	}
	else {
		int m = (tl + tr) / 2;
		build1(tl, m, v * 2);
		build1(m + 1, tr, v * 2 + 1);
		t2[v] = t2[v * 2] ^ t2[v * 2 + 1];
	}
}

ll sum(int tl, int tr, int l, int r, int v) {
	if (l > r)
		return 0;
	if (l == tl && r == tr)
		return t1[v];
	int m = (tl + tr) / 2;
	return sum(tl, m, l, min(r, m), v * 2)
		^ sum(m + 1, tr, max(l, m + 1), r, v * 2 + 1);
}

ll sum1(int tl, int tr, int l, int r, int v) {
	if (l > r)
		return 0;
	if (l == tl && r == tr)
		return t2[v];
	int m = (tl + tr) / 2;
	return sum1(tl, m, l, min(r, m), v * 2)
		^ sum1(m + 1, tr, max(l, m + 1), r, v * 2 + 1);
}

void update(int tl, int tr, int v, int pos, int new_val) {
	if (tl == tr) {
		t1[v] = new_val;
	}
	else {
		int m = (tl + tr) / 2;
		if (pos <= m) {
			update(tl, m, v * 2, pos, new_val);
		}
		else {
			update(m + 1, tr, v * 2 + 1, pos, new_val);
		}
		t1[v] = t1[v * 2] ^ t1[v * 2 + 1];
	}
}

void update1(int tl, int tr, int v, int pos, int new_val) {
	if (tl == tr) {
		t2[v] = new_val;
	}
	else {
		int m = (tl + tr) / 2;
		if (pos <= m) {
			update1(tl, m, v * 2, pos, new_val);
		}
		else {
			update1(m + 1, tr, v * 2 + 1, pos, new_val);
		}
		t2[v] = t2[v * 2] ^ t2[v * 2 + 1];
	}
}

void solve() {
	int n, q;
	cin >> n >> q;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	vec.push_back(0);
	for (int i = 1; i <= n; i++) {
		if (i % 2 == 1) {
			vec.push_back(a[i]);
		}
		else {
			vec.push_back(0);
		}
	}
	build(1, n, 1);
	build1(1, n, 1);
	for (int i = 1; i <= q; i++) {
		int c, l, r;
		cin >> c >> l >> r;
		if (c == 1) {
			update(1, n, 1, l, r);
			if (l % 2 == 1) {
				update1(1, n, 1, l, r);
			}
		}
		else {
			if (r - l + 1 == 2) {
				cout << 0 << endl;
			}
			else if (r - l + 1 == 1) {
				cout << sum(1, n, l, r, 1) << endl;
			}
			else {
				ll ans = 0;
				if ((r - l + 1) % 2 == 0) {
					cout << 0 << endl;
				}
				else {
					ll num1 = sum1(1, n, l, r, 1);
					if (l % 2 == 1) {
						cout << num1 << endl;
					}
					else {
						ll num2 = sum(1, n, l, r, 1);
						cout <<(num2 ^ num1);
						cout << endl;
					}
				}
			}
		}
	}
}

int main() {
    /*cout.setf(ios::fixed | ios::showpoint);
    cout.precision(6);*/
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    solve();
    return 0;
}

Compilation message

xoranges.cpp: In function 'void solve()':
xoranges.cpp:138:8: warning: unused variable 'ans' [-Wunused-variable]
  138 |     ll ans = 0;
      |        ^~~

Subtask #1
12.0 / 12.0

# 결과 실행 시간 메모리 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 #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 2 ms 332 KB Output is correct

Subtask #3
25.0 / 25.0

# 결과 실행 시간 메모리 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
6 Correct 1 ms 332 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 2 ms 332 KB Output is correct
11 Correct 8 ms 852 KB Output is correct
12 Correct 9 ms 844 KB Output is correct
13 Correct 11 ms 796 KB Output is correct
14 Correct 11 ms 792 KB Output is correct

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 14 ms 1200 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# 결과 실행 시간 메모리 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
6 Correct 1 ms 332 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 2 ms 332 KB Output is correct
11 Correct 8 ms 852 KB Output is correct
12 Correct 9 ms 844 KB Output is correct
13 Correct 11 ms 796 KB Output is correct
14 Correct 11 ms 792 KB Output is correct
15 Runtime error 14 ms 1200 KB Execution killed with signal 11
16 Halted 0 ms 0 KB -