oj.uz

Submission #958680

# Submission time Handle Problem Language Result Execution time Memory
958680 2024-04-06T10:18:54 Z M_SH_O XORanges (eJOI19_xoranges) C++14
18 / 100
 35 ms 7116 KB 
#pragma GCC optimize("O3")
#pragma GCC optimization("Ofast,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
 
#include<bits/stdc++.h>
#define ll long long
#define dou long double
#define str string
#define pb push_back
#define fr first
#define se second
#define vll vector<ll>
#define vpll vector<pair<ll, ll>>
#define pll pair<ll, ll>
#define endl "\n"
 
using namespace std;
 
ll n;
ll a[100000];     
ll tree[400004];  
ll tree1[400004]; 


void build_tree1(int v, int tl, int tr) {
    if (tl == tr) 
    {
        if(tl % 2 == 1) tree1[v] = a[tl];
        else tree1[v] = 0;
    } else {
        int tm = (tl + tr) / 2;
        build_tree1(v * 2, tl, tm);
        build_tree1(v * 2 + 1, tm + 1, tr);
        tree1[v] = tree1[v * 2] ^ tree1[v * 2 + 1];
    }
}
int get_sum1(int l, int r, int v, int tl, int tr) {
    if (l <= tl && tr <= r) {
        return tree1[v];
    }
 
    if (tr < l || r < tl) {
        return 0;
    }
 
    int tm = (tl + tr) / 2;
    ll k = get_sum1(l, r, v * 2,     tl,     tm)
         ^ get_sum1(l, r, v * 2 + 1, tm + 1, tr);
    return k;
}






void build_tree(int v, int tl, int tr) {
    if (tl == tr) 
    {
        if(tl % 2 == 0) tree[v] = a[tl];
        else tree[v] = 0;
    } else {
        int tm = (tl + tr) / 2;
        build_tree(v * 2, tl, tm);
        build_tree(v * 2 + 1, tm + 1, tr);
        tree[v] = tree[v * 2] ^ tree[v * 2 + 1];
    }
}
int get_sum(int l, int r, int v, int tl, int tr) {
    if (l <= tl && tr <= r) {
        return tree[v];
    }
 
    if (tr < l || r < tl) {
        return 0;
    }
 
    int tm = (tl + tr) / 2;
    ll k = get_sum(l, r, v * 2,     tl,     tm)
         ^ get_sum(l, r, v * 2 + 1, tm + 1, tr);
    return k;
}
void update(int idx, int val, int v, int tl, int tr) 
{
    if (idx <= tl && tr <= idx) 
    {
        a[idx] = val;
        if(idx % 2 == 0) tree[v] = val;
        else tree1[v] = val;
        return;
    }
 
    if (tr < idx || idx < tl) {
        return;
    }
 
    int tm = (tl + tr) / 2;
    update(idx, val, v * 2,     tl,     tm);
    update(idx, val, v * 2 + 1, tm + 1, tr);
    tree[v] = tree[v * 2] ^ tree[v * 2 + 1];
}

 
int main()
{
    ll n, q, k, x, l, r;
    cin >> n >> q;
    for(int i = 0; i < n; i ++)
    {
        cin >> a[i];
    }
    build_tree(1, 0, n-1);
    build_tree1(1, 0, n-1);
    for(; q > 0; q --)
    {
        cin >> x >> l >> r;
        if(x == 1)
        {
            update(l-1, r, 1, 0, n-1);
        }
        else
        {
            k = 0;
            if((r-l+1) % 2 == 1) 
            {
                if(l % 2 == 1) k = get_sum(l-1, r-1, 1, 0, n-1);
                else k = get_sum1(l-1, r-1, 1, 0, n-1);
                //cout << "!!!" << endl;
            }
            
            cout << k << endl;
            
        }
    }
    
}

Compilation message

xoranges.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    2 | #pragma GCC optimization("Ofast,unroll-loops")
      |

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 4440 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
18.0 / 18.0

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

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 4440 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

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

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 4440 KB Output isn't correct
2 Halted 0 ms 0 KB -