oj.uz

Submission #999737

# Submission time Handle Problem Language Result Execution time Memory
999737 2024-06-16T06:04:40 Z vjudge1 XORanges (eJOI19_xoranges) C++17
100 / 100
 301 ms 14084 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 12888 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 3 ms 12888 KB Output is correct
2 Correct 3 ms 12892 KB Output is correct
3 Correct 3 ms 12888 KB Output is correct
4 Correct 2 ms 12888 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 12888 KB Output is correct
4 Correct 2 ms 12892 KB Output is correct
5 Correct 2 ms 12892 KB Output is correct
6 Correct 3 ms 12888 KB Output is correct
7 Correct 3 ms 12892 KB Output is correct
8 Correct 3 ms 12888 KB Output is correct
9 Correct 2 ms 12888 KB Output is correct
10 Correct 3 ms 12892 KB Output is correct
11 Correct 7 ms 12892 KB Output is correct
12 Correct 6 ms 12892 KB Output is correct
13 Correct 9 ms 12892 KB Output is correct
14 Correct 8 ms 12888 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 294 ms 14084 KB Output is correct
2 Correct 282 ms 13908 KB Output is correct
3 Correct 301 ms 13904 KB Output is correct
4 Correct 276 ms 13912 KB Output is correct
5 Correct 277 ms 14052 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 12888 KB Output is correct
4 Correct 2 ms 12892 KB Output is correct
5 Correct 2 ms 12892 KB Output is correct
6 Correct 3 ms 12888 KB Output is correct
7 Correct 3 ms 12892 KB Output is correct
8 Correct 3 ms 12888 KB Output is correct
9 Correct 2 ms 12888 KB Output is correct
10 Correct 3 ms 12892 KB Output is correct
11 Correct 7 ms 12892 KB Output is correct
12 Correct 6 ms 12892 KB Output is correct
13 Correct 9 ms 12892 KB Output is correct
14 Correct 8 ms 12888 KB Output is correct
15 Correct 294 ms 14084 KB Output is correct
16 Correct 282 ms 13908 KB Output is correct
17 Correct 301 ms 13904 KB Output is correct
18 Correct 276 ms 13912 KB Output is correct
19 Correct 277 ms 14052 KB Output is correct
20 Correct 210 ms 13492 KB Output is correct
21 Correct 183 ms 13524 KB Output is correct
22 Correct 184 ms 13652 KB Output is correct
23 Correct 276 ms 14056 KB Output is correct
24 Correct 279 ms 13904 KB Output is correct