oj.uz

Submission #1020967

# Submission time Handle Problem Language Result Execution time Memory
1020967 2024-07-12T12:17:18 Z FIFI_cpp XORanges (eJOI19_xoranges) C++17
100 / 100
 432 ms 20560 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <stack>
#include <deque>
#include <fstream>
#include <iterator>
#include <set>
#include <map>
#include <unordered_map>
#include <iomanip>
#include <cctype>
#include <string>
#include <cassert>
#include <set>
#include <bitset>
#include <unordered_set>
using ll = int64_t;
#define pb push_back
#define all(a) a.begin(),a.end()
#define ppi pair<pair<int,int>,int>
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define int int64_t
// xcode cant include bits/stdc++.h
using namespace std;
//ifstream fin ("sleepy.in");
//ofstream fout ("sleepy.out");
/*   /\_/\
*   (= ._.)
*   / >  \>
*/
// encouraging cat
//const int INF = 10000000000000000;
const int mod = 1000000007;
const int MAXN = 800010;
struct node
{
    int even,odd;
};
vector<pair<int,int>> t;
vector<int> a;
pair<int,int> merge(int v)
{
    t[v].first = t[v * 2].first ^ t[v * 2 + 1].first;
    t[v].second = t[v * 2].second ^ t[v * 2 + 1].second;
    return t[v];
}
void build(int v, int tl, int tr)
{
    if (tl == tr)
    {
        if (tl % 2 == 0)
        {
            t[v].first = a[tl];
            t[v].second = 0;
        }
        else
        {
            t[v].first = 0;
            t[v].second = a[tl];
        }
    }
    else
    {
        int tm = (tl + tr) / 2;
        build(v*2, tl, tm);
        build(v*2+1, tm+1, tr);
        merge(v);
    }
}
int query(int v, int tl, int tr, int l, int r,int p) {
    if (l > r)
        return 0;
    if (l == tl && r == tr)
    {
        if (p == 0)
            return t[v].first;
        return t[v].second;
    }
    int tm = (tl + tr) / 2;
    return query(v*2, tl, tm, l, min(r, tm),p)
           ^ query(v*2+1, tm+1, tr, max(l, tm+1), r,p);
}
void update(int v, int tl, int tr, int pos, int new_val) {
    if (tl == tr) {
        if (tr % 2 == 0)
            t[v].first = new_val;
        else
            t[v].second = new_val;
    } else {
        int tm = (tl + tr) / 2;
        if (pos <= tm)
            update(v*2, tl, tm, pos, new_val);
        else
            update(v*2+1, tm+1, tr, pos, new_val);
        merge(v);
    }
}

int32_t main() {
    int n,q;
    cin >> n >> q;
    a.resize(n);
    t.resize(MAXN);
    for (int i = 0;i < n;i++)
        cin >> a[i];
    build(1, 0, n - 1);
    while (q--)
    {
        int t;
        cin >> t;
        if (t == 1)
        {
            int i,v;
            cin >> i >> v;
            i--;
            a[i] = v;
            update(1, 0, n - 1, i, v);
        }
        else
        {
            int l,r;
            cin >> l >> r;
            l--;
            r--;
            if ((l - r + 1) % 2 == 0)
            {
                cout << 0 << '\n';
                continue;
            }
            else if (l - r + 1 == 2)
            {
                int cr = a[l];
                cr ^= a[r];
                cout << cr << '\n';
                continue;
            }
            cout << query(1, 0, n - 1, l, r,l % 2) << '\n';
        }
    }
    return 0;
}

Compilation message

xoranges.cpp:32:9: warning: "/*" within comment [-Wcomment]
   32 | /*   /\_/\
      |

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12888 KB Output is correct
2 Correct 2 ms 12888 KB Output is correct
3 Correct 2 ms 12776 KB Output is correct
4 Correct 3 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 12892 KB Output is correct
2 Correct 3 ms 12892 KB Output is correct
3 Correct 5 ms 12892 KB Output is correct
4 Correct 3 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 3 ms 12888 KB Output is correct
2 Correct 2 ms 12888 KB Output is correct
3 Correct 2 ms 12776 KB Output is correct
4 Correct 3 ms 12892 KB Output is correct
5 Correct 2 ms 12892 KB Output is correct
6 Correct 3 ms 12892 KB Output is correct
7 Correct 3 ms 12892 KB Output is correct
8 Correct 5 ms 12892 KB Output is correct
9 Correct 3 ms 12892 KB Output is correct
10 Correct 3 ms 12892 KB Output is correct
11 Correct 9 ms 12892 KB Output is correct
12 Correct 10 ms 12892 KB Output is correct
13 Correct 11 ms 12876 KB Output is correct
14 Correct 11 ms 12892 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 408 ms 18368 KB Output is correct
2 Correct 416 ms 20520 KB Output is correct
3 Correct 432 ms 20560 KB Output is correct
4 Correct 379 ms 20016 KB Output is correct
5 Correct 391 ms 20156 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12888 KB Output is correct
2 Correct 2 ms 12888 KB Output is correct
3 Correct 2 ms 12776 KB Output is correct
4 Correct 3 ms 12892 KB Output is correct
5 Correct 2 ms 12892 KB Output is correct
6 Correct 3 ms 12892 KB Output is correct
7 Correct 3 ms 12892 KB Output is correct
8 Correct 5 ms 12892 KB Output is correct
9 Correct 3 ms 12892 KB Output is correct
10 Correct 3 ms 12892 KB Output is correct
11 Correct 9 ms 12892 KB Output is correct
12 Correct 10 ms 12892 KB Output is correct
13 Correct 11 ms 12876 KB Output is correct
14 Correct 11 ms 12892 KB Output is correct
15 Correct 408 ms 18368 KB Output is correct
16 Correct 416 ms 20520 KB Output is correct
17 Correct 432 ms 20560 KB Output is correct
18 Correct 379 ms 20016 KB Output is correct
19 Correct 391 ms 20156 KB Output is correct
20 Correct 342 ms 20264 KB Output is correct
21 Correct 314 ms 20148 KB Output is correct
22 Correct 293 ms 20052 KB Output is correct
23 Correct 386 ms 20072 KB Output is correct
24 Correct 381 ms 20052 KB Output is correct