#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 = 200'032;
const int S0 = 32767;
const int S1 = 2048;
pii ab[N];
unsigned short sa[N], sb[N];
int q[N];
unsigned short sq[N];
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];
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, 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 |
2 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 |
2 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 |
692 KB |
Output is correct |
| 15 |
Correct |
46 ms |
956 KB |
Output is correct |
| 16 |
Correct |
83 ms |
1224 KB |
Output is correct |
| 17 |
Correct |
145 ms |
1360 KB |
Output is correct |
| 18 |
Correct |
134 ms |
1312 KB |
Output is correct |
| 19 |
Correct |
137 ms |
1364 KB |
Output is correct |
| 20 |
Correct |
137 ms |
1344 KB |
Output is correct |
| 21 |
Correct |
136 ms |
1428 KB |
Output is correct |
| 22 |
Correct |
135 ms |
1368 KB |
Output is correct |
| 23 |
Correct |
135 ms |
1300 KB |
Output is correct |
| 24 |
Correct |
132 ms |
1340 KB |
Output is correct |
| 25 |
Correct |
141 ms |
1392 KB |
Output is correct |
| 26 |
Correct |
110 ms |
1368 KB |
Output is correct |
| 27 |
Correct |
141 ms |
1380 KB |
Output is correct |
| 28 |
Correct |
127 ms |
1368 KB |
Output is correct |
| 29 |
Correct |
135 ms |
1348 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 |
2 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 |
692 KB |
Output is correct |
| 15 |
Correct |
46 ms |
956 KB |
Output is correct |
| 16 |
Correct |
83 ms |
1224 KB |
Output is correct |
| 17 |
Correct |
145 ms |
1360 KB |
Output is correct |
| 18 |
Correct |
134 ms |
1312 KB |
Output is correct |
| 19 |
Correct |
137 ms |
1364 KB |
Output is correct |
| 20 |
Correct |
137 ms |
1344 KB |
Output is correct |
| 21 |
Correct |
136 ms |
1428 KB |
Output is correct |
| 22 |
Correct |
135 ms |
1368 KB |
Output is correct |
| 23 |
Correct |
135 ms |
1300 KB |
Output is correct |
| 24 |
Correct |
132 ms |
1340 KB |
Output is correct |
| 25 |
Correct |
141 ms |
1392 KB |
Output is correct |
| 26 |
Correct |
110 ms |
1368 KB |
Output is correct |
| 27 |
Correct |
141 ms |
1380 KB |
Output is correct |
| 28 |
Correct |
127 ms |
1368 KB |
Output is correct |
| 29 |
Correct |
135 ms |
1348 KB |
Output is correct |
| 30 |
Correct |
168 ms |
1768 KB |
Output is correct |
| 31 |
Correct |
739 ms |
2416 KB |
Output is correct |
| 32 |
Correct |
1436 ms |
3140 KB |
Output is correct |
| 33 |
Correct |
2832 ms |
4412 KB |
Output is correct |
| 34 |
Correct |
19 ms |
1492 KB |
Output is correct |
| 35 |
Correct |
2826 ms |
4204 KB |
Output is correct |
| 36 |
Correct |
2844 ms |
4408 KB |
Output is correct |
| 37 |
Correct |
2842 ms |
4216 KB |
Output is correct |
| 38 |
Correct |
2908 ms |
4336 KB |
Output is correct |
| 39 |
Execution timed out |
3002 ms |
4328 KB |
Time limit exceeded |
| 40 |
Halted |
0 ms |
0 KB |
- |
