oj.uz

Submission #999736

# Submission time Handle Problem Language Result Execution time Memory
999736 2024-06-16T06:04:20 Z LilPluton XORanges (eJOI19_xoranges) C++14
100 / 100
 318 ms 14164 KB 
#include <bits/stdc++.h>
// author : Pluton
#define OPT         ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int         ll
#define ll          long long
#define pb          push_back
#define arr         array
#define fi          first
#define se          second
#define rep(i,j,k)  for(int i = j; i <= k; ++i)
#define all(a)      a.begin(),a.end()
#define pii         pair<int,int>
using namespace std;
const int INF = 1e18;

struct BIT
{
    int n;
    vector<int> ft;
    void init(int N)
    {
        n = N + 5;
        ft.assign(n + 5, 0);
    }
    void add(int pos, int val)
    {
        for (pos = pos + 1; pos <= n; pos += pos & -pos) ft[pos] += val;
    }
    int get(int pos, int res = 0)
    {
        for (pos = pos + 1; pos > 0; pos -= pos & -pos) res += ft[pos];
        return res;
    }
};
const int N = 2e5 + 5;

struct tree{
    int t[N * 4];
    tree()
    {
        memset(t, 0, sizeof(t));
    }
    void update(int node,int l,int r,int pos,int val)
    {
        if(l == r)
        {
            t[node] = val;
            return;
        }
        int mid = (l + r) / 2;
        if(pos <= mid)  update(node * 2, l, mid, pos, val);
        else    update(node * 2 + 1, mid + 1, r, pos, val);
        t[node] = (t[node * 2] ^ t[node * 2 + 1]);
    }
    int getans(int node,int tl,int tr,int l,int r)
    {
        if(tr < l || tl > r)    return 0;
        if(l <= tl && tr <= r)  return t[node];
        int mid = (tl + tr) >> 1;
        return getans(node * 2, tl, mid, l, r) ^ getans(node * 2 + 1, mid + 1, tr, l, r);
    }
} seg1,seg2;

void _()
{
    int n, q;
    cin >> n >> q;
    for(int i = 1, x; i <= n; ++i)
    {
        cin >> x;
        if(i & 1)   seg1.update(1,1,n,i / 2 + 1, x);
        else    seg2.update(1,1,n,i / 2, x);   
    }
    while(q--)
    {
        int t,a,b;
        cin >> t >> a >> b;
        if(t == 1)
        {
            if(a & 1) seg1.update(1, 1, n, a / 2 + 1, b);
            else seg2.update(1, 1, n, a / 2, b);
        }
        else
        {
            int k = b - a + 1;
            if((b - a + 1) & 1)
            {
                if(a & 1)   cout << seg1.getans(1,1,n,a / 2 + 1, a / 2 + 1 + k / 2) << endl;
                else    cout << seg2.getans(1,1,n,a / 2, a / 2 + k / 2) << endl;
            }
            else
            {
                cout << 0 << endl;
            }
        }
    }

    
}

signed main()
{
    OPT
    int tc = 1;
    while(tc--)
    {
        _();
    }
}

Subtask #1
12.0 / 12.0

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

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12888 KB Output is correct
2 Correct 2 ms 12892 KB Output is correct
3 Correct 2 ms 12892 KB Output is correct
4 Correct 2 ms 12892 KB Output is correct
5 Correct 3 ms 12892 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12892 KB Output is correct
2 Correct 2 ms 12892 KB Output is correct
3 Correct 2 ms 12892 KB Output is correct
4 Correct 2 ms 12892 KB Output is correct
5 Correct 2 ms 12892 KB Output is correct
6 Correct 2 ms 12888 KB Output is correct
7 Correct 2 ms 12892 KB Output is correct
8 Correct 2 ms 12892 KB Output is correct
9 Correct 2 ms 12892 KB Output is correct
10 Correct 3 ms 12892 KB Output is correct
11 Correct 6 ms 12892 KB Output is correct
12 Correct 6 ms 12980 KB Output is correct
13 Correct 8 ms 12984 KB Output is correct
14 Correct 8 ms 12988 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 286 ms 14164 KB Output is correct
2 Correct 318 ms 14000 KB Output is correct
3 Correct 289 ms 14000 KB Output is correct
4 Correct 275 ms 13908 KB Output is correct
5 Correct 279 ms 14160 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12892 KB Output is correct
2 Correct 2 ms 12892 KB Output is correct
3 Correct 2 ms 12892 KB Output is correct
4 Correct 2 ms 12892 KB Output is correct
5 Correct 2 ms 12892 KB Output is correct
6 Correct 2 ms 12888 KB Output is correct
7 Correct 2 ms 12892 KB Output is correct
8 Correct 2 ms 12892 KB Output is correct
9 Correct 2 ms 12892 KB Output is correct
10 Correct 3 ms 12892 KB Output is correct
11 Correct 6 ms 12892 KB Output is correct
12 Correct 6 ms 12980 KB Output is correct
13 Correct 8 ms 12984 KB Output is correct
14 Correct 8 ms 12988 KB Output is correct
15 Correct 286 ms 14164 KB Output is correct
16 Correct 318 ms 14000 KB Output is correct
17 Correct 289 ms 14000 KB Output is correct
18 Correct 275 ms 13908 KB Output is correct
19 Correct 279 ms 14160 KB Output is correct
20 Correct 182 ms 13664 KB Output is correct
21 Correct 181 ms 13560 KB Output is correct
22 Correct 220 ms 13396 KB Output is correct
23 Correct 303 ms 13904 KB Output is correct
24 Correct 270 ms 14000 KB Output is correct