oj.uz

Submission #457977

# Submission time Handle Problem Language Result Execution time Memory
457977 2021-08-07T16:37:20 Z mansur XORanges (eJOI19_xoranges) C++14
100 / 100
 185 ms 16148 KB 
#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 ((r - l + 1) % 2 == 0) {
    			cout << 0 << nl;
    			continue;
    		}
    		if (l % 2 == 0) {
    			cout << get1(1, 1, n, l, r) << nl;
    		}else {
    			cout << get2(1, 1, n, l, r) << nl;
    		}
    	}
    }
}

Compilation message

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

Subtask #1
12.0 / 12.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 #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 336 KB Output is correct

Subtask #3
25.0 / 25.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
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 336 KB Output is correct
11 Correct 4 ms 716 KB Output is correct
12 Correct 5 ms 716 KB Output is correct
13 Correct 4 ms 716 KB Output is correct
14 Correct 5 ms 720 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 11180 KB Output is correct
2 Correct 169 ms 16076 KB Output is correct
3 Correct 170 ms 16148 KB Output is correct
4 Correct 149 ms 15696 KB Output is correct
5 Correct 137 ms 15776 KB Output is correct

Subtask #5
25.0 / 25.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
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 336 KB Output is correct
11 Correct 4 ms 716 KB Output is correct
12 Correct 5 ms 716 KB Output is correct
13 Correct 4 ms 716 KB Output is correct
14 Correct 5 ms 720 KB Output is correct
15 Correct 159 ms 11180 KB Output is correct
16 Correct 169 ms 16076 KB Output is correct
17 Correct 170 ms 16148 KB Output is correct
18 Correct 149 ms 15696 KB Output is correct
19 Correct 137 ms 15776 KB Output is correct
20 Correct 171 ms 15760 KB Output is correct
21 Correct 185 ms 15824 KB Output is correct
22 Correct 158 ms 15816 KB Output is correct
23 Correct 138 ms 15664 KB Output is correct
24 Correct 139 ms 15676 KB Output is correct