oj.uz

Submission #467173

# Submission time Handle Problem Language Result Execution time Memory
467173 2021-08-21T20:36:46 Z nemethm XORanges (eJOI19_xoranges) C++17
100 / 100
 172 ms 6736 KB 
#include <iostream>
#include <list>
#include <algorithm>
#include <queue>
#include <vector>
#include <limits>
#include <set>
#include <numeric>
#include <string>
#include <assert.h>
#include <map>
#include <cmath>
#include <stack>
#include <cstring>
#include <stack>
#pragma warning(disable : 4996)
using namespace std;
using ll = long long int;
const ll inf = numeric_limits<ll>::max();
const ll mod = 1e9+7;
void setIO(string s) {
	freopen((s + ".in").c_str(), "r", stdin);
	freopen((s + ".out").c_str(), "w", stdout);
}
vector<int> evenv, oddv, eventree, oddtree;
void upd(vector<int>& tree, int index, int val, int tl = 0, int tr = -1, int poz = 1) {
	if (tr == -1) tr = tree.size() / 4 - 1;
	if (tl == tr) {
		tree[poz] = val;
		return;
	}
	int m = (tl + tr) / 2;
	if (index <= m) {
		upd(tree, index, val, tl, m, poz * 2);
	}
	else {
		upd(tree, index, val, m + 1, tr, poz * 2 + 1);
	}
	tree[poz] = tree[poz * 2] ^ tree[poz * 2 + 1];
}
int query(vector<int>& tree, int l, int r, int tl = 0, int tr = -1, int poz = 1) {
	if (l > r) return 0;
	if (tr == -1) tr = tree.size() / 4 - 1;
	if (tl == l && tr == r) {
		return tree[poz];
	}
	int tm = (tl + tr) / 2;
	return query(tree, l, min(r, tm), tl, tm, poz * 2) ^ query(tree, max(l,tm + 1), r, tm + 1, tr, poz * 2 + 1);
}
void build(vector<int>& v, vector<int>& tree, int l, int r, int poz = 1) {
	if (l == r) {
		tree[poz] = v[l];
		return;
	}
	int m = (l + r) / 2;
	build(v, tree, l, m, poz * 2);
	build(v, tree, m + 1, r, poz * 2 + 1);
	tree[poz] = tree[poz * 2] ^ tree[poz * 2 + 1];
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.precision(9);
	int n, q;
	cin >> n >> q;
	/*csak a páratlan hosszó queryknél kell nézni a páratlan indexeken lévőt(1 based) (seg tree)*/
	//v.resize(n); eventree.resize(n * 4); oddtree.resize(n * 4);
	for (int i = 0; i < n; ++i) {
		int var;
		cin >> var;
		if (i % 2 == 0) evenv.push_back(var);
		else oddv.push_back(var);
	}
	eventree.resize(evenv.size() * 4);
	oddtree.resize(oddv.size() * 4);
	build(evenv, eventree, 0, evenv.size() - 1);
	build(oddv, oddtree, 0,oddv.size() - 1);
	while (q--) {
		int t, a, b;
		cin >> t >> a >> b;
		if (t == 1) {
			--a;
			upd(a % 2 == 0 ? eventree : oddtree, a / 2, b);
		}
		else if (t == 2) {
			--a; --b;
			if ((b - a + 1) % 2 == 1)
				cout << query(a % 2 == 0 ? eventree : oddtree, a / 2, b / 2) << "\n";
			else
				cout << "0\n";
		}
	}
	return 0;
}

Compilation message

xoranges.cpp:16: warning: ignoring '#pragma warning ' [-Wunknown-pragmas]
   16 | #pragma warning(disable : 4996)
      | 
xoranges.cpp: In function 'void setIO(std::string)':
xoranges.cpp:22:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |  freopen((s + ".in").c_str(), "r", stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
xoranges.cpp:23:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |  freopen((s + ".out").c_str(), "w", stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
25.0 / 25.0

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

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 5708 KB Output is correct
2 Correct 167 ms 5632 KB Output is correct
3 Correct 151 ms 5628 KB Output is correct
4 Correct 144 ms 5580 KB Output is correct
5 Correct 146 ms 5632 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 5 ms 576 KB Output is correct
12 Correct 4 ms 460 KB Output is correct
13 Correct 5 ms 460 KB Output is correct
14 Correct 4 ms 588 KB Output is correct
15 Correct 168 ms 5708 KB Output is correct
16 Correct 167 ms 5632 KB Output is correct
17 Correct 151 ms 5628 KB Output is correct
18 Correct 144 ms 5580 KB Output is correct
19 Correct 146 ms 5632 KB Output is correct
20 Correct 149 ms 6148 KB Output is correct
21 Correct 172 ms 6200 KB Output is correct
22 Correct 157 ms 6192 KB Output is correct
23 Correct 149 ms 6736 KB Output is correct
24 Correct 147 ms 6700 KB Output is correct