Submission #457976

#	Time	Username	Problem	Language	Result	Execution time	Memory
457976		mansur	XORanges (eJOI19_xoranges)	C++14	0 / 100	215 ms	16300 KiB

xoranges

#include<bits/stdc++.h>

#pragma optimize ("g",on)
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize ("03")
#pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,avx2,mmx,fma,avx,tune=native")
             		
using namespace std;

#define all(a) a.begin(), a.end()
#define ll long long
#define pb push_back
#define nl '\n'
#define popb pop_back()
#define sz size()
#define ld long double
#define ull unsigned long long
#define F first
#define S second
#define fix fixed << setprecision
#define pii pair<int, int>
#define E exit (0)
#define int long long

const int inf = (1ll << 62ll), N = 1e6 + 1, mod = 998244353;                    

vector<pii> dd = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

int t1[N], t2[N], a[N];

void build1(int u, int tl, int tr) {
	if (tl == tr) {
		if (tl % 2 == 0) {
			t1[u] = a[tl];
		}
		return;
	}
	int mid = (tl + tr) / 2;
	build1(u * 2, tl, mid);
	build1(u * 2 + 1, mid + 1, tr);
	t1[u] = (t1[u * 2] ^ t1[u * 2 + 1]);
}

void build2(int u, int tl, int tr) {
	if (tl == tr) {
		if (tl % 2 == 1) {
			t2[u] = a[tl];
		}
		return;
	}
	int mid = (tl + tr) / 2;
	build2(u * 2, tl, mid);
	build2(u * 2 + 1, mid + 1, tr);
	t2[u] = (t2[u * 2] ^ t2[u * 2 + 1]);
}

void update1(int u, int tl, int tr, int pos, int val) {
	if (tl > pos || tr < pos) return;
	if (tl == tr) {
		t1[u] = val;
		return;
	}
	int mid = (tl + tr) / 2;
	update1(u * 2, tl, mid, pos, val);
	update1(u * 2 + 1, mid + 1, tr, pos, val);
	t1[u] = (t1[u * 2] ^ t1[u * 2 + 1]);
}

void update2(int u, int tl, int tr, int pos, int val) {
	if (tl > pos || tr < pos) return;
	if (tl == tr) {
		t2[u] = val;
		return;
	}
	int mid = (tl + tr) / 2;
	update2(u * 2, tl, mid, pos, val);
	update2(u * 2 + 1, mid + 1, tr, pos, val);
	t2[u] = (t2[u * 2] ^ t2[u * 2 + 1]);
}

int get1(int u, int tl, int tr, int l, int r) {
	if (tl > r || tr < l) return 0;
	if (tl >= l && tr <= r) return t1[u];
	int mid = (tl + tr) / 2;
	return (get1(u * 2, tl, mid, l, r) ^ get1(u * 2 + 1, mid + 1, tr, l, r));
}

int get2(int u, int tl, int tr, int l, int r) {
	if (tl > r || tr < l) return 0;
	if (tl >= l && tr <= r) return t2[u];
	int mid = (tl + tr) / 2;
	return (get2(u * 2, tl, mid, l, r) ^ get2(u * 2 + 1, mid + 1, tr, l, r));
}

signed main() {
	//freopen("invtrans.in", "r", stdin);
	//freopen("invtrans.out", "w", stdout);
	ios_base::sync_with_stdio(NULL);
	cin.tie(NULL);
	int n, q;
	cin >> n >> q;
	for (int i = 1; i <= n; i++) {
    	cin >> a[i];
    }
    build1(1, 1, n);
    build2(1, 1, n);
    while (q--) {
    	int tp;
    	cin >> tp;
    	if (tp == 1) {
    		int i, j;
    		cin >> i >> j;
    		if (i % 2 == 0) {
    			update1(1, 1, n, i, j);
    		}else {
    			update2(1, 1, n, i, j);
    		}
    	}else {
    		int l, r;
    		cin >> l >> r;
    		if (l % 2 == 0) {
    			cout << get1(1, 1, n, l, r) << nl;
    		}else {
    			cout << get2(1, 1, n, l, r) << nl;
    		}
    	}
    }
}      

Compilation message (stderr)

xoranges.cpp:3: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    3 | #pragma optimize ("g",on)
      |

• Subtask 1: 0 / 12
• Subtask 2: 0 / 18
• Subtask 3: 0 / 25
• Subtask 4: 0 / 20
• Subtask 5: 0 / 25