oj.uz

Submission #960957

# Submission time Handle Problem Language Result Execution time Memory
960957 2024-04-11T09:50:52 Z vjudge1 XORanges (eJOI19_xoranges) C++17
100 / 100
 232 ms 52084 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 12636 KB Output is correct
3 Correct 2 ms 12632 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 12892 KB Output is correct
2 Correct 2 ms 12892 KB Output is correct
3 Correct 2 ms 12880 KB Output is correct
4 Correct 2 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 2 ms 12632 KB Output is correct
2 Correct 2 ms 12636 KB Output is correct
3 Correct 2 ms 12632 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 12892 KB Output is correct
7 Correct 2 ms 12892 KB Output is correct
8 Correct 2 ms 12880 KB Output is correct
9 Correct 2 ms 12892 KB Output is correct
10 Correct 3 ms 12892 KB Output is correct
11 Correct 7 ms 12888 KB Output is correct
12 Correct 7 ms 12892 KB Output is correct
13 Correct 7 ms 12900 KB Output is correct
14 Correct 7 ms 12892 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 226 ms 51832 KB Output is correct
2 Correct 210 ms 51708 KB Output is correct
3 Correct 210 ms 51796 KB Output is correct
4 Correct 187 ms 51904 KB Output is correct
5 Correct 174 ms 52084 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 12636 KB Output is correct
3 Correct 2 ms 12632 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 12892 KB Output is correct
7 Correct 2 ms 12892 KB Output is correct
8 Correct 2 ms 12880 KB Output is correct
9 Correct 2 ms 12892 KB Output is correct
10 Correct 3 ms 12892 KB Output is correct
11 Correct 7 ms 12888 KB Output is correct
12 Correct 7 ms 12892 KB Output is correct
13 Correct 7 ms 12900 KB Output is correct
14 Correct 7 ms 12892 KB Output is correct
15 Correct 226 ms 51832 KB Output is correct
16 Correct 210 ms 51708 KB Output is correct
17 Correct 210 ms 51796 KB Output is correct
18 Correct 187 ms 51904 KB Output is correct
19 Correct 174 ms 52084 KB Output is correct
20 Correct 224 ms 51408 KB Output is correct
21 Correct 232 ms 51608 KB Output is correct
22 Correct 229 ms 51600 KB Output is correct
23 Correct 190 ms 51800 KB Output is correct
24 Correct 177 ms 51892 KB Output is correct