#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+32];
int n;
void up(unsigned short, unsigned short, unsigned short, int, int);
asm(" .p2align 4\n.globl _Z2uptttii\n.type _Z2uptttii, @function\n_Z2uptttii:\n.myLFB9897:\n.cfi_startproc\nmovl %edx, %r11d\nmovslq %r8d, %r8\nmovslq %ecx, %rdx\ncmpq %rdx, %r8\njle .myL135\npushq %rbp\n.cfi_def_cfa_offset 16\n.cfi_offset 6, -16\nmovl %edi, %r9d\nmovq %r8, %rdi\nmovl %esi, %r10d\nsubq %rdx, %rdi\nleaq -1(%rdi), %rax\nmovq %rsp, %rbp\n.cfi_def_cfa_register 6\npushq %r15\npushq %r14\n.cfi_offset 15, -24\n.cfi_offset 14, -32\nmovq %rdx, %r14\npushq %r13\npushq %r12\npushq %rbx\n.cfi_offset 13, -40\n.cfi_offset 12, -48\n.cfi_offset 3, -56\ncmpq $14, %rax\njbe .myL114\nmovq %rdi, %r15\nleaq (%rdx,%rdx), %r12\nleaq sa(%rip), %rsi\nxorl %eax, %eax\nvmovd %r9d, %xmm6\nshrq $4, %r15\nvmovd %r10d, %xmm5\nvmovd %r11d, %xmm4\nsalq $5, %r15\nleaq sb(%rip), %rbx\nleaq (%rsi,%r12), %rcx\nleaq -32(%r15), %r13\nvpbroadcastw %xmm6, %ymm6\nvpxor %xmm3, %xmm3, %xmm3\naddq %rbx, %r12\nshrq $5, %r13\nvpbroadcastw %xmm5, %ymm5\nvpbroadcastw %xmm4, %ymm4\naddq $1, %r13\nandl $3, %r13d\nje .myL86\ncmpq $1, %r13\nje .myL125\ncmpq $2, %r13\nje .myL126\nvmovdqu (%rcx), %ymm0\nvmovdqu (%r12), %ymm1\nmovl $32, %eax\nvpsubusw %ymm6, %ymm0, %ymm2\nvpxor %ymm1, %ymm0, %ymm7\nvpcmpeqw %ymm3, %ymm2, %ymm2\nvpblendvb %ymm2, %ymm7, %ymm0, %ymm0\nvpsubusw %ymm5, %ymm0, %ymm2\nvpxor %ymm0, %ymm1, %ymm7\nvpcmpeqw %ymm3, %ymm2, %ymm2\nvpblendvb %ymm2, %ymm7, %ymm0, %ymm0\nvpsubusw %ymm4, %ymm0, %ymm2\nvpxor %ymm0, %ymm1, %ymm1\nvpcmpeqw %ymm3, %ymm2, %ymm2\nvpblendvb %ymm2, %ymm1, %ymm0, %ymm0\nvmovdqu %ymm0, (%rcx)\n.myL126:\nvmovdqu (%rcx,%rax), %ymm0\nvmovdqu (%r12,%rax), %ymm1\nvpsubusw %ymm6, %ymm0, %ymm2\nvpxor %ymm1, %ymm0, %ymm7\nvpcmpeqw %ymm3, %ymm2, %ymm2\nvpblendvb %ymm2, %ymm7, %ymm0, %ymm0\nvpsubusw %ymm5, %ymm0, %ymm2\nvpxor %ymm0, %ymm1, %ymm7\nvpcmpeqw %ymm3, %ymm2, %ymm2\nvpblendvb %ymm2, %ymm7, %ymm0, %ymm0\nvpsubusw %ymm4, %ymm0, %ymm2\nvpxor %ymm0, %ymm1, %ymm1\nvpcmpeqw %ymm3, %ymm2, %ymm2\nvpblendvb %ymm2, %ymm1, %ymm0, %ymm0\nvmovdqu %ymm0, (%rcx,%rax)\naddq $32, %rax\n.myL125:\nvmovdqu (%rcx,%rax), %ymm0\nvmovdqu (%r12,%rax), %ymm1\nvpsubusw %ymm6, %ymm0, %ymm2\nvpxor %ymm1, %ymm0, %ymm7\nvpcmpeqw %ymm3, %ymm2, %ymm2\nvpblendvb %ymm2, %ymm7, %ymm0, %ymm0\nvpsubusw %ymm5, %ymm0, %ymm2\nvpxor %ymm0, %ymm1, %ymm7\nvpcmpeqw %ymm3, %ymm2, %ymm2\nvpblendvb %ymm2, %ymm7, %ymm0, %ymm0\nvpsubusw %ymm4, %ymm0, %ymm2\nvpxor %ymm0, %ymm1, %ymm1\nvpcmpeqw %ymm3, %ymm2, %ymm2\nvpblendvb %ymm2, %ymm1, %ymm0, %ymm0\nvmovdqu %ymm0, (%rcx,%rax)\naddq $32, %rax\ncmpq %r15, %rax\nje .myL131\n.myL86:\nvmovdqu (%rcx,%rax), %ymm0\nvmovdqu (%r12,%rax), %ymm1\nleaq 32(%rax), %r13\nvpsubusw %ymm6, %ymm0, %ymm2\nvpxor %ymm1, %ymm0, %ymm7\nvpcmpeqw %ymm3, %ymm2, %ymm2\nvpblendvb %ymm2, %ymm7, %ymm0, %ymm0\nvpsubusw %ymm5, %ymm0, %ymm2\nvpxor %ymm0, %ymm1, %ymm7\nvpcmpeqw %ymm3, %ymm2, %ymm2\nvpblendvb %ymm2, %ymm7, %ymm0, %ymm0\nvpsubusw %ymm4, %ymm0, %ymm2\nvpxor %ymm0, %ymm1, %ymm1\nvpcmpeqw %ymm3, %ymm2, %ymm2\nvpblendvb %ymm2, %ymm1, %ymm0, %ymm0\nvmovdqu %ymm0, (%rcx,%rax)\nvmovdqu 32(%rcx,%rax), %ymm0\nvmovdqu 32(%r12,%rax), %ymm1\nvpsubusw %ymm6, %ymm0, %ymm2\nvpxor %ymm1, %ymm0, %ymm7\nvpcmpeqw %ymm3, %ymm2, %ymm2\nvpblendvb %ymm2, %ymm7, %ymm0, %ymm0\nvpsubusw %ymm5, %ymm0, %ymm2\nvpxor %ymm0, %ymm1, %ymm7\nvpcmpeqw %ymm3, %ymm2, %ymm2\nvpblendvb %ymm2, %ymm7, %ymm0, %ymm0\nvpsubusw %ymm4, %ymm0, %ymm2\nvpxor %ymm0, %ymm1, %ymm1\nvpcmpeqw %ymm3, %ymm2, %ymm2\nvpblendvb %ymm2, %ymm1, %ymm0, %ymm0\nvmovdqu %ymm0, 32(%rcx,%rax)\nvmovdqu 64(%rcx,%rax), %ymm0\nvmovdqu 64(%r12,%rax), %ymm1\nvpsubusw %ymm6, %ymm0, %ymm2\nvpxor %ymm1, %ymm0, %ymm7\nvpcmpeqw %ymm3, %ymm2, %ymm2\nvpblendvb %ymm2, %ymm7, %ymm0, %ymm0\nvpsubusw %ymm5, %ymm0, %ymm2\nvpxor %ymm0, %ymm1, %ymm7\nvpcmpeqw %ymm3, %ymm2, %ymm2\nvpblendvb %ymm2, %ymm7, %ymm0, %ymm0\nvpsubusw %ymm4, %ymm0, %ymm2\nvpxor %ymm0, %ymm1, %ymm1\nvpcmpeqw %ymm3, %ymm2, %ymm2\nvpblendvb %ymm2, %ymm1, %ymm0, %ymm0\nvmovdqu %ymm0, 64(%rcx,%rax)\nvmovdqu 64(%rcx,%r13), %ymm0\nleaq 96(%r13), %rax\nvmovdqu 64(%r12,%r13), %ymm1\nvpsubusw %ymm6, %ymm0, %ymm2\nvpxor %ymm1, %ymm0, %ymm7\nvpcmpeqw %ymm3, %ymm2, %ymm2\nvpblendvb %ymm2, %ymm7, %ymm0, %ymm0\nvpsubusw %ymm5, %ymm0, %ymm2\nvpxor %ymm0, %ymm1, %ymm7\nvpcmpeqw %ymm3, %ymm2, %ymm2\nvpblendvb %ymm2, %ymm7, %ymm0, %ymm0\nvpsubusw %ymm4, %ymm0, %ymm2\nvpxor %ymm0, %ymm1, %ymm1\nvpcmpeqw %ymm3, %ymm2, %ymm2\nvpblendvb %ymm2, %ymm1, %ymm0, %ymm0\nvmovdqu %ymm0, 64(%rcx,%r13)\ncmpq %r15, %rax\njne .myL86\n.myL131:\nmovq %rdi, %rax\nandq $-16, %rax\naddq %rax, %rdx\ncmpq %rax, %rdi\nje .myL139\nvzeroupper\n.myL85:\nsubq %rax, %rdi\nleaq -1(%rdi), %rcx\ncmpq $6, %rcx\njbe .myL90\nvmovd %r9d, %xmm3\nvpxor %xmm5, %xmm5, %xmm5\nvmovd %r10d, %xmm2\naddq %r14, %rax\nleaq (%rsi,%rax,2), %rcx\nvpbroadcastw %xmm3, %xmm3\nvmovdqu (%rbx,%rax,2), %xmm4\nmovq %rdi, %rax\nvmovdqu (%rcx), %xmm0\nvpbroadcastw %xmm2, %xmm2\nvmovd %r11d, %xmm1\nandq $-8, %rax\nvpbroadcastw %xmm1, %xmm1\naddq %rax, %rdx\nvpsubusw %xmm3, %xmm0, %xmm3\nvpxor %xmm4, %xmm0, %xmm6\nvpcmpeqw %xmm5, %xmm3, %xmm3\nvpblendvb %xmm3, %xmm6, %xmm0, %xmm0\nvpsubusw %xmm2, %xmm0, %xmm2\nvpxor %xmm0, %xmm4, %xmm3\nvpcmpeqw %xmm5, %xmm2, %xmm2\nvpblendvb %xmm2, %xmm3, %xmm0, %xmm0\nvpsubusw %xmm1, %xmm0, %xmm1\nvpxor %xmm0, %xmm4, %xmm4\nvpcmpeqw %xmm5, %xmm1, %xmm1\nvpblendvb %xmm1, %xmm4, %xmm0, %xmm0\nvmovdqu %xmm0, (%rcx)\ncmpq %rax, %rdi\nje .myL133\n.myL90:\nmovzwl (%rsi,%rdx,2), %eax\nmovzwl (%rbx,%rdx,2), %ecx\nleaq 1(%rdx), %rdi\nxorl %eax, %ecx\ncmpw %r9w, %ax\ncmovbe %ecx, %eax\nmovzwl (%rbx,%rdx,2), %ecx\nxorl %eax, %ecx\ncmpw %r10w, %ax\ncmovbe %ecx, %eax\nmovzwl (%rbx,%rdx,2), %ecx\nxorl %eax, %ecx\ncmpw %r11w, %ax\ncmovbe %ecx, %eax\nmovw %ax, (%rsi,%rdx,2)\ncmpq %rdi, %r8\njle .myL133\nmovzwl (%rsi,%rdi,2), %eax\nmovzwl (%rbx,%rdi,2), %ecx\nxorl %eax, %ecx\ncmpw %r9w, %ax\ncmovbe %ecx, %eax\nmovzwl (%rbx,%rdi,2), %ecx\nxorl %eax, %ecx\ncmpw %r10w, %ax\ncmovbe %ecx, %eax\nmovzwl (%rbx,%rdi,2), %ecx\nxorl %eax, %ecx\ncmpw %r11w, %ax\ncmovbe %ecx, %eax\nmovw %ax, (%rsi,%rdi,2)\nleaq 2(%rdx), %rdi\ncmpq %rdi, %r8\njle .myL133\nmovzwl (%rsi,%rdi,2), %eax\nmovzwl (%rbx,%rdi,2), %ecx\nxorl %eax, %ecx\ncmpw %r9w, %ax\ncmovbe %ecx, %eax\nmovzwl (%rbx,%rdi,2), %ecx\nxorl %eax, %ecx\ncmpw %r10w, %ax\ncmovbe %ecx, %eax\nmovzwl (%rbx,%rdi,2), %ecx\nxorl %eax, %ecx\ncmpw %r11w, %ax\ncmovbe %ecx, %eax\nmovw %ax, (%rsi,%rdi,2)\nleaq 3(%rdx), %rdi\ncmpq %rdi, %r8\njle .myL133\nmovzwl (%rsi,%rdi,2), %eax\nmovzwl (%rbx,%rdi,2), %ecx\nxorl %eax, %ecx\ncmpw %r9w, %ax\ncmovbe %ecx, %eax\nmovzwl (%rbx,%rdi,2), %ecx\nxorl %eax, %ecx\ncmpw %r10w, %ax\ncmovbe %ecx, %eax\nmovzwl (%rbx,%rdi,2), %ecx\nxorl %eax, %ecx\ncmpw %r11w, %ax\ncmovbe %ecx, %eax\nmovw %ax, (%rsi,%rdi,2)\nleaq 4(%rdx), %rdi\ncmpq %rdi, %r8\njle .myL133\nmovzwl (%rsi,%rdi,2), %eax\nmovzwl (%rbx,%rdi,2), %ecx\nxorl %eax, %ecx\ncmpw %r9w, %ax\ncmovbe %ecx, %eax\nmovzwl (%rbx,%rdi,2), %ecx\nxorl %eax, %ecx\ncmpw %r10w, %ax\ncmovbe %ecx, %eax\nmovzwl (%rbx,%rdi,2), %ecx\nxorl %eax, %ecx\ncmpw %r11w, %ax\ncmovbe %ecx, %eax\nmovw %ax, (%rsi,%rdi,2)\nleaq 5(%rdx), %rdi\ncmpq %rdi, %r8\njle .myL133\nmovzwl (%rsi,%rdi,2), %eax\nmovzwl (%rbx,%rdi,2), %ecx\nxorl %eax, %ecx\ncmpw %r9w, %ax\ncmovbe %ecx, %eax\nmovzwl (%rbx,%rdi,2), %ecx\nxorl %eax, %ecx\ncmpw %r10w, %ax\ncmovbe %ecx, %eax\nmovzwl (%rbx,%rdi,2), %ecx\nxorl %eax, %ecx\ncmpw %r11w, %ax\ncmovbe %ecx, %eax\naddq $6, %rdx\nmovw %ax, (%rsi,%rdi,2)\ncmpq %rdx, %r8\njle .myL133\nmovzwl (%rsi,%rdx,2), %eax\nmovzwl (%rbx,%rdx,2), %ecx\nmovl %eax, %edi\nxorl %ecx, %edi\ncmpw %r9w, %ax\ncmovbe %edi, %eax\nmovl %eax, %edi\nxorl %ecx, %edi\ncmpw %r10w, %ax\ncmovbe %edi, %eax\nxorl %eax, %ecx\ncmpw %r11w, %ax\ncmovbe %ecx, %eax\nmovw %ax, (%rsi,%rdx,2)\n.myL133:\npopq %rbx\npopq %r12\npopq %r13\npopq %r14\npopq %r15\npopq %rbp\n.cfi_def_cfa 7, 8\nret\n.p2align 4,,10\n.p2align 3\n.myL135:\n.cfi_restore 3\n.cfi_restore 6\n.cfi_restore 12\n.cfi_restore 13\n.cfi_restore 14\n.cfi_restore 15\nret\n.myL114:\n.cfi_def_cfa 6, 16\n.cfi_offset 3, -56\n.cfi_offset 6, -16\n.cfi_offset 12, -48\n.cfi_offset 13, -40\n.cfi_offset 14, -32\n.cfi_offset 15, -24\nxorl %eax, %eax\nleaq sa(%rip), %rsi\nleaq sb(%rip), %rbx\njmp .myL85\n.myL139:\nvzeroupper\njmp .myL133\n.cfi_endproc\n.myLFE9897:\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];
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, r1);
}
Loop (i,l0,r0)
ans += vec[sa[i]];
}
cout << ans << '\n';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
17 ms |
724 KB |
Output is correct |
15 |
Correct |
44 ms |
984 KB |
Output is correct |
16 |
Correct |
79 ms |
1204 KB |
Output is correct |
17 |
Correct |
132 ms |
1360 KB |
Output is correct |
18 |
Correct |
137 ms |
1376 KB |
Output is correct |
19 |
Correct |
134 ms |
1408 KB |
Output is correct |
20 |
Correct |
137 ms |
1292 KB |
Output is correct |
21 |
Correct |
128 ms |
1320 KB |
Output is correct |
22 |
Correct |
121 ms |
1368 KB |
Output is correct |
23 |
Correct |
121 ms |
1368 KB |
Output is correct |
24 |
Correct |
121 ms |
1368 KB |
Output is correct |
25 |
Correct |
129 ms |
1328 KB |
Output is correct |
26 |
Correct |
105 ms |
1332 KB |
Output is correct |
27 |
Correct |
131 ms |
1468 KB |
Output is correct |
28 |
Correct |
122 ms |
1356 KB |
Output is correct |
29 |
Correct |
133 ms |
1384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
17 ms |
724 KB |
Output is correct |
15 |
Correct |
44 ms |
984 KB |
Output is correct |
16 |
Correct |
79 ms |
1204 KB |
Output is correct |
17 |
Correct |
132 ms |
1360 KB |
Output is correct |
18 |
Correct |
137 ms |
1376 KB |
Output is correct |
19 |
Correct |
134 ms |
1408 KB |
Output is correct |
20 |
Correct |
137 ms |
1292 KB |
Output is correct |
21 |
Correct |
128 ms |
1320 KB |
Output is correct |
22 |
Correct |
121 ms |
1368 KB |
Output is correct |
23 |
Correct |
121 ms |
1368 KB |
Output is correct |
24 |
Correct |
121 ms |
1368 KB |
Output is correct |
25 |
Correct |
129 ms |
1328 KB |
Output is correct |
26 |
Correct |
105 ms |
1332 KB |
Output is correct |
27 |
Correct |
131 ms |
1468 KB |
Output is correct |
28 |
Correct |
122 ms |
1356 KB |
Output is correct |
29 |
Correct |
133 ms |
1384 KB |
Output is correct |
30 |
Correct |
168 ms |
1828 KB |
Output is correct |
31 |
Correct |
713 ms |
2476 KB |
Output is correct |
32 |
Correct |
1428 ms |
3148 KB |
Output is correct |
33 |
Correct |
2798 ms |
4324 KB |
Output is correct |
34 |
Correct |
19 ms |
1492 KB |
Output is correct |
35 |
Correct |
2826 ms |
4324 KB |
Output is correct |
36 |
Correct |
2834 ms |
4324 KB |
Output is correct |
37 |
Correct |
2912 ms |
4300 KB |
Output is correct |
38 |
Correct |
2987 ms |
4316 KB |
Output is correct |
39 |
Correct |
2780 ms |
4284 KB |
Output is correct |
40 |
Correct |
2672 ms |
4216 KB |
Output is correct |
41 |
Correct |
2802 ms |
4416 KB |
Output is correct |
42 |
Correct |
2744 ms |
4340 KB |
Output is correct |
43 |
Correct |
2601 ms |
4320 KB |
Output is correct |
44 |
Correct |
2595 ms |
4320 KB |
Output is correct |
45 |
Correct |
2626 ms |
4208 KB |
Output is correct |
46 |
Correct |
2630 ms |
4332 KB |
Output is correct |
47 |
Correct |
2613 ms |
4216 KB |
Output is correct |
48 |
Correct |
2695 ms |
4216 KB |
Output is correct |
49 |
Correct |
2699 ms |
4456 KB |
Output is correct |