oj.uz

Submission #960913

# Submission time Handle Problem Language Result Execution time Memory
960913 2024-04-11T08:26:15 Z Yang8on XORanges (eJOI19_xoranges) C++14
100 / 100
 256 ms 54008 KB 
#include <bits/stdc++.h>
#define Y8o "xoranges"
#define maxn 200005
#define ll long long
#define pii pair<int, int>
#define gb(i, j) ((i >> j) & 1)

using namespace std;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll GetRandom(ll l, ll r) {
    return uniform_int_distribution<ll> (l, r) (rng);
}
void iof() {
    if(fopen(Y8o".inp", "r"))
    {
        freopen(Y8o".inp", "r", stdin);
//        freopen(Y8o".out", "w", stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(NULL), cout.tie(NULL);
}
void ctime() {
    cerr << "\n" << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
}


int n, Q;
int a[maxn];

struct BIT {

    int bit[maxn][2][30];

    void update(int x, int t, int pos, int val)
    {
        while(x <= maxn - 5)
        {
            bit[x][t][pos] += val;
            x += (x & -x);
        }
    }

    int get(int x, int t, int pos)
    {
        int best = 0;
        while(x)
        {
            best += bit[x][t][pos];
            x -= (x & -x);
        }
        return best;
    }

} B;

void solve()
{
    cin >> n >> Q;
    for(int i = 1; i <= n; i ++) cin >> a[i];

    for(int i = 1; i <= n; i ++) for(int j = 0; j <= 29; j ++)
        if(gb( a[i], j )) B.update(i, i % 2, j, +1);


    for(int i = 1, id, u, v, l, r; i <= Q; i ++)
    {
        cin >> id >> u >> v, l = u, r = v;
        if(id == 1) /// a[u] = v
        {
            for(int j = 0; j <= 29; j ++)
            {
                if(gb(a[u], j) != gb(v, j))
                {
                    if(gb(v, j)) B.update(u, u % 2, j, +1);
                    else         B.update(u, u % 2, j, -1);
                }
            } a[u] = v;
        }
        else /// get range (l, r)
        {
//            int best = 0;
//            for(int j = l; j <= r; j ++)
//            {
//                int sl = (j - l + 1) * (r - j + 1);
//                if(sl % 2) best ^= a[j];
//            }
//            cout << best << ' ';

            int tmp = (r + l) % 2;
            int tmp2 = ((-l + r - l * r + 1) % 2 + 2) % 2;

            if(tmp == 1)
            {
                if(tmp2 == 0) cout << 0 << '\n';
                else
                {
                    int ans = 0;
                    for(int j = 0; j <= 29; j ++)
                    {
                        int left = (l == 1) ? 0 : B.get(l - 1, 0, j) + B.get(l - 1, 1, j);
                        int right = B.get(r, 0, j) + B.get(r, 1, j);
                        ans += (right - left) % 2 * (1 << j);
                    }
                    cout << ans << '\n';
                }
            }
            else
            {
                if(tmp2 == 0)
                {
                    int ans = 0;
                    for(int j = 0; j <= 29; j ++)
                    {
                        int left = (l == 1) ? 0 : B.get(l - 1, 1, j);
                        int right = B.get(r, 1, j);
                        ans += (right - left) % 2 * (1 << j);
                    }
                    cout << ans << '\n';
                }
                else
                {
                    int ans = 0;
                    for(int j = 0; j <= 29; j ++)
                    {
                        int left = (l == 1) ? 0 : B.get(l - 1, 0, j);
                        int right = B.get(r, 0, j);
                        ans += (right - left) % 2 * (1 << j);
                    }
                    cout << ans << '\n';
                }
            }
        }
    }
}


int main()
{
    iof();

    int nTest = 1;
//    cin >> nTest;

    while(nTest --) {
        solve();
    }

    ctime();
    return 0;
}

Compilation message

xoranges.cpp: In function 'void iof()':
xoranges.cpp:17:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |         freopen(Y8o".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12632 KB Output is correct
2 Correct 2 ms 12884 KB Output is correct
3 Correct 2 ms 12636 KB Output is correct
4 Correct 2 ms 12636 KB Output is correct
5 Correct 2 ms 12636 KB Output is correct
6 Correct 2 ms 12888 KB Output is correct
7 Correct 2 ms 12888 KB Output is correct
8 Correct 3 ms 12892 KB Output is correct
9 Correct 2 ms 12892 KB Output is correct
10 Correct 2 ms 13144 KB Output is correct
11 Correct 9 ms 13044 KB Output is correct
12 Correct 10 ms 12800 KB Output is correct
13 Correct 6 ms 12892 KB Output is correct
14 Correct 6 ms 12892 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 232 ms 49232 KB Output is correct
2 Correct 234 ms 53988 KB Output is correct
3 Correct 211 ms 54008 KB Output is correct
4 Correct 175 ms 53768 KB Output is correct
5 Correct 181 ms 53840 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12632 KB Output is correct
2 Correct 2 ms 12884 KB Output is correct
3 Correct 2 ms 12636 KB Output is correct
4 Correct 2 ms 12636 KB Output is correct
5 Correct 2 ms 12636 KB Output is correct
6 Correct 2 ms 12888 KB Output is correct
7 Correct 2 ms 12888 KB Output is correct
8 Correct 3 ms 12892 KB Output is correct
9 Correct 2 ms 12892 KB Output is correct
10 Correct 2 ms 13144 KB Output is correct
11 Correct 9 ms 13044 KB Output is correct
12 Correct 10 ms 12800 KB Output is correct
13 Correct 6 ms 12892 KB Output is correct
14 Correct 6 ms 12892 KB Output is correct
15 Correct 232 ms 49232 KB Output is correct
16 Correct 234 ms 53988 KB Output is correct
17 Correct 211 ms 54008 KB Output is correct
18 Correct 175 ms 53768 KB Output is correct
19 Correct 181 ms 53840 KB Output is correct
20 Correct 253 ms 53752 KB Output is correct
21 Correct 256 ms 53976 KB Output is correct
22 Correct 238 ms 53884 KB Output is correct
23 Correct 178 ms 53660 KB Output is correct
24 Correct 200 ms 53800 KB Output is correct