Submission #1050306

#	Time	Username	Problem	Language	Result	Execution time	Memory
1050306		Nickpapadak	XORanges (eJOI19_xoranges)	C++14	0 / 100	107 ms	18008 KiB

xoranges

#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 (stderr)

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: 0 / 12
• Subtask 2: 0 / 18
• Subtask 3: 0 / 25
• Subtask 4: 0 / 20
• Subtask 5: 0 / 25