# | 제출 시각UTC-0 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
721427 | Dan4Life | Building Bridges (CEOI17_building) | C++17 | 75 ms | 35132 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mxN = (int)1e5+10;
const int mxC = (int)1e6+10;
const int LINF = (int)1e12+10;
int n, m, x, h[mxN], w[mxN], dp[mxN];
struct Line{
int m, c;
Line(){ m=c=LINF; }
Line(int _m, int _c){ m = _m, c = _c;}
int operator()(int x){ return m*x+c; }
} seg[2*mxC+10];
void addLine(Line a, int p=0, int l=1, int r=mxC){
if(l==r){
if(seg[p](l)>a(l)) seg[p]=a;
return;
}
int mid = (l+r)>>1; int rp = p+2*(mid-l+1);
if(a.m > seg[p].m) swap(a,seg[p]);
if(a(mid) < seg[p](mid))
swap(a,seg[p]), addLine(a,p+1,l,mid);
else addLine(a,rp,mid+1,r);
}
int query(int x, int p=0, int l=1, int r=mxC){
if(l==r) return seg[p](x);
int mid = (l+r)>>1; int rp = p+2*(mid-l+1);
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |