Submission #1781260


Source Code Expand

Copy
#include<bits/stdc++.h>

using namespace std;

int flip[1 << 18], L[1 << 18], R[1 << 18], V[1 << 18];

void push(int k, int depth)
{
  if((flip[k] >> depth) & 1) {
    flip[k] ^= 1 << depth;
    swap(L[k], R[k]);
  }
  flip[L[k]] ^= flip[k];
  flip[R[k]] ^= flip[k];
  flip[k] = 0;
}

void update(int a, int b, int k, int l, int r, int dep, int beet)
{
  if(a >= r || b <= l) return;
  if(a <= l && r <= b) {
    flip[k] ^= 1 << beet;
    return;
  }
  push(k, dep);
  update(a, b, L[k], l, (l + r) >> 1, dep + 1, beet);
  update(a, b, R[k], (l + r) >> 1, r, dep + 1, beet);
}

int query(int x, int k, int l, int r, int dep)
{
  if(l + 1 == r) return (V[k]);
  push(k, dep);
  if(x < (l + r) / 2) return (query(x, L[k], l, (l + r) >> 1, dep + 1));
  return (query(x, R[k], (l + r) >> 1, r, dep + 1));
}


int main()
{
  int N, Q;
  scanf("%d %d", &N, &Q);

  int st = (1 << N);
  for(int i = 0; i < st - 1; i++) {
    L[i] = 2 * i + 1;
    R[i] = 2 * i + 2;
  }
  for(int i = 1; i < st; i++) {
    V[i + st - 1] = i;
  }

  while(Q--) {
    int T, A, B;
    scanf("%d %d %d", &T, &A, &B);
    if(T == 1) {
      --A;
      printf("%d\n", query(A, 0, 0, 1 << N, 0) + 1);
    } else {
      ++B;
      for(int i = 0; i < N; i++) {
        int l = 1 << i;
        int r = l * 2;
        l = max(l, A);
        r = min(r, B);
        l -= 1 << i;
        r -= 1 << i;

        //cout << l << " " << r << endl;

        if(l < r) update(l, r, 0, 0, 1 << i, 0, i);
      }
    }
  }
}

Submission Info

Submission Time
Task D - すわっぷしまーす
User ei13333
Language C++14 (GCC 5.4.1)
Score 100
Code Size 1554 Byte
Status
Exec Time 161 ms
Memory 4352 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:42:25: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &N, &Q);
                         ^
./Main.cpp:55:34: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &T, &A, &B);
                                  ^

Judge Result

Set Name Score / Max Score Test Cases
Sample 0 / 0 example_0.txt
All 100 / 100 corner_0.txt, example_0.txt, manytp1_0.txt, manytp1_1.txt, manytp1_2_0.txt, manytp1_2_1.txt, manytp2_0.txt, manytp2_1.txt, manytp2_2_0.txt, manytp2_2_1.txt, maxrand_0.txt, maxrand_1.txt, maxrand_2_0.txt, maxrand_2_1.txt, random_0.txt, random_1.txt, random_2.txt, smallrand_0.txt, smallrand_1.txt, smallrand_2.txt
Case Name Status Exec Time Memory
corner_0.txt 2 ms 2304 KB
example_0.txt 2 ms 2304 KB
manytp1_0.txt 129 ms 4352 KB
manytp1_1.txt 130 ms 4352 KB
manytp1_2_0.txt 138 ms 4352 KB
manytp1_2_1.txt 131 ms 4352 KB
manytp2_0.txt 160 ms 3456 KB
manytp2_1.txt 161 ms 3456 KB
manytp2_2_0.txt 125 ms 3456 KB
manytp2_2_1.txt 124 ms 3456 KB
maxrand_0.txt 148 ms 3968 KB
maxrand_1.txt 148 ms 3968 KB
maxrand_2_0.txt 132 ms 3968 KB
maxrand_2_1.txt 131 ms 3968 KB
random_0.txt 23 ms 2432 KB
random_1.txt 48 ms 2560 KB
random_2.txt 35 ms 3456 KB
smallrand_0.txt 3 ms 2304 KB
smallrand_1.txt 2 ms 2304 KB
smallrand_2.txt 2 ms 2304 KB