oj.uz

Submission #960907

# Submission time Handle Problem Language Result Execution time Memory
960907 2024-04-11T08:05:18 Z Yang8on XORanges (eJOI19_xoranges) C++14
55 / 100
 1000 ms 48288 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];

//    n = GetRandom(5, 5), Q = GetRandom(1, 10);
//    cout << n << ' ' << Q << '\n';
//    for(int i = 1; i <= n; i ++) a[i] = GetRandom(1, 10), cout << a[i] << ' ';
//    cout << '\n';

    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;
//        id = GetRandom(1, 2);
//        if(id == 1) u = GetRandom(1, n), v = GetRandom(1, 10);
//        else { u = GetRandom(1, n), v = GetRandom(1, n); if(u > v) swap(u, v); l = u, r = v; }
//        cout << id << ' ' << u << ' ' << v << '\n';

        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)
        {
//            cout << "ANS :" << ' ';

            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 << '\n';

//            int ans = 0, st = l % 2, len = (r - l + 1) % 2;
//            int t = (st != len) ? 0 : 1;
//
//            for(int j = 0; j <= 29; j ++)
//            {
//                int left = l == 1 ? 0 : B.get(l - 1, t, j);
//                int right = B.get(r, t, j);
//
//                ans += (1 << j) * ( (right - left) % 2 );
//            }
//
//            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 12632 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 12892 KB Output is correct
3 Correct 2 ms 12888 KB Output is correct
4 Correct 2 ms 12892 KB Output is correct
5 Correct 2 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 12632 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 12892 KB Output is correct
8 Correct 2 ms 12888 KB Output is correct
9 Correct 2 ms 12892 KB Output is correct
10 Correct 2 ms 12892 KB Output is correct
11 Correct 10 ms 12956 KB Output is correct
12 Correct 10 ms 13072 KB Output is correct
13 Correct 23 ms 12892 KB Output is correct
14 Correct 24 ms 12892 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1066 ms 48288 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12632 KB Output is correct
2 Correct 2 ms 12632 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 12892 KB Output is correct
8 Correct 2 ms 12888 KB Output is correct
9 Correct 2 ms 12892 KB Output is correct
10 Correct 2 ms 12892 KB Output is correct
11 Correct 10 ms 12956 KB Output is correct
12 Correct 10 ms 13072 KB Output is correct
13 Correct 23 ms 12892 KB Output is correct
14 Correct 24 ms 12892 KB Output is correct
15 Execution timed out 1066 ms 48288 KB Time limit exceeded
16 Halted 0 ms 0 KB -