oj.uz

Submission #1050311

# Submission time Handle Problem Language Result Execution time Memory
1050311 2024-08-09T08:39:31 Z Nickpapadak XORanges (eJOI19_xoranges) C++14
100 / 100
 82 ms 14676 KB 
#include<bits/stdc++.h>
using namespace std;
const unsigned int MAXN = 2e+5 + 10;
bool mp[MAXN];
int pf1[MAXN],pf2[MAXN], a[MAXN];
int seg1[4*MAXN], seg2[4*MAXN];
int N, Q;
int cealingN;

int build1(int low, int high, int indx){
    // printf("%d %d: %d %d\n", low, high, pf1[low], pf1[high]);
    if(low == high){
        // printf("%d %d: %d\n", low, high, pf1[low]);
        return seg1[indx] = pf1[low];
    }
    int mid = (low+high) >> 1;
    
    // if(low > high) return seg1[indx] = 0;
    // printf("%d %d\n", low, high);
    build1(low, mid, 2*indx);
    build1(mid+1, high, 2*indx+1);
    seg1[indx] = seg1[2*indx] ^ seg1[2*indx+1]; // ----------------------------------
    // printf("%d %d: %d\n", low, high, seg1[indx]);
    return seg1[indx];
}

int build2(int low, int high, int indx){
    // printf("%d %d: %d %d\n", low, high, pf1[low], pf1[high]);
    if(low == high){
        return seg2[indx] = pf2[low];
    }
    int mid = (low+high) >> 1;
    
    // if(low > high) return seg1[indx] = 0;
    // printf("%d %d\n", low, high);
    build2(low, mid, 2*indx);
    build2(mid+1, high, 2*indx+1);
    seg2[indx] = seg2[2*indx] ^ seg2[2*indx+1]; // ----------------------------------
    // printf("%d %d: %d\n", low, high, seg2[indx]);
    return seg2[indx];
}

int Query1(int low, int high, int i, int j, int indx){
    if(low > j || high < i) return 0;
    // printf("%d %d: %d\n", low, high, seg1[indx]);
    if(low >= i && high <= j) return seg1[indx];
    int mid = (low+high)>>1;
    int x = Query1(low, mid, i, j, 2*indx);
    int y = Query1(mid+1, high, i, j, 2*indx+1);
    // printf("%d %d: %d %d %d\n",low, high, x, y, x ^ y);
    return x ^ y;
}

int Query2(int low, int high, int i, int j, int indx){
    if(low > j || high < i) return 0;
    if(low >= i && high <= j) return seg2[indx];
    int mid = (low+high)>>1;
    int x = Query2(low, mid, i, j, 2*indx);
    int y = Query2(mid+1, high, i, j, 2*indx+1);
    // printf("%d %d: %d %d %d\n",low, high, x, y, x ^ y);
    return x ^ y;
}

int Update1(int low, int high, int i, int indx){
    if(low > i || high < i) return seg1[indx];
    if(low == high) return seg1[indx] = pf1[i];
    int mid = (low+high)>>1;
    seg1[indx] = Update1(low,mid,i,2*indx) ^ Update1(mid+1,high, i, 2*indx+1);
    return seg1[indx];
}

int Update2(int low, int high, int i, int indx){
    if(low > i || high < i) return seg2[indx];
    if(low == high) return seg2[indx] = pf2[i];
    int mid = (low+high)>>1;
    seg2[indx] = Update2(low,mid,i,2*indx) ^ Update2(mid+1,high, i, 2*indx+1);
    return seg2[indx];
}

