Submission #307143

---

Source Code Expand

#include <cstdio>
#include <vector>
#include <algorithm>
#include <emmintrin.h>

using namespace std;

// pminsd 命令 (32bit整数のmin) の関数化
static inline __m128i __attribute__((always_inline))
_mm_min_epi32(__m128i a, __m128i b){
    __asm__("pminsd %1, %0" : "+x" (a) : "xm" (b));
    return a;
}

// 入力された数列
static int32_t a[100008];
// XORの累積和
static int32_t b[100008];
// i番目の要素の次にj番目のビットが0になる要素のテーブル
static int32_t next_table[1000008][32];

int main(){
	// 入力の読み込み
	int n, q;
	scanf("%d%d", &n, &q);
	for(int i = 0; i < n; ++i){ scanf("%d", a + i); }
	// テーブルの生成
	for(int i = 0; i < n; ++i){
		b[i + 1] = b[i] ^ a[i];
	}
	for(int i = 0; i < 32; ++i){
		int32_t last = n;
		for(int j = n - 1; j >= 0; --j){
			next_table[j][i] = last;
			if((a[j] & (1 << i)) == 0){ last = j; }
		}
	}
	// クエリ処理ループ
	int32_t m = -1;
	while(q--){
		// 入力・スクランブルの除去
		int l, r;
		scanf("%d%d", &l, &r);
		if(m >= 0){
			l = ((int64_t)l + m) % n;
			r = ((int64_t)r + m) % n + 1;
		}else{
			--l;
		}
		// 初期値 (k=l+1) を求める
		int32_t xor_tail = b[r];
		int32_t and_sum = a[l];
		int32_t answer = and_sum - (xor_tail ^ b[l + 1]);
		const __m128i v_xor_tail = _mm_set1_epi32(xor_tail);
		// ANDで結合した値を1ビットずつ変化させる
		for(int i = l; i < r - 1; ){
			// 次に値が変化する位置を求めて区間の終端とする
			int last = r - 1;
			for(int j = 0; j < 32; ++j){
				if(and_sum & (1 << j)){
					last = min(last, next_table[i][j]);
				}
			}
			// 区間内で最小の x_k ^ x_r を求める
			int j = i + 1;
			int32_t xor_min = xor_tail ^ b[i + 1];
			__m128i v_xor_min = _mm_set1_epi32(xor_min);
			for(; j + 3 <= last; j += 4){
				const __m128i bj = _mm_loadu_si128((const __m128i *)(b + j));
				v_xor_min = _mm_min_epi32(v_xor_min, _mm_xor_si128(bj, v_xor_tail));
			}
			// 端数処理
			for(; j <= last; ++j){
				xor_min = min(xor_min, xor_tail ^ b[j]);
			}
			// リダクション
			v_xor_min = _mm_min_epi32(
				v_xor_min, _mm_srli_si128(v_xor_min, 8));
			v_xor_min = _mm_min_epi32(
				v_xor_min, _mm_srli_si128(v_xor_min, 4));
			xor_min = min(xor_min, _mm_cvtsi128_si32(v_xor_min));
			answer = max(answer, and_sum - xor_min);
			// 区間を進める
			and_sum &= a[last];
			i = last;
		}
		printf("%d\n", answer);
		m = (answer < 0 ? -answer : answer);
	}
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:25:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &q);
                       ^
./Main.cpp:26:48: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 0; i < n; ++i){ scanf("%d", a + i); }
                                                ^
./Main.cpp:43:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &l, &r);
                        ^

Judge Result