結果

問題 No.206 数の積集合を求めるクエリ
ユーザー ふっぴーふっぴー
提出日時 2017-11-27 23:58:53
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 1,553 ms / 7,000 ms
コード長 3,337 bytes
コンパイル時間 1,797 ms
コンパイル使用メモリ 172,928 KB
実行使用メモリ 4,384 KB
最終ジャッジ日時 2023-08-18 07:54:32
合計ジャッジ時間 11,393 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,376 KB
testcase_01 AC 2 ms
4,376 KB
testcase_02 AC 2 ms
4,376 KB
testcase_03 AC 2 ms
4,380 KB
testcase_04 AC 2 ms
4,376 KB
testcase_05 AC 2 ms
4,380 KB
testcase_06 AC 3 ms
4,376 KB
testcase_07 AC 3 ms
4,384 KB
testcase_08 AC 3 ms
4,376 KB
testcase_09 AC 3 ms
4,376 KB
testcase_10 AC 2 ms
4,380 KB
testcase_11 AC 2 ms
4,376 KB
testcase_12 AC 9 ms
4,376 KB
testcase_13 AC 8 ms
4,380 KB
testcase_14 AC 8 ms
4,380 KB
testcase_15 AC 7 ms
4,376 KB
testcase_16 AC 8 ms
4,380 KB
testcase_17 AC 70 ms
4,376 KB
testcase_18 AC 36 ms
4,376 KB
testcase_19 AC 63 ms
4,380 KB
testcase_20 AC 36 ms
4,380 KB
testcase_21 AC 44 ms
4,376 KB
testcase_22 AC 43 ms
4,376 KB
testcase_23 AC 65 ms
4,380 KB
testcase_24 AC 908 ms
4,376 KB
testcase_25 AC 1,011 ms
4,376 KB
testcase_26 AC 1,553 ms
4,376 KB
testcase_27 AC 958 ms
4,376 KB
testcase_28 AC 929 ms
4,376 KB
testcase_29 AC 1,412 ms
4,376 KB
testcase_30 AC 870 ms
4,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include "bits/stdc++.h"
using namespace std;

#define DEBUG(x) cout<<#x<<": "<<x<<endl;
#define DEBUG_VEC(v) cout<<#v<<":";for(int i=0;i<v.size();i++) cout<<" "<<v[i]; cout<<endl

typedef long long ll;
#define vi vector<int>
#define vl vector<ll>
#define vii vector< vector<int> >
#define vll vector< vector<ll> >
#define vs vector<string>
#define pii pair<int,int>
#define pis pair<int,string>
#define psi pair<string,int>
#define pll pair<ll,ll>
const int inf = 1000000001;
const ll INF = 1e18 * 2;
#define MOD 1000000007
#define mod 1000000009
#define pi 3.14159265358979323846
#define Sp(p) cout<<setprecision(15)<< fixed<<p<<endl;
int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };
int dx2[8] = { 1,1,0,-1,-1,-1,0,1 }, dy2[8] = { 0,1,1,1,0,-1,-1,-1 };

void print_bit(ll n, ll k) {
	ll m = (1LL << (k - 1));
	while (m >= 1) {
		if ((n&m)) {
			cout << 1;
		}
		else {
			cout << 0;
		}
		m >>= 1;
	}
	return;
}


int main() {
	int l, m, n, i0;
	cin >> l >> m >> n;
	vi a(l), b(m);
	for (i0 = 0; i0 < l; i0++) {
		cin >> a[i0];
	}
	for (i0 = 0; i0 < m; i0++) {
		cin >> b[i0];
	}
	sort(a.begin(), a.end());
	sort(b.begin(), b.end());
	//DEBUG_VEC(a);
	//DEBUG_VEC(b);
	vl x(n / 32 + 2), y(n / 32 + 2);
	int ai = 0, bi = 0;
	for (int i = 0;; i++) {
		if (i * 32 > n) {
			break;
		}
		for (int j = 0; j < 32; j++) {
			int z = i * 32 + j;
			if (ai < l) {
				if (a[ai] == z) {
					x[i] |= (1LL << j);
				}
				if (a[ai] <= z) {
					ai++;
				}
			}
			if (bi < m) {
				if (b[bi] == z) {
					y[i] |= (1LL << j);
				}
				if (b[bi] <= z) {
					bi++;
				}
			}
		}
	}
	//DEBUG_VEC(x);
	//DEBUG_VEC(y);

	vi bitstand(1 << 16);
	for (i0 = 0; i0 < (1 << 16); i0++) {
		int cnt = 0;
		int temp = 1;
		for (int i = 0; i < 16; i++) {
			if (i0 & temp) {
				cnt++;
			}
			temp <<= 1;
		}
		bitstand[i0] = cnt;
	}

	int q;
	cin >> q;
	int length = x.size();
	for (i0 = 0; i0 < q; i0++) {
		int i, j;
		for (i = length - 1; i >= 0; i--) {
			//print_bit(y[i], 64);
		}
		//cout << endl;
		int ans = 0;
		for (i = 0; i < length; i++) {
			ll temp = x[i] & y[i];
			ll mask = (1 << 16) - 1;
			for (j = 0; j < 2; j++) {
				ll bit = temp & mask;
				ans += bitstand[bit];
				temp >>= 16;
			}
		}
		ll mask = 1 << 31;
		for (i = length - 1; i >= 0; i--) {
			y[i] = (y[i] & (mask - 1)) << 1;
			if (i != 0) {
				if (y[i - 1] & mask) {
					y[i] |= 1ULL;
				}
			}
		}
		cout << ans << endl;
	}
}

/*
100 100 100 
52 21 91 38 1 8 3 20 17 73 14 82 26 88 25 89 72 56 11 55 9 62 51 32 66 97 58 75 61 74 4 84 86 100 64 87 69 78 54 45 34 7 81 60 98 23 2 16 18 6 5 41 63 57 96 36 99 27 53 30 39 10 42 12 35 92 28 33 50 83 90 22 71 93 15 13 77 70 46 80 67 29 95 24 37 47 68 59 19 44 79 40 65 48 43 85 31 94 76 49 
53 89 78 21 97 44 40 43 86 26 95 82 57 60 66 42 75 45 4 77 91 9 7 90 2 58 51 12 16 27 13 71 52 30 50 8 84 83 65 5 54 85 55 99 6 24 14 47 28 11 76 64 56 1 34 29 3 48 17 33 87 15 94 46 62 70 35 41 68 18 32 96 100 23 25 88 49 73 31 37 59 69 22 98 20 19 92 38 80 79 81 39 67 74 36 63 72 93 61 10 
1

50 50 150 
92 135 12 87 104 130 21 38 60 81 80 145 29 120 52 136 66 57 133 22 1 15 56 111 93 137 114 116 97 115 37 28 32 122 17 113 73 101 100 98 138 127 109 144 91 36 74 134 72 88 
11 25 60 56 75 39 38 8 12 90 9 63 2 58 80 94 28 45 31 34 100 13 88 35 85 3 54 43 40 71 19 21 69 98 66 73 65 46 52 84 77 17 59 67 4 99 7 51 62 83 
150
*/
0