제출 #721427

#제출 시각UTC-0아이디문제언어결과실행 시간메모리
7214272023-04-10 21:54:46Dan4LifeBuilding Bridges (CEOI17_building)C++17
100 / 100
75 ms35132 KiB
#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);
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...