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 < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;
typedef pair<double, double> pdd;
pdd in()
{
ll x, y;
cin >> x >> y;
return {x, y};
}
const int N = 200'010;
double a[N], b[N] = {1e30};
int len = 0;
void insert(pdd f)
{
a[len] = f.first;
b[len] = f.second;
++len;
}
/*__attribute__((optimize("Ofast,unroll-loops"),target("avx2,fma")))
double get_ans(double x, bool side)
{
#define MIN(x, y) ((x)>(y)?(y):(x))
double ans = 1e30;
if (side) {
Loop (i,1,len) {
double tmp = a[i]*x + b[i];
ans = MIN(ans, tmp);
}
} else {
LoopR (i,1,len) {
double tmp = a[i]*x + b[i];
ans = MIN(ans, tmp);
}
}
return ans;
#undef MIN
}*/
double get_ans(double x, bool side);
asm("\n"
" .p2align 4\n"
" .globl _Z7get_ansdb\n"
" .type _Z7get_ansdb, @function\n"
"_Z7get_ansdb:\n"
".myLFB9908:\n"
" .cfi_startproc\n"
" vmovsd %xmm0, %xmm0, %xmm1\n"
" movslq len(%rip), %rax\n"
" vmovsd a(%rip), %xmm0\n"
" leaq a(%rip), %rdx\n"
" vfmadd213sd b(%rip), %xmm1, %xmm0\n"
" leaq b(%rip), %rcx\n"
" testb %dil, %dil\n"
" je .myL8\n"
" cmpl $1, %eax\n"
" jle .myL107\n"
" movslq %eax, %r8\n"
" leaq -2(%r8), %rax\n"
" leaq -1(%r8), %r9\n"
" cmpq $2, %rax\n"
" jbe .myL22\n"
" movq %r9, %rsi\n"
" vbroadcastsd %xmm0, %ymm0\n"
" vbroadcastsd %xmm1, %ymm3\n"
" movl $8, %eax\n"
" shrq $2, %rsi\n"
" salq $5, %rsi\n"
" leaq 8(%rsi), %rdi\n"
" subq $32, %rsi\n"
" shrq $5, %rsi\n"
" addq $1, %rsi\n"
" andl $7, %esi\n"
" je .myL11\n"
" cmpq $1, %rsi\n"
" je .myL72\n"
" cmpq $2, %rsi\n"
" je .myL73\n"
" cmpq $3, %rsi\n"
" je .myL74\n"
" cmpq $4, %rsi\n"
" je .myL75\n"
" cmpq $5, %rsi\n"
" je .myL76\n"
" cmpq $6, %rsi\n"
" je .myL77\n"
" vmovupd 8+a(%rip), %ymm2\n"
" movl $40, %eax\n"
" vfmadd213pd 8+b(%rip), %ymm3, %ymm2\n"
" vminpd %ymm2, %ymm0, %ymm0\n"
".myL77:\n"
" vmovupd (%rdx,%rax), %ymm2\n"
" vfmadd213pd (%rcx,%rax), %ymm3, %ymm2\n"
" addq $32, %rax\n"
" vminpd %ymm2, %ymm0, %ymm0\n"
".myL76:\n"
" vmovupd (%rdx,%rax), %ymm2\n"
" vfmadd213pd (%rcx,%rax), %ymm3, %ymm2\n"
" addq $32, %rax\n"
" vminpd %ymm2, %ymm0, %ymm0\n"
".myL75:\n"
" vmovupd (%rdx,%rax), %ymm2\n"
" vfmadd213pd (%rcx,%rax), %ymm3, %ymm2\n"
" addq $32, %rax\n"
" vminpd %ymm2, %ymm0, %ymm0\n"
".myL74:\n"
" vmovupd (%rdx,%rax), %ymm2\n"
" vfmadd213pd (%rcx,%rax), %ymm3, %ymm2\n"
" addq $32, %rax\n"
" vminpd %ymm2, %ymm0, %ymm0\n"
".myL73:\n"
" vmovupd (%rdx,%rax), %ymm2\n"
" vfmadd213pd (%rcx,%rax), %ymm3, %ymm2\n"
" addq $32, %rax\n"
" vminpd %ymm2, %ymm0, %ymm0\n"
".myL72:\n"
" vmovupd (%rdx,%rax), %ymm2\n"
" vfmadd213pd (%rcx,%rax), %ymm3, %ymm2\n"
" addq $32, %rax\n"
" vminpd %ymm2, %ymm0, %ymm0\n"
" cmpq %rdi, %rax\n"
" je .myL102\n"
".myL11:\n"
" vmovupd (%rdx,%rax), %ymm2\n"
" vfmadd213pd (%rcx,%rax), %ymm3, %ymm2\n"
" vminpd %ymm2, %ymm0, %ymm0\n"
" vmovupd 32(%rdx,%rax), %ymm2\n"
" vfmadd213pd 32(%rcx,%rax), %ymm3, %ymm2\n"
" vminpd %ymm2, %ymm0, %ymm0\n"
" vmovupd 64(%rdx,%rax), %ymm2\n"
" vfmadd213pd 64(%rcx,%rax), %ymm3, %ymm2\n"
" vminpd %ymm2, %ymm0, %ymm0\n"
" vmovupd 96(%rdx,%rax), %ymm2\n"
" vfmadd213pd 96(%rcx,%rax), %ymm3, %ymm2\n"
" vminpd %ymm2, %ymm0, %ymm0\n"
" vmovupd 128(%rdx,%rax), %ymm2\n"
" vfmadd213pd 128(%rcx,%rax), %ymm3, %ymm2\n"
" vminpd %ymm2, %ymm0, %ymm0\n"
" vmovupd 160(%rdx,%rax), %ymm2\n"
" vfmadd213pd 160(%rcx,%rax), %ymm3, %ymm2\n"
" vminpd %ymm2, %ymm0, %ymm0\n"
" vmovupd 192(%rdx,%rax), %ymm2\n"
" vfmadd213pd 192(%rcx,%rax), %ymm3, %ymm2\n"
" vminpd %ymm2, %ymm0, %ymm0\n"
" vmovupd 224(%rdx,%rax), %ymm2\n"
" vfmadd213pd 224(%rcx,%rax), %ymm3, %ymm2\n"
" addq $256, %rax\n"
" vminpd %ymm2, %ymm0, %ymm0\n"
" cmpq %rdi, %rax\n"
" jne .myL11\n"
".myL102:\n"
" vextractf128 $0x1, %ymm0, %xmm2\n"
" movq %r9, %rdi\n"
" vminpd %xmm0, %xmm2, %xmm2\n"
" andq $-4, %rdi\n"
" leaq 1(%rdi), %rsi\n"
" vunpckhpd %xmm2, %xmm2, %xmm0\n"
" vminpd %xmm2, %xmm0, %xmm0\n"
" cmpq %r9, %rdi\n"
" je .myL111\n"
" vzeroupper\n"
".myL10:\n"
" movq %r8, %rax\n"
" subq %rdi, %rax\n"
" leaq -1(%rax), %r9\n"
" cmpq $2, %rax\n"
" je .myL14\n"
" vmovupd 8(%rcx,%rdi,8), %xmm7\n"
" vmovddup %xmm1, %xmm2\n"
" vmovddup %xmm0, %xmm0\n"
" movq %r9, %rax\n"
" vfmadd132pd 8(%rdx,%rdi,8), %xmm7, %xmm2\n"
" andq $-2, %rax\n"
" addq %rax, %rsi\n"
" vminpd %xmm2, %xmm0, %xmm0\n"
" vunpckhpd %xmm0, %xmm0, %xmm2\n"
" vminpd %xmm0, %xmm2, %xmm0\n"
" cmpq %rax, %r9\n"
" je .myL107\n"
".myL14:\n"
" vmovsd (%rcx,%rsi,8), %xmm5\n"
" vfmadd132sd (%rdx,%rsi,8), %xmm5, %xmm1\n"
" vminsd %xmm1, %xmm0, %xmm0\n"
" ret\n"
" .p2align 4,,10\n"
" .p2align 3\n"
".myL8:\n"
" leal -1(%rax), %esi\n"
" movslq %esi, %r8\n"
" testl %esi, %esi\n"
" jle .myL107\n"
" pushq %rbp\n"
" .cfi_def_cfa_offset 16\n"
" .cfi_offset 6, -16\n"
" movq %r8, %r11\n"
" movq %rsp, %rbp\n"
" .cfi_def_cfa_register 6\n"
" pushq %rbx\n"
" .cfi_offset 3, -24\n"
" cmpq $3, %r8\n"
" jle .myL23\n"
" movq %r8, %rbx\n"
" movslq %eax, %rsi\n"
" vbroadcastsd %xmm0, %ymm0\n"
" xorl %edi, %edi\n"
" shrq $2, %rbx\n"
" leaq -32(,%rsi,8), %r9\n"
" vbroadcastsd %xmm1, %ymm4\n"
" negq %rbx\n"
" leaq (%rdx,%r9), %r10\n"
" addq %rcx, %r9\n"
" salq $5, %rbx\n"
" movq %rbx, %rsi\n"
" negq %rsi\n"
" subq $32, %rsi\n"
" shrq $5, %rsi\n"
" addq $1, %rsi\n"
" andl $7, %esi\n"
" je .myL17\n"
" cmpq $1, %rsi\n"
" je .myL78\n"
" cmpq $2, %rsi\n"
" je .myL79\n"
" cmpq $3, %rsi\n"
" je .myL80\n"
" cmpq $4, %rsi\n"
" je .myL81\n"
" cmpq $5, %rsi\n"
" je .myL82\n"
" cmpq $6, %rsi\n"
" je .myL83\n"
" vpermpd $27, (%r10), %ymm2\n"
" vpermpd $27, (%r9), %ymm3\n"
" movq $-32, %rdi\n"
" vfmadd132pd %ymm4, %ymm3, %ymm2\n"
" vminpd %ymm2, %ymm0, %ymm0\n"
".myL83:\n"
" vpermpd $27, (%r10,%rdi), %ymm2\n"
" vpermpd $27, (%r9,%rdi), %ymm3\n"
" subq $32, %rdi\n"
" vfmadd132pd %ymm4, %ymm3, %ymm2\n"
" vminpd %ymm2, %ymm0, %ymm0\n"
".myL82:\n"
" vpermpd $27, (%r10,%rdi), %ymm2\n"
" vpermpd $27, (%r9,%rdi), %ymm3\n"
" subq $32, %rdi\n"
" vfmadd132pd %ymm4, %ymm3, %ymm2\n"
" vminpd %ymm2, %ymm0, %ymm0\n"
".myL81:\n"
" vpermpd $27, (%r10,%rdi), %ymm2\n"
" vpermpd $27, (%r9,%rdi), %ymm3\n"
" subq $32, %rdi\n"
" vfmadd132pd %ymm4, %ymm3, %ymm2\n"
" vminpd %ymm2, %ymm0, %ymm0\n"
".myL80:\n"
" vpermpd $27, (%r10,%rdi), %ymm2\n"
" vpermpd $27, (%r9,%rdi), %ymm3\n"
" subq $32, %rdi\n"
" vfmadd132pd %ymm4, %ymm3, %ymm2\n"
" vminpd %ymm2, %ymm0, %ymm0\n"
".myL79:\n"
" vpermpd $27, (%r10,%rdi), %ymm2\n"
" vpermpd $27, (%r9,%rdi), %ymm3\n"
" subq $32, %rdi\n"
" vfmadd132pd %ymm4, %ymm3, %ymm2\n"
" vminpd %ymm2, %ymm0, %ymm0\n"
".myL78:\n"
" vpermpd $27, (%r10,%rdi), %ymm2\n"
" vpermpd $27, (%r9,%rdi), %ymm3\n"
" subq $32, %rdi\n"
" vfmadd132pd %ymm4, %ymm3, %ymm2\n"
" vminpd %ymm2, %ymm0, %ymm0\n"
" cmpq %rdi, %rbx\n"
" je .myL103\n"
".myL17:\n"
" vpermpd $27, (%r9,%rdi), %ymm3\n"
" vpermpd $27, (%r10,%rdi), %ymm2\n"
" leaq -32(%rdi), %rsi\n"
" vfmadd132pd %ymm4, %ymm3, %ymm2\n"
" vpermpd $27, -32(%r9,%rdi), %ymm3\n"
" vminpd %ymm2, %ymm0, %ymm0\n"
" vpermpd $27, -32(%r10,%rdi), %ymm2\n"
" vfmadd132pd %ymm4, %ymm3, %ymm2\n"
" vpermpd $27, -64(%r9,%rdi), %ymm3\n"
" vminpd %ymm2, %ymm0, %ymm0\n"
" vpermpd $27, -64(%r10,%rdi), %ymm2\n"
" leaq -224(%rsi), %rdi\n"
" vfmadd132pd %ymm4, %ymm3, %ymm2\n"
" vpermpd $27, -64(%r9,%rsi), %ymm3\n"
" vminpd %ymm2, %ymm0, %ymm0\n"
" vpermpd $27, -64(%r10,%rsi), %ymm2\n"
" vfmadd132pd %ymm4, %ymm3, %ymm2\n"
" vpermpd $27, -96(%r9,%rsi), %ymm3\n"
" vminpd %ymm2, %ymm0, %ymm0\n"
" vpermpd $27, -96(%r10,%rsi), %ymm2\n"
" vfmadd132pd %ymm4, %ymm3, %ymm2\n"
" vpermpd $27, -128(%r9,%rsi), %ymm3\n"
" vminpd %ymm2, %ymm0, %ymm0\n"
" vpermpd $27, -128(%r10,%rsi), %ymm2\n"
" vfmadd132pd %ymm4, %ymm3, %ymm2\n"
" vpermpd $27, -160(%r9,%rsi), %ymm3\n"
" vminpd %ymm2, %ymm0, %ymm0\n"
" vpermpd $27, -160(%r10,%rsi), %ymm2\n"
" vfmadd132pd %ymm4, %ymm3, %ymm2\n"
" vpermpd $27, -192(%r9,%rsi), %ymm3\n"
" vminpd %ymm2, %ymm0, %ymm0\n"
" vpermpd $27, -192(%r10,%rsi), %ymm2\n"
" vfmadd132pd %ymm4, %ymm3, %ymm2\n"
" vminpd %ymm2, %ymm0, %ymm0\n"
" cmpq %rdi, %rbx\n"
" jne .myL17\n"
".myL103:\n"
" vextractf128 $0x1, %ymm0, %xmm2\n"
" movq %r8, %rsi\n"
" vminpd %xmm0, %xmm2, %xmm2\n"
" andq $-4, %rsi\n"
" subq %rsi, %r8\n"
" vunpckhpd %xmm2, %xmm2, %xmm0\n"
" vminpd %xmm2, %xmm0, %xmm0\n"
" cmpq %rsi, %r11\n"
" je .myL112\n"
" vzeroupper\n"
".myL16:\n"
" subq %rsi, %r11\n"
" cmpq $1, %r11\n"
" je .myL20\n"
" subq %rsi, %rax\n"
" vmovddup %xmm1, %xmm3\n"
" vmovddup %xmm0, %xmm0\n"
" vpermilpd $1, -16(%rdx,%rax,8), %xmm2\n"
" vpermilpd $1, -16(%rcx,%rax,8), %xmm4\n"
" movq %r11, %rax\n"
" andq $-2, %rax\n"
" vfmadd132pd %xmm3, %xmm4, %xmm2\n"
" subq %rax, %r8\n"
" vminpd %xmm2, %xmm0, %xmm0\n"
" vunpckhpd %xmm0, %xmm0, %xmm2\n"
" vminpd %xmm0, %xmm2, %xmm0\n"
" cmpq %rax, %r11\n"
" je .myL7\n"
".myL20:\n"
" vmovsd (%rcx,%r8,8), %xmm6\n"
" vfmadd132sd (%rdx,%r8,8), %xmm6, %xmm1\n"
" vminsd %xmm1, %xmm0, %xmm0\n"
".myL7:\n"
" movq -8(%rbp), %rbx\n"
" leave\n"
" .cfi_def_cfa 7, 8\n"
" ret\n"
" .p2align 4,,10\n"
" .p2align 3\n"
".myL107:\n"
" .cfi_restore 3\n"
" .cfi_restore 6\n"
" ret\n"
" .p2align 4,,10\n"
" .p2align 3\n"
".myL112:\n"
" .cfi_def_cfa 6, 16\n"
" .cfi_offset 3, -24\n"
" .cfi_offset 6, -16\n"
" vzeroupper\n"
" movq -8(%rbp), %rbx\n"
" leave\n"
" .cfi_def_cfa 7, 8\n"
" ret\n"
" .p2align 4,,10\n"
" .p2align 3\n"
".myL111:\n"
" .cfi_restore 3\n"
" .cfi_restore 6\n"
" vzeroupper\n"
" ret\n"
".myL22:\n"
" xorl %edi, %edi\n"
" movl $1, %esi\n"
" jmp .myL10\n"
".myL23:\n"
" .cfi_def_cfa 6, 16\n"
" .cfi_offset 3, -24\n"
" .cfi_offset 6, -16\n"
" xorl %esi, %esi\n"
" jmp .myL16\n"
" .cfi_endproc\n"
".myLFE9908:\n"
" .size _Z7get_ansdb, .-_Z7get_ansdb\n"
);
int main()
{
cin.tie(0) -> sync_with_stdio(false);
cout << fixed << setprecision(3);
int n;
cin >> n;
Loop (i,0,n) {
auto [x, r] = in();
r = sqrt(r);
r = min(r, get_ans(x, i&1));
cout << r*r << '\n';
insert({0.5/r, -x*0.5/r});
}
}
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
