oj.uz

답안 #644726

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
644726 2022-09-25T06:47:35 Z ymm 운세 보기 2 (JOI14_fortune_telling2) C++17
35 / 100
 2766 ms 4204 KB 
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 2000*100;
const int S0 = 2000*16;
const int S1 = 2000;
pii ab[N];
unsigned short sa[N], sb[N];
int q[N+32];
unsigned short sq[N];
int n;

/*
__attribute__((optimize("O3,unroll-loops"),target("avx2")))
void up(unsigned short x, unsigned short y, unsigned short z, int l, int r)
{
	l *= S1; r *= S1;
	Loop (i,l,r) {
		unsigned short v = sa[i], u = sb[i];
		v ^= v <= x? u: 0;
		v ^= v <= y? u: 0;
		v ^= v <= z? u: 0;
		sa[i] = v;
	}
}
*/
void up(unsigned short x, unsigned short y, unsigned short z, int l, int r);

asm("\n"
"	.p2align 4\n"
"	.globl	_Z2uptttii\n"
"	.type	_Z2uptttii, @function\n"
"_Z2uptttii:\n"
".myLFB9901:\n"
"	.cfi_startproc\n"
"	movl	%edi, %eax\n"
"	imull	$2000, %ecx, %r10d\n"
"	movl	%esi, %edi\n"
"	movl	%edx, %r9d\n"
"	imull	$2000, %r8d, %esi\n"
"	cmpl	%r8d, %ecx\n"
"	jge	.myL103\n"
"	movslq	%esi, %rsi\n"
"	movslq	%r10d, %r10\n"
"	vmovd	%edi, %xmm5\n"
"	movslq	%ecx, %rdx\n"
"	vmovd	%eax, %xmm6\n"
"	subq	%r10, %rsi\n"
"	leaq	sa(%rip), %rcx\n"
"	xorl	%eax, %eax\n"
"	vmovd	%r9d, %xmm4\n"
"	vpbroadcastw	%xmm6, %ymm6\n"
"	vpxor	%xmm3, %xmm3, %xmm3\n"
"	addq	%rsi, %rsi\n"
"	imulq	$4000, %rdx, %rdx\n"
"	leaq	-32(%rsi), %rdi\n"
"	vpbroadcastw	%xmm5, %ymm5\n"
"	shrq	$5, %rdi\n"
"	leaq	sb(%rip), %r8\n"
"	vpbroadcastw	%xmm4, %ymm4\n"
"	addq	$1, %rdi\n"
"	addq	%rdx, %rcx\n"
"	addq	%r8, %rdx\n"
"	andl	$3, %edi\n"
"	je	.myL85\n"
"	cmpq	$1, %rdi\n"
"	je	.myL97\n"
"	cmpq	$2, %rdi\n"
"	je	.myL98\n"
"	vmovdqa	(%rcx), %ymm0\n"
"	vmovdqa	(%rdx), %ymm1\n"
"	movl	$32, %eax\n"
"	vpsubusw	%ymm6, %ymm0, %ymm2\n"
"	vpxor	%ymm1, %ymm0, %ymm7\n"
"	vpcmpeqw	%ymm3, %ymm2, %ymm2\n"
"	vpblendvb	%ymm2, %ymm7, %ymm0, %ymm0\n"
"	vpsubusw	%ymm5, %ymm0, %ymm2\n"
"	vpxor	%ymm0, %ymm1, %ymm7\n"
"	vpcmpeqw	%ymm3, %ymm2, %ymm2\n"
"	vpblendvb	%ymm2, %ymm7, %ymm0, %ymm0\n"
"	vpsubusw	%ymm4, %ymm0, %ymm2\n"
"	vpxor	%ymm0, %ymm1, %ymm1\n"
"	vpcmpeqw	%ymm3, %ymm2, %ymm2\n"
"	vpblendvb	%ymm2, %ymm1, %ymm0, %ymm0\n"
"	vmovdqa	%ymm0, (%rcx)\n"
".myL98:\n"
"	vmovdqa	(%rcx,%rax), %ymm0\n"
"	vmovdqa	(%rdx,%rax), %ymm1\n"
"	vpsubusw	%ymm6, %ymm0, %ymm2\n"
"	vpxor	%ymm1, %ymm0, %ymm7\n"
"	vpcmpeqw	%ymm3, %ymm2, %ymm2\n"
"	vpblendvb	%ymm2, %ymm7, %ymm0, %ymm0\n"
"	vpsubusw	%ymm5, %ymm0, %ymm2\n"
"	vpxor	%ymm0, %ymm1, %ymm7\n"
"	vpcmpeqw	%ymm3, %ymm2, %ymm2\n"
"	vpblendvb	%ymm2, %ymm7, %ymm0, %ymm0\n"
"	vpsubusw	%ymm4, %ymm0, %ymm2\n"
"	vpxor	%ymm0, %ymm1, %ymm1\n"
"	vpcmpeqw	%ymm3, %ymm2, %ymm2\n"
"	vpblendvb	%ymm2, %ymm1, %ymm0, %ymm0\n"
"	vmovdqa	%ymm0, (%rcx,%rax)\n"
"	addq	$32, %rax\n"
".myL97:\n"
"	vmovdqa	(%rcx,%rax), %ymm0\n"
"	vmovdqa	(%rdx,%rax), %ymm1\n"
"	vpsubusw	%ymm6, %ymm0, %ymm2\n"
"	vpxor	%ymm1, %ymm0, %ymm7\n"
"	vpcmpeqw	%ymm3, %ymm2, %ymm2\n"
"	vpblendvb	%ymm2, %ymm7, %ymm0, %ymm0\n"
"	vpsubusw	%ymm5, %ymm0, %ymm2\n"
"	vpxor	%ymm0, %ymm1, %ymm7\n"
"	vpcmpeqw	%ymm3, %ymm2, %ymm2\n"
"	vpblendvb	%ymm2, %ymm7, %ymm0, %ymm0\n"
"	vpsubusw	%ymm4, %ymm0, %ymm2\n"
"	vpxor	%ymm0, %ymm1, %ymm1\n"
"	vpcmpeqw	%ymm3, %ymm2, %ymm2\n"
"	vpblendvb	%ymm2, %ymm1, %ymm0, %ymm0\n"
"	vmovdqa	%ymm0, (%rcx,%rax)\n"
"	addq	$32, %rax\n"
"	cmpq	%rsi, %rax\n"
"	je	.myL104\n"
".myL85:\n"
"	vmovdqa	(%rcx,%rax), %ymm0\n"
"	vmovdqa	(%rdx,%rax), %ymm1\n"
"	leaq	32(%rax), %rdi\n"
"	vpsubusw	%ymm6, %ymm0, %ymm2\n"
"	vpxor	%ymm1, %ymm0, %ymm7\n"
"	vpcmpeqw	%ymm3, %ymm2, %ymm2\n"
"	vpblendvb	%ymm2, %ymm7, %ymm0, %ymm0\n"
"	vpsubusw	%ymm5, %ymm0, %ymm2\n"
"	vpxor	%ymm0, %ymm1, %ymm7\n"
"	vpcmpeqw	%ymm3, %ymm2, %ymm2\n"
"	vpblendvb	%ymm2, %ymm7, %ymm0, %ymm0\n"
"	vpsubusw	%ymm4, %ymm0, %ymm2\n"
"	vpxor	%ymm0, %ymm1, %ymm1\n"
"	vpcmpeqw	%ymm3, %ymm2, %ymm2\n"
"	vpblendvb	%ymm2, %ymm1, %ymm0, %ymm0\n"
"	vmovdqa	%ymm0, (%rcx,%rax)\n"
"	vmovdqa	32(%rcx,%rax), %ymm0\n"
"	vmovdqa	32(%rdx,%rax), %ymm1\n"
"	vpsubusw	%ymm6, %ymm0, %ymm2\n"
"	vpxor	%ymm1, %ymm0, %ymm7\n"
"	vpcmpeqw	%ymm3, %ymm2, %ymm2\n"
"	vpblendvb	%ymm2, %ymm7, %ymm0, %ymm0\n"
"	vpsubusw	%ymm5, %ymm0, %ymm2\n"
"	vpxor	%ymm0, %ymm1, %ymm7\n"
"	vpcmpeqw	%ymm3, %ymm2, %ymm2\n"
"	vpblendvb	%ymm2, %ymm7, %ymm0, %ymm0\n"
"	vpsubusw	%ymm4, %ymm0, %ymm2\n"
"	vpxor	%ymm0, %ymm1, %ymm1\n"
"	vpcmpeqw	%ymm3, %ymm2, %ymm2\n"
"	vpblendvb	%ymm2, %ymm1, %ymm0, %ymm0\n"
"	vmovdqa	%ymm0, 32(%rcx,%rax)\n"
"	vmovdqa	64(%rcx,%rax), %ymm0\n"
"	vmovdqa	64(%rdx,%rax), %ymm1\n"
"	vpsubusw	%ymm6, %ymm0, %ymm2\n"
"	vpxor	%ymm1, %ymm0, %ymm7\n"
"	vpcmpeqw	%ymm3, %ymm2, %ymm2\n"
"	vpblendvb	%ymm2, %ymm7, %ymm0, %ymm0\n"
"	vpsubusw	%ymm5, %ymm0, %ymm2\n"
"	vpxor	%ymm0, %ymm1, %ymm7\n"
"	vpcmpeqw	%ymm3, %ymm2, %ymm2\n"
"	vpblendvb	%ymm2, %ymm7, %ymm0, %ymm0\n"
"	vpsubusw	%ymm4, %ymm0, %ymm2\n"
"	vpxor	%ymm0, %ymm1, %ymm1\n"
"	vpcmpeqw	%ymm3, %ymm2, %ymm2\n"
"	vpblendvb	%ymm2, %ymm1, %ymm0, %ymm0\n"
"	vmovdqa	%ymm0, 64(%rcx,%rax)\n"
"	vmovdqa	64(%rcx,%rdi), %ymm0\n"
"	vmovdqa	64(%rdx,%rdi), %ymm1\n"
"	leaq	96(%rdi), %rax\n"
"	vpsubusw	%ymm6, %ymm0, %ymm2\n"
"	vpxor	%ymm1, %ymm0, %ymm7\n"
"	vpcmpeqw	%ymm3, %ymm2, %ymm2\n"
"	vpblendvb	%ymm2, %ymm7, %ymm0, %ymm0\n"
"	vpsubusw	%ymm5, %ymm0, %ymm2\n"
"	vpxor	%ymm0, %ymm1, %ymm7\n"
"	vpcmpeqw	%ymm3, %ymm2, %ymm2\n"
"	vpblendvb	%ymm2, %ymm7, %ymm0, %ymm0\n"
"	vpsubusw	%ymm4, %ymm0, %ymm2\n"
"	vpxor	%ymm0, %ymm1, %ymm1\n"
"	vpcmpeqw	%ymm3, %ymm2, %ymm2\n"
"	vpblendvb	%ymm2, %ymm1, %ymm0, %ymm0\n"
"	vmovdqa	%ymm0, 64(%rcx,%rdi)\n"
"	cmpq	%rsi, %rax\n"
"	jne	.myL85\n"
".myL104:\n"
"	vzeroupper\n"
".myL103:\n"
"	ret\n"
"	.cfi_endproc\n"
".myLFE9901:\n"
"	.size	_Z2uptttii, .-_Z2uptttii\n"
);

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	int k;
	cin >> n >> k;
	Loop (i,0,n)
		cin >> ab[i].first >> ab[i].second;
	Loop (i,0,k)
		cin >> q[i];
	mt19937_64 rd(time(0));
	shuffle(ab, ab+N, rd);
	ll ans = 0;
	for (int l0 = 0; l0 < N; l0 += S0) {
		int r0 = min(N, l0+S0);
		vector<int> vec = {0};
		Loop (i,l0,r0) {
			vec.push_back(ab[i].first);
			vec.push_back(ab[i].second);
		}
		sort(vec.begin(), vec.end());
		vec.resize(unique(vec.begin(), vec.end()) - vec.begin());
		Loop (i,l0,r0) {
			sa[i] = lower_bound(vec.begin(), vec.end(), ab[i].first) - vec.begin();
			sb[i] = lower_bound(vec.begin(), vec.end(), ab[i].second) - vec.begin();
			sb[i] ^= sa[i];
		}
		Loop (i,0,k)
			sq[i] = upper_bound(vec.begin(), vec.end(), q[i]) - vec.begin() - 1;
		for (int l1 = l0; l1 < r0; l1 += S1) {
			int r1 = min(r0, l1+S1);
			for (int i = 0; i < k; i += 3)
				up(sq[i+0], sq[i+1], sq[i+2], l1/S1, r1/S1);
		}
		Loop (i,l0,r0)
			ans += vec[sa[i]];
	}
	cout << ans << '\n';
}

Subtask #1
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 3048 KB Output is correct
2 Correct 30 ms 3052 KB Output is correct
3 Correct 29 ms 3072 KB Output is correct
4 Correct 28 ms 3052 KB Output is correct
5 Correct 27 ms 3084 KB Output is correct
6 Correct 29 ms 3064 KB Output is correct
7 Correct 30 ms 3048 KB Output is correct
8 Correct 27 ms 3072 KB Output is correct
9 Correct 28 ms 3156 KB Output is correct
10 Correct 28 ms 3072 KB Output is correct
11 Correct 30 ms 3052 KB Output is correct
12 Correct 27 ms 3052 KB Output is correct
13 Correct 28 ms 3164 KB Output is correct

Subtask #2
31.0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 3048 KB Output is correct
2 Correct 30 ms 3052 KB Output is correct
3 Correct 29 ms 3072 KB Output is correct
4 Correct 28 ms 3052 KB Output is correct
5 Correct 27 ms 3084 KB Output is correct
6 Correct 29 ms 3064 KB Output is correct
7 Correct 30 ms 3048 KB Output is correct
8 Correct 27 ms 3072 KB Output is correct
9 Correct 28 ms 3156 KB Output is correct
10 Correct 28 ms 3072 KB Output is correct
11 Correct 30 ms 3052 KB Output is correct
12 Correct 27 ms 3052 KB Output is correct
13 Correct 28 ms 3164 KB Output is correct
14 Correct 163 ms 3212 KB Output is correct
15 Correct 293 ms 3144 KB Output is correct
16 Correct 453 ms 3328 KB Output is correct
17 Correct 583 ms 3396 KB Output is correct
18 Correct 606 ms 3400 KB Output is correct
19 Correct 581 ms 3380 KB Output is correct
20 Correct 623 ms 3284 KB Output is correct
21 Correct 574 ms 3408 KB Output is correct
22 Correct 590 ms 3384 KB Output is correct
23 Correct 592 ms 3280 KB Output is correct
24 Correct 584 ms 3392 KB Output is correct
25 Correct 619 ms 3284 KB Output is correct
26 Correct 569 ms 3296 KB Output is correct
27 Correct 599 ms 3388 KB Output is correct
28 Correct 583 ms 3412 KB Output is correct
29 Correct 587 ms 3292 KB Output is correct

Subtask #3
0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 3048 KB Output is correct
2 Correct 30 ms 3052 KB Output is correct
3 Correct 29 ms 3072 KB Output is correct
4 Correct 28 ms 3052 KB Output is correct
5 Correct 27 ms 3084 KB Output is correct
6 Correct 29 ms 3064 KB Output is correct
7 Correct 30 ms 3048 KB Output is correct
8 Correct 27 ms 3072 KB Output is correct
9 Correct 28 ms 3156 KB Output is correct
10 Correct 28 ms 3072 KB Output is correct
11 Correct 30 ms 3052 KB Output is correct
12 Correct 27 ms 3052 KB Output is correct
13 Correct 28 ms 3164 KB Output is correct
14 Correct 163 ms 3212 KB Output is correct
15 Correct 293 ms 3144 KB Output is correct
16 Correct 453 ms 3328 KB Output is correct
17 Correct 583 ms 3396 KB Output is correct
18 Correct 606 ms 3400 KB Output is correct
19 Correct 581 ms 3380 KB Output is correct
20 Correct 623 ms 3284 KB Output is correct
21 Correct 574 ms 3408 KB Output is correct
22 Correct 590 ms 3384 KB Output is correct
23 Correct 592 ms 3280 KB Output is correct
24 Correct 584 ms 3392 KB Output is correct
25 Correct 619 ms 3284 KB Output is correct
26 Correct 569 ms 3296 KB Output is correct
27 Correct 599 ms 3388 KB Output is correct
28 Correct 583 ms 3412 KB Output is correct
29 Correct 587 ms 3292 KB Output is correct
30 Incorrect 2766 ms 4204 KB Output isn't correct
31 Halted 0 ms 0 KB -