oj.uz

Submission #1020964

# Submission time Handle Problem Language Result Execution time Memory
1020964 2024-07-12T12:13:00 Z FIFI_cpp XORanges (eJOI19_xoranges) C++17
55 / 100
 85 ms 12144 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 = 200010;
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 1 ms 3420 KB Output is correct
2 Correct 2 ms 3420 KB Output is correct
3 Correct 1 ms 3420 KB Output is correct
4 Correct 1 ms 3504 KB Output is correct
5 Correct 1 ms 3420 KB Output is correct

Subtask #2
18.0 / 18.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3420 KB Output is correct
2 Correct 2 ms 3420 KB Output is correct
3 Correct 1 ms 3420 KB Output is correct
4 Correct 1 ms 3504 KB Output is correct
5 Correct 1 ms 3420 KB Output is correct
6 Correct 4 ms 3420 KB Output is correct
7 Correct 3 ms 3420 KB Output is correct
8 Correct 2 ms 3420 KB Output is correct
9 Correct 2 ms 3420 KB Output is correct
10 Correct 2 ms 3420 KB Output is correct
11 Correct 8 ms 3676 KB Output is correct
12 Correct 9 ms 3676 KB Output is correct
13 Correct 11 ms 3676 KB Output is correct
14 Correct 11 ms 3676 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 85 ms 12144 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3420 KB Output is correct
2 Correct 2 ms 3420 KB Output is correct
3 Correct 1 ms 3420 KB Output is correct
4 Correct 1 ms 3504 KB Output is correct
5 Correct 1 ms 3420 KB Output is correct
6 Correct 4 ms 3420 KB Output is correct
7 Correct 3 ms 3420 KB Output is correct
8 Correct 2 ms 3420 KB Output is correct
9 Correct 2 ms 3420 KB Output is correct
10 Correct 2 ms 3420 KB Output is correct
11 Correct 8 ms 3676 KB Output is correct
12 Correct 9 ms 3676 KB Output is correct
13 Correct 11 ms 3676 KB Output is correct
14 Correct 11 ms 3676 KB Output is correct
15 Runtime error 85 ms 12144 KB Execution killed with signal 11
16 Halted 0 ms 0 KB -