| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 644680 | ymm | Fortune Telling 2 (JOI14_fortune_telling2) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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;
int a[N], b[N];
short sa[N], sb[N];
int q[N];
short sq[N];
int n;
/*
__attribute__((optimize("O3,unroll-loops"),target("avx2")))
void up(short x, short y, short z, int l, int r)
{
Loop (i,l,r) {
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(short,short,short,int,int);
asm(".text\n.p2align4\n.globl_Z2upsssii\n.type_Z2upsssii,@function\n_Z2upsssii:\n.myLFB9703:\n.cfi_startproc\nmovl%edx,%r11d\nmovslq%r8d,%r8\nmovslq%ecx,%rdx\ncmpq%r8,%rdx\njge.myL73\npushq%rbp\n.cfi_def_cfa_offset16\n.cfi_offset6,-16\nmovl%edi,%r9d\nmovq%r8,%rdi\nmovl%esi,%r10d\nsubq%rdx,%rdi\nleaq-1(%rdi),%rax\nmovq%rsp,%rbp\n.cfi_def_cfa_register6\npushq%r15\npushq%r14\n.cfi_offset15,-24\n.cfi_offset14,-32\nmovq%rdx,%r14\npushq%r13\npushq%r12\npushq%rbx\n.cfi_offset13,-40\n.cfi_offset12,-48\n.cfi_offset3,-56\ncmpq$14,%rax\njbe.myL52\nmovq%rdi,%r15\nleaq(%rdx,%rdx),%r12\nleaqsa(%rip),%rsi\nxorl%eax,%eax\nvmovd%r9d,%xmm6\nshrq$4,%r15\nvmovd%r10d,%xmm5\nvmovd%r11d,%xmm4\nsalq$5,%r15\nleaqsb(%rip),%rbx\nleaq(%rsi,%r12),%rcx\nleaq-32(%r15),%r13\naddq%rbx,%r12\nvpbroadcastw%xmm6,%ymm6\nshrq$5,%r13\nvpbroadcastw%xmm5,%ymm5\nvpbroadcastw%xmm4,%ymm4\naddq$1,%r13\nandl$3,%r13d\nje.myL24\ncmpq$1,%r13\nje.myL63\ncmpq$2,%r13\nje.myL64\nvmovdqu(%rcx),%ymm1\nvmovdqu(%r12),%ymm0\nmovl$32,%eax\nvpcmpgtw%ymm6,%ymm1,%ymm3\nvpxor%ymm0,%ymm1,%ymm2\nvpblendvb%ymm3,%ymm1,%ymm2,%ymm2\nvpcmpgtw%ymm5,%ymm2,%ymm3\nvpxor%ymm2,%ymm0,%ymm1\nvpblendvb%ymm3,%ymm2,%ymm1,%ymm1\nvpcmpgtw%ymm4,%ymm1,%ymm2\nvpxor%ymm1,%ymm0,%ymm0\nvpblendvb%ymm2,%ymm1,%ymm0,%ymm0\nvmovdqu%ymm0,(%rcx)\n.myL64:\nvmovdqu(%rcx,%rax),%ymm1\nvmovdqu(%r12,%rax),%ymm0\nvpcmpgtw%ymm6,%ymm1,%ymm3\nvpxor%ymm0,%ymm1,%ymm2\nvpblendvb%ymm3,%ymm1,%ymm2,%ymm2\nvpcmpgtw%ymm5,%ymm2,%ymm3\nvpxor%ymm2,%ymm0,%ymm1\nvpblendvb%ymm3,%ymm2,%ymm1,%ymm1\nvpcmpgtw%ymm4,%ymm1,%ymm2\nvpxor%ymm1,%ymm0,%ymm0\nvpblendvb%ymm2,%ymm1,%ymm0,%ymm0\nvmovdqu%ymm0,(%rcx,%rax)\naddq$32,%rax\n.myL63:\nvmovdqu(%rcx,%rax),%ymm1\nvmovdqu(%r12,%rax),%ymm0\nvpcmpgtw%ymm6,%ymm1,%ymm3\nvpxor%ymm0,%ymm1,%ymm2\nvpblendvb%ymm3,%ymm1,%ymm2,%ymm2\nvpcmpgtw%ymm5,%ymm2,%ymm3\nvpxor%ymm2,%ymm0,%ymm1\nvpblendvb%ymm3,%ymm2,%ymm1,%ymm1\nvpcmpgtw%ymm4,%ymm1,%ymm2\nvpxor%ymm1,%ymm0,%ymm0\nvpblendvb%ymm2,%ymm1,%ymm0,%ymm0\nvmovdqu%ymm0,(%rcx,%rax)\naddq$32,%rax\ncmpq%r15,%rax\nje.myL69\n.myL24:\nvmovdqu(%rcx,%rax),%ymm1\nvmovdqu(%r12,%rax),%ymm0\nleaq32(%rax),%r13\nvpcmpgtw%ymm6,%ymm1,%ymm3\nvpxor%ymm0,%ymm1,%ymm2\nvpblendvb%ymm3,%ymm1,%ymm2,%ymm2\nvpcmpgtw%ymm5,%ymm2,%ymm3\nvpxor%ymm2,%ymm0,%ymm1\nvpblendvb%ymm3,%ymm2,%ymm1,%ymm1\nvpcmpgtw%ymm4,%ymm1,%ymm2\nvpxor%ymm1,%ymm0,%ymm0\nvpblendvb%ymm2,%ymm1,%ymm0,%ymm0\nvmovdqu32(%rcx,%rax),%ymm1\nvmovdqu%ymm0,(%rcx,%rax)\nvmovdqu32(%r12,%rax),%ymm0\nvpcmpgtw%ymm6,%ymm1,%ymm3\nvpxor%ymm0,%ymm1,%ymm2\nvpblendvb%ymm3,%ymm1,%ymm2,%ymm2\nvpcmpgtw%ymm5,%ymm2,%ymm3\nvpxor%ymm2,%ymm0,%ymm1\nvpblendvb%ymm3,%ymm2,%ymm1,%ymm1\nvpcmpgtw%ymm4,%ymm1,%ymm2\nvpxor%ymm1,%ymm0,%ymm0\nvpblendvb%ymm2,%ymm1,%ymm0,%ymm0\nvmovdqu64(%rcx,%rax),%ymm1\nvmovdqu%ymm0,32(%rcx,%rax)\nvmovdqu64(%r12,%rax),%ymm0\nvpcmpgtw%ymm6,%ymm1,%ymm3\nvpxor%ymm0,%ymm1,%ymm2\nvpblendvb%ymm3,%ymm1,%ymm2,%ymm2\nvpcmpgtw%ymm5,%ymm2,%ymm3\nvpxor%ymm2,%ymm0,%ymm1\nvpblendvb%ymm3,%ymm2,%ymm1,%ymm1\nvpcmpgtw%ymm4,%ymm1,%ymm2\nvpxor%ymm1,%ymm0,%ymm0\nvpblendvb%ymm2,%ymm1,%ymm0,%ymm0\nvmovdqu%ymm0,64(%rcx,%rax)\nvmovdqu64(%rcx,%r13),%ymm1\nleaq96(%r13),%rax\nvmovdqu64(%r12,%r13),%ymm0\nvpcmpgtw%ymm6,%ymm1,%ymm3\nvpxor%ymm0,%ymm1,%ymm2\nvpblendvb%ymm3,%ymm1,%ymm2,%ymm2\nvpcmpgtw%ymm5,%ymm2,%ymm3\nvpxor%ymm2,%ymm0,%ymm1\nvpblendvb%ymm3,%ymm2,%ymm1,%ymm1\nvpcmpgtw%ymm4,%ymm1,%ymm2\nvpxor%ymm1,%ymm0,%ymm0\nvpblendvb%ymm2,%ymm1,%ymm0,%ymm0\nvmovdqu%ymm0,64(%rcx,%r13)\ncmpq%r15,%rax\njne.myL24\n.myL69:\nmovq%rdi,%rax\nandq$-16,%rax\naddq%rax,%rdx\ncmpq%rax,%rdi\nje.myL77\nvzeroupper\n.myL23:\nsubq%rax,%rdi\nleaq-1(%rdi),%rcx\ncmpq$6,%rcx\njbe.myL28\nvmovd%r9d,%xmm1\nvmovd%r10d,%xmm4\nvmovd%r11d,%xmm2\naddq%r14,%rax\nleaq(%rsi,%rax,2),%rcx\nvpbroadcastw%xmm1,%xmm1\nvmovdqu(%rbx,%rax,2),%xmm0\nvpbroadcastw%xmm4,%xmm4\nvmovdqu(%rcx),%xmm5\nvpbroadcastw%xmm2,%xmm2\nmovq%rdi,%rax\nandq$-8,%rax\nvpcmpgtw%xmm1,%xmm5,%xmm1\nvpxor%xmm0,%xmm5,%xmm3\naddq%rax,%rdx\nvpblendvb%xmm1,%xmm5,%xmm3,%xmm3\nvpcmpgtw%xmm4,%xmm3,%xmm4\nvpxor%xmm3,%xmm0,%xmm1\nvpblendvb%xmm4,%xmm3,%xmm1,%xmm1\nvpcmpgtw%xmm2,%xmm1,%xmm2\nvpxor%xmm1,%xmm0,%xmm0\nvpblendvb%xmm2,%xmm1,%xmm0,%xmm0\nvmovdqu%xmm0,(%rcx)\ncmpq%rax,%rdi\nje.myL71\n.myL28:\nmovzwl(%rsi,%rdx,2),%eax\nmovzwl(%rbx,%rdx,2),%ecx\nleaq1(%rdx),%rdi\nxorl%eax,%ecx\ncmpw%r9w,%ax\ncmovle%ecx,%eax\nmovzwl(%rbx,%rdx,2),%ecx\nxorl%eax,%ecx\ncmpw%r10w,%ax\ncmovle%ecx,%eax\nmovzwl(%rbx,%rdx,2),%ecx\nxorl%eax,%ecx\ncmpw%r11w,%ax\ncmovle%ecx,%eax\nmovw%ax,(%rsi,%rdx,2)\ncmpq%rdi,%r8\njle.myL71\nmovzwl(%rsi,%rdi,2),%eax\nmovzwl(%rbx,%rdi,2),%ecx\nxorl%eax,%ecx\ncmpw%r9w,%ax\ncmovle%ecx,%eax\nmovzwl(%rbx,%rdi,2),%ecx\nxorl%eax,%ecx\ncmpw%r10w,%ax\ncmovle%ecx,%eax\nmovzwl(%rbx,%rdi,2),%ecx\nxorl%eax,%ecx\ncmpw%r11w,%ax\ncmovle%ecx,%eax\nmovw%ax,(%rsi,%rdi,2)\nleaq2(%rdx),%rdi\ncmpq%rdi,%r8\njle.myL71\nmovzwl(%rsi,%rdi,2),%eax\nmovzwl(%rbx,%rdi,2),%ecx\nxorl%eax,%ecx\ncmpw%r9w,%ax\ncmovle%ecx,%eax\nmovzwl(%rbx,%rdi,2),%ecx\nxorl%eax,%ecx\ncmpw%r10w,%ax\ncmovle%ecx,%eax\nmovzwl(%rbx,%rdi,2),%ecx\nxorl%eax,%ecx\ncmpw%r11w,%ax\ncmovle%ecx,%eax\nmovw%ax,(%rsi,%rdi,2)\nleaq3(%rdx),%rdi\ncmpq%r8,%rdi\njge.myL71\nmovzwl(%rsi,%rdi,2),%eax\nmovzwl(%rbx,%rdi,2),%ecx\nxorl%eax,%ecx\ncmpw%r9w,%ax\ncmovle%ecx,%eax\nmovzwl(%rbx,%rdi,2),%ecx\nxorl%eax,%ecx\ncmpw%r10w,%ax\ncmovle%ecx,%eax\nmovzwl(%rbx,%rdi,2),%ecx\nxorl%eax,%ecx\ncmpw%r11w,%ax\ncmovle%ecx,%eax\nmovw%ax,(%rsi,%rdi,2)\nleaq4(%rdx),%rdi\ncmpq%rdi,%r8\njle.myL71\nmovzwl(%rsi,%rdi,2),%eax\nmovzwl(%rbx,%rdi,2),%ecx\nxorl%eax,%ecx\ncmpw%r9w,%ax\ncmovle%ecx,%eax\nmovzwl(%rbx,%rdi,2),%ecx\nxorl%eax,%ecx\ncmpw%r10w,%ax\ncmovle%ecx,%eax\nmovzwl(%rbx,%rdi,2),%ecx\nxorl%eax,%ecx\ncmpw%r11w,%ax\ncmovle%ecx,%eax\nmovw%ax,(%rsi,%rdi,2)\nleaq5(%rdx),%rdi\ncmpq%rdi,%r8\njle.myL71\nmovzwl(%rsi,%rdi,2),%eax\nmovzwl(%rbx,%rdi,2),%ecx\nxorl%eax,%ecx\ncmpw%r9w,%ax\ncmovle%ecx,%eax\nmovzwl(%rbx,%rdi,2),%ecx\nxorl%eax,%ecx\ncmpw%r10w,%ax\ncmovle%ecx,%eax\nmovzwl(%rbx,%rdi,2),%ecx\nxorl%eax,%ecx\ncmpw%r11w,%ax\ncmovle%ecx,%eax\naddq$6,%rdx\nmovw%ax,(%rsi,%rdi,2)\ncmpq%rdx,%r8\njle.myL71\nmovzwl(%rsi,%rdx,2),%eax\nmovzwl(%rbx,%rdx,2),%ecx\nmovl%eax,%edi\nxorl%ecx,%edi\ncmpw%r9w,%ax\ncmovle%edi,%eax\nmovl%eax,%edi\nxorl%ecx,%edi\ncmpw%r10w,%ax\ncmovle%edi,%eax\nxorl%eax,%ecx\ncmpw%r11w,%ax\ncmovle%ecx,%eax\nmovw%ax,(%rsi,%rdx,2)\n.myL71:\npopq%rbx\npopq%r12\npopq%r13\npopq%r14\npopq%r15\npopq%rbp\n.cfi_def_cfa7,8\nret\n.p2align4,,10\n.p2align3\n.myL73:\n.cfi_restore3\n.cfi_restore6\n.cfi_restore12\n.cfi_restore13\n.cfi_restore14\n.cfi_restore15\nret\n.myL52:\n.cfi_def_cfa6,16\n.cfi_offset3,-56\n.cfi_offset6,-16\n.cfi_offset12,-48\n.cfi_offset13,-40\n.cfi_offset14,-32\n.cfi_offset15,-24\nxorl%eax,%eax\nleaqsa(%rip),%rsi\nleaqsb(%rip),%rbx\njmp.myL23\n.myL77:\nvzeroupper\njmp.myL71\n.cfi_endproc\n.myLFE9703:\n.size_Z2upsssii,.-_Z2upsssii\n");
int main()
{
cin.tie(0) -> sync_with_stdio(false);
int k;
cin >> n >> k;
Loop (i,0,n)
cin >> a[i] >> b[i];
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(a[i]);
vec.push_back(b[i]);
}
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(), a[i]) - vec.begin();
sb[i] = lower_bound(vec.begin(), vec.end(), b[i]) - 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(q[i+0], q[i+1], q[i+2], l1, r1);
}
Loop (i,l0,r0)
ans += vec[sa[i]];
}
cout << ans << '\n';
}