oj.uz

Submission #1089372

# Submission time Handle Problem Language Result Execution time Memory
1089372 2024-09-16T10:56:31 Z KluydQ XORanges (eJOI19_xoranges) C++17
100 / 100
 112 ms 16208 KB 
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

#define ll long long
#define ld long double
#define ull unsigned long long
#define pb push_back	
#define pob pop_back
#define int long long
#define int2 __int128_t
#define Shrek_Crush228 ios_base::sync_with_stdio(0), cin.tie(0);
#define F first
#define S second
#define FOR( i, x, n, d ) for( int i = x; i <= n; i += d )
#define FORR( i, x, n, d ) for( int i = x; i >= n; i -= d )
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define no cout << "NO\n"
#define yes cout << "YES\n"
#define nep next_permutation
#define sigma signed
#define pii pair <int, int> 

using namespace std;

string alp = "abcdefghijklmnopqrstuvwxyz";
string ae = "aoeiuy";
string nums = "123456789";

const int N = 1e6 + 123;
const int inf = 1e18;
const int MOD = 1e9 + 7;
const int MOD1 = 998244353;
const long long maxsum = 1e14;

int a[N], b[N], c[N], l, r, n, k, m, w, sum, sum1, y, ans1, mx = -inf, mn = inf, ind, ind1, pref[N], suf[N];
string s, s1;
ll ans, x;

template<class T> using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

struct RT
{
	int sum, l, r, ind;	
};
int gcd( int a, int b )
{
	return ( b ? gcd( b, a % b ) : a );
}
int lcm( int a, int b )
{
	return a / gcd( a, b ) * b;
}
int bp( int a, int b, int m )
{
	if( !b ) return 1;
	if( b & 1 ) return bp( a, b >> 1, m ) * bp( a, b >> 1, m ) % m * a % m;
	else return bp( a, b >> 1, m ) * bp( a, b >> 1, m ) % m;
}
struct po
{
	int mn, sum, mx;
};
pii t[4 * N];

void update( int pos, int val, int v = 1, int tl = 1, int tr = n )
{
	if( tl == tr ) 
	{
		if( tl % 2 ) t[v] = { val, 0 };
		else t[v] = { 0, val };
		
		return;
	}
	int tm = ( tl + tr ) >> 1;
	
	if( pos <= tm ) update( pos, val, v + v, tl, tm );
	else update( pos, val, v + v + 1, tm + 1, tr );
	
	t[v].F = t[v + v].F ^ t[v + v + 1].F;
	t[v].S = t[v + v].S ^ t[v + v + 1].S;
}
int get( int l, int r, int tp, int v = 1, int tl = 1, int tr = n )
{
	if( tl > r || l > tr ) return 0;
	if( l <= tl && tr <= r ) return ( tp ? t[v].F : t[v].S );
	
	int tm = ( tl + tr ) >> 1;
	
	return get( l, r, tp, v + v, tl, tm ) ^ get( l, r, tp, v + v + 1, tm + 1, tr );
}
void solve()
{
	cin >> n >> m;
	
	FOR( i, 1, n, 1 ) cin >> a[i], update( i, a[i] );
	
	while( m -- )
	{
		int tp; cin >> tp;
		cin >> l >> r;
		
		if( tp == 1 ) 
		{
			update( l, r );
			continue;
		}
		else
		{
			if(( r - l ) % 2 ) ans = 0;
			else if( l % 2 ) ans = get( l, r, 1 );
			else ans = get( l, r, 0 );
		}
		cout << ans << '\n'; ans = 0;
	}
}
sigma main() 
{
	//freopen("rmq.in", "r", stdin);
	//freopen("rmq.out", "w", stdout);
	    
    Shrek_Crush228	
    
    int test = 1;
    
    if( !test ) cin >> test;
	
	while( test -- )
	{
		solve();
	}
}
// solved by KluydQ

Subtask #1
12.0 / 12.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 472 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 480 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 3 ms 836 KB Output is correct
12 Correct 2 ms 860 KB Output is correct
13 Correct 2 ms 860 KB Output is correct
14 Correct 2 ms 860 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 15728 KB Output is correct
2 Correct 100 ms 16208 KB Output is correct
3 Correct 101 ms 16168 KB Output is correct
4 Correct 97 ms 15696 KB Output is correct
5 Correct 90 ms 15700 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 472 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 480 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 3 ms 836 KB Output is correct
12 Correct 2 ms 860 KB Output is correct
13 Correct 2 ms 860 KB Output is correct
14 Correct 2 ms 860 KB Output is correct
15 Correct 112 ms 15728 KB Output is correct
16 Correct 100 ms 16208 KB Output is correct
17 Correct 101 ms 16168 KB Output is correct
18 Correct 97 ms 15696 KB Output is correct
19 Correct 90 ms 15700 KB Output is correct
20 Correct 100 ms 15952 KB Output is correct
21 Correct 105 ms 15896 KB Output is correct
22 Correct 105 ms 15812 KB Output is correct
23 Correct 92 ms 15696 KB Output is correct
24 Correct 99 ms 15700 KB Output is correct