int main(){
    scanf("%d%d",&N,&Q);
    // mp.resize(N+1, 0);
    cealingN = N>>1;
    if(N%2 == 1) cealingN++;
    for(int i = 1; i<=N;++i){
        scanf("%d",&a[i]);
        if(i %2 == 1) pf1[(i>>1) +1] = a[i];
        else          pf2[i>>1] = a[i];
    }
    // pf1[1] = a[1];
    // for(int i = 1; i<=N; i++){
    //     pf1[i] = pf1[i-1] ^ a[i*2-1];
    // }
    // for(int i = 1; i<=N >> 1; i++){
    //     pf2[i] = pf2[i-1] ^ a[i*2];
    // }
    build1(1, cealingN, 1);
    build2(1, N>>1, 1);
    // for(int i = 1; i <=4*N;++i){
        // printf("%d ", seg1[i]);
    // }
    while(Q--){
        int s,b, type;
        scanf("%d%d%d", &type, &s, &b);
        if(type == 2){
            int ans = 0;
            // for(int i = 1; i <= b-s+1; ++i){
                // for(int j = s; j+i-1 <= b;++j){
                    // ans ^= (pf[j+i-1] ^ pf[j-1]);
                //     // changemp(j+i-1);
                //     // changemp(j+i-1);
                //     for(int k = j; k <= j+i-1; ++k) mp[k] = !mp[k];
                //     // mp[j+i-1] = !mp[j+i-1];
                //     // mp[j-1] = !mp[j-1];
                // }
            // }
            if((b-s+1) % 2 == 1){
                if(s % 2 == 1) ans = Query1(1, cealingN, (s>>1)+1, (b>>1)+1, 1);
                else           ans = Query2(1, N>>1, (s>>1), b>>1, 1);
            }
            // for(int i = 1; i<=N;++i){
                // printf("[%d]", i);
            // }
            // printf("\n");
            // for(int i = 1; i<=N;++i){
                // printf(" %d ", mp[i]);
                // mp[i] = 0;
            // }
            // printf("\n");
            printf("%d\n", ans);
        // }
        }else{
            // a[s] = b;
            // pf1[1] = a[1];
            if(s % 2 == 1){
                pf1[(s>>1)+1] = b;
                Update1(1, cealingN, (s>>1)+1, 1);
            }
            else{
                pf2[s>>1] = b;
                Update2(1, N>>1, s>>1, 1);
            }
        }
        //     for(int i = s; i<=N;++i){
        //         pf[i] = pf[i-1] ^ a[i];
        //     }
        // }
    }
    return 0;
}

Compilation message

xoranges.cpp: In function 'int main()':
xoranges.cpp:81:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |     scanf("%d%d",&N,&Q);
      |     ~~~~~^~~~~~~~~~~~~~
xoranges.cpp:86:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |         scanf("%d",&a[i]);
      |         ~~~~~^~~~~~~~~~~~
xoranges.cpp:104:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  104 |         scanf("%d%d%d", &type, &s, &b);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

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

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6588 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 2 ms 6600 KB Output is correct
12 Correct 2 ms 6748 KB Output is correct
13 Correct 2 ms 6748 KB Output is correct
14 Correct 2 ms 6748 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 9908 KB Output is correct
2 Correct 82 ms 14676 KB Output is correct
3 Correct 73 ms 14672 KB Output is correct
4 Correct 69 ms 14416 KB Output is correct
5 Correct 69 ms 14416 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6588 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 2 ms 6600 KB Output is correct
12 Correct 2 ms 6748 KB Output is correct
13 Correct 2 ms 6748 KB Output is correct
14 Correct 2 ms 6748 KB Output is correct
15 Correct 72 ms 9908 KB Output is correct
16 Correct 82 ms 14676 KB Output is correct
17 Correct 73 ms 14672 KB Output is correct
18 Correct 69 ms 14416 KB Output is correct
19 Correct 69 ms 14416 KB Output is correct
20 Correct 71 ms 14348 KB Output is correct
21 Correct 70 ms 14420 KB Output is correct
22 Correct 77 ms 14548 KB Output is correct
23 Correct 72 ms 14420 KB Output is correct
24 Correct 71 ms 14420 KB Output is correct