oj.uz

Submission #467172

# Submission time Handle Problem Language Result Execution time Memory
467172 2021-08-21T20:35:28 Z nemethm XORanges (eJOI19_xoranges) C++17
38 / 100
 165 ms 5620 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;
			a /= 2;
			upd((a * 2) % 2 == 0 ? eventree : oddtree, a, 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
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

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 332 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 5588 KB Output is correct
2 Correct 165 ms 5576 KB Output is correct
3 Correct 154 ms 5604 KB Output is correct
4 Correct 139 ms 5620 KB Output is correct
5 Correct 140 ms 5580 KB Output is correct

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -