oj.uz

Submission #977221

# Submission time Handle Problem Language Result Execution time Memory
977221 2024-05-07T14:23:25 Z vahagng XORanges (eJOI19_xoranges) C++17
100 / 100
 115 ms 24656 KB 
//----------vahagng----------//
#define CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;

template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

// Defines

#define ll long long
#define all(v) v.begin(), v.end()
#define pii pair<int, int>
#define ppb pop_back
#define pb push_back
#define mii map<int, int>
#define mll map<long long, long long>
#define no_ans cout << -1 << '\n';
#define YES cout << "YES\n";
#define NO cout << "NO\n";
#define ok cout << "OK\n";

// Constants 

const ll N = 3e5 + 10, M = 105;
const ll inf = 1e18, mod = 1000000007;

// Functions

void SetIO(string str = "") {
    if (str != "") {
        freopen((str + ".in").c_str(), "r", stdin);
        freopen((str + ".out").c_str(), "w", stdout);
    } else {
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    }
}
 
void FastIO() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
}

ll add(ll a, ll b)
{
    return (a + b)%mod;
}

ll mult(ll a, ll b)
{
    return (a%mod * b%mod)%mod;
}

ll sub(ll a, ll b)
{
    return (a - b + 2*mod)%mod;
}

long long binpower(long long a, long long n) {
	if(n == 0) {
		return 1;
	}
 
	if(n == 1) {
		return a;
	}
 
	if(n % 2 == 1) {
		long long curr = binpower(a, n / 2);
		curr = mult(curr, curr);
		curr = mult(a, curr);
		return curr;
	} else {
		long long curr = binpower(a, n / 2);
		return mult(curr, curr);
	}
}

ll power(int a, int b)
{
    ll res = 1;
    while(b--)
    {
        res*=a;
    }
    return res;
}

// const int N = 2e5 + 10;
// pair<int,int>max_dist;
// vector<int>adj[N];
// int dists[N];

// void dfs(int node, int parent, int dist) 
// {
//     dists[node] = max(dists[node], dist);
// 	if(dist > max_dist.first) 
//     {
// 		max_dist = {dist, node};
// 	}
 
// 	for(auto i: adj[node]) 
//     {
// 		if(i == parent) continue;
// 		dfs(i, node, dist + 1);
// 	}
// }
 
// pair<int, int> get_farthest_distance(int node) 
// {
// 	max_dist = {-1, -1};
// 	dfs(node, -1, 0);
// 	return max_dist;
// }

void precision(int x)
{
	cout.setf(ios::fixed | ios::showpoint);
	cout.precision(x);
	return;
}

ll ceil_division(ll a, ll b)
{
    return (a + b - 1) / b;
}

ll digit_sum(int n)
{
    ll sum = 0;
    for(int i = 1; i * i <= n; i++)
    {
        if(n%i == 0)
        {
            sum += i;
            if(n/i == i || n / i == n) continue;
            sum += (n/i);
        }
    }
    return sum;
}

ll lcm(ll a, ll b)
{
    return a / gcd(a, b) * b;
}

// Solution

ll n, q;
vector<ll>v;

struct segtree{
    int size = 1;
    vector<ll>stree;
    void init()
    {
        while(size < n) size <<= 1;
        stree.assign(4*size + 10, 0);
    }
 
    void set(int i, int y, int x, int lx, int rx)
    {
        if(rx - lx == 1)
        {
            stree[x] = y;
            return;
        }
        int mid = (lx + rx)/2;
        if(i < mid)
        {
            set(i, y, 2*x + 1, lx, mid);
        }else{
            set(i, y, 2*x + 2, mid, rx);
        }
        stree[x] = stree[2*x + 1] ^ stree[2*x + 2];
    }
 
    void set(int i, int x)
    {
        set(i, x, 0, 0, size);
    }
 
    ll get(int l, int r, int x, int lx, int rx)
    {
        if(l >= rx || r <= lx)
        {
            return 0;
        }
        if(l <= lx && r >= rx)
        {
            return stree[x];
        }
        int mid = (lx + rx)/2;
        return get(l, r, 2*x + 1, lx, mid) ^ get(l, r, 2*x + 2, mid, rx);
    }
 
    ll get(int l, int r)
    {
        return get(l, r, 0, 0, size);
    }
};


/*
5 6
1 2 3 4 5
2 1 3
1 1 3
2 1 5
2 4 4
1 1 1
2 4 4
*/

void solve()
{
    cin >> n >> q;
    v.resize(n);
    for(int i = 0; i < n; i++)
    {
        cin >> v[i];
    }
    segtree st1, st2;
    st1.init();
    st2.init();
    for(int i = 0; i < n; i++)
    {
        if(i&1)
        {
            st1.set(i, v[i]);
        }else{
            st2.set(i, v[i]);
        }
    }
    while(q--)
    {
        ll type, l, r;
        cin >> type >> l >> r;
        if(type == 1)
        {
            v[l-1] = r;
            if(l&1)
            {
                st2.set(l-1, r);
            }else{
                st1.set(l-1, r);
            }
        }else{
            if(l == r)
            {
                cout << v[l-1] << '\n';
            }else{
                if(l%2 != r%2) cout << 0 << '\n';
                else{
                    if(l&1)
                    {
                        cout << st2.get(l-1, r) << '\n';
                    }else{
                        cout << st1.get(l-1, r) << '\n';
                    }
                }
            }
        }
    }
}

void precalc()
{
    
}

int main()
{
    FastIO();
    precalc();
    int test_case = 1;
    // cin >> test_case;
    while (test_case--) 
    {
        solve();
    }
    return 0;
}

Compilation message

xoranges.cpp: In function 'void SetIO(std::string)':
xoranges.cpp:33:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |         freopen((str + ".in").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
xoranges.cpp:34:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |         freopen((str + ".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
xoranges.cpp:36:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |         freopen("input.txt", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
xoranges.cpp:37:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |         freopen("output.txt", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 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 344 KB Output is correct
4 Correct 0 ms 600 KB Output is correct
5 Correct 0 ms 348 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 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 344 KB Output is correct
9 Correct 0 ms 600 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 3 ms 860 KB Output is correct
12 Correct 3 ms 860 KB Output is correct
13 Correct 3 ms 1044 KB Output is correct
14 Correct 3 ms 860 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 19712 KB Output is correct
2 Correct 109 ms 24268 KB Output is correct
3 Correct 115 ms 24656 KB Output is correct
4 Correct 107 ms 24112 KB Output is correct
5 Correct 113 ms 23924 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 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 344 KB Output is correct
9 Correct 0 ms 600 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 3 ms 860 KB Output is correct
12 Correct 3 ms 860 KB Output is correct
13 Correct 3 ms 1044 KB Output is correct
14 Correct 3 ms 860 KB Output is correct
15 Correct 108 ms 19712 KB Output is correct
16 Correct 109 ms 24268 KB Output is correct
17 Correct 115 ms 24656 KB Output is correct
18 Correct 107 ms 24112 KB Output is correct
19 Correct 113 ms 23924 KB Output is correct
20 Correct 107 ms 24212 KB Output is correct
21 Correct 104 ms 24140 KB Output is correct
22 Correct 108 ms 24024 KB Output is correct
23 Correct 102 ms 24016 KB Output is correct
24 Correct 101 ms 24080 KB Output is correct