| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 791999 | I_Love_EliskaM_ | Aliens (IOI16_aliens) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<n;++i)
#define pb push_back
#define all(x) x.begin(), x.end()
#define pi pair<int,int>
#define f first
#define s second
using ll = long long;
#define int ll
const int inf=1e18;
int sq(int x) {
return x*x;
}
struct line {
int a,b;
int f(int x) {
return a*x+b;
}
line() {
a=0, b=inf;
}
line(int x, int y) {
a=x, b=y;
}
};
const int sz=1<<20;
struct sgt {
sgt *L, *R;
line ln;
sgt() {
L=R=NULL; ln=line();
}
sgt(line n) {
L=R=NULL; ln=n;
}
int it=0;
void add(int l, int r, line n) {
if (n.f(l)<=ln.f(l) && n.f(r)<=ln.f(r)) {
ln=n; return;
}
if (n.f(l)>=ln.f(l) && n.f(r)>=ln.f(r)) {
return;
}
if (r-l==1) return;
int m=(l+r)>>1;
if (!L) L=new sgt(ln);
if (!R) R=new sgt(ln);
L->add(l,m,n);
R->add(m,r,n);
}
void add(line n) {
it=0;
add(0,sz,n);
assert(it<=4*20);
}
int query(int l, int r, int x) {
if (r<=x || l>x) return inf;
int m=(l+r)>>1;
int f=ln.f(x);
int s=L?L->query(l,m,x):inf;
int t=R?R->query(m,r,x):inf;
return min({f,s,t});
}
int query(int x) {
return query(0,sz,x);
}
};