oj.uz

Submission #958644

# Submission time Handle Problem Language Result Execution time Memory
958644 2024-04-06T09:35:03 Z M_SH_O XORanges (eJOI19_xoranges) C++14
12 / 100
 1000 ms 3152 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];  
void build_tree(int v, int tl, int tr) {
    if (tl == tr) {
        tree[v] = a[tl];
    } 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;
        tree[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 q, k, x, l, r;
    cin >> n >> q;
    for(int i = 0; i < n; i ++)
    {
        cin >> a[i];
    }
    build_tree(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 = get_sum(l-1, r-1, 1, 0, n-1);;
            for(int i1 = 1; i1 <= r-l; i1 ++)
            {
                for(int i = l-1; i < r-i1+1; i ++)
                {
                    k ^= get_sum(i, i+i1-1, 1, 0, n-1);
                }
            }
            cout << k << endl;
            
        }
    }
    
}

Compilation message

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

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 348 KB Output is correct
2 Correct 4 ms 348 KB Output is correct
3 Correct 3 ms 348 KB Output is correct
4 Correct 16 ms 348 KB Output is correct
5 Correct 17 ms 344 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 851 ms 344 KB Output is correct
2 Correct 733 ms 344 KB Output is correct
3 Correct 948 ms 548 KB Output is correct
4 Execution timed out 1020 ms 344 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 348 KB Output is correct
2 Correct 4 ms 348 KB Output is correct
3 Correct 3 ms 348 KB Output is correct
4 Correct 16 ms 348 KB Output is correct
5 Correct 17 ms 344 KB Output is correct
6 Correct 851 ms 344 KB Output is correct
7 Correct 733 ms 344 KB Output is correct
8 Correct 948 ms 548 KB Output is correct
9 Execution timed out 1020 ms 344 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 28 ms 3152 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 3 ms 348 KB Output is correct
2 Correct 4 ms 348 KB Output is correct
3 Correct 3 ms 348 KB Output is correct
4 Correct 16 ms 348 KB Output is correct
5 Correct 17 ms 344 KB Output is correct
6 Correct 851 ms 344 KB Output is correct
7 Correct 733 ms 344 KB Output is correct
8 Correct 948 ms 548 KB Output is correct
9 Execution timed out 1020 ms 344 KB Time limit exceeded
10 Halted 0 ms 0 KB -