Submission #426792

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
426792	2021-06-14 09:50:44	oleh1421	Building Bridges (CEOI17_building)	C++17	100 / 100	74 ms	7496 KiB

building

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
//#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
typedef pair<ll,ll> line;
const int N=1000010;
const ll mod=1000000007;
const ll inf=1e15;
ll h[N],w[N];
ll dp[N];
ll a[N],b[N];
line t[N];
ll f(line cur,ll x){
    return cur.first*x+cur.second;
}
int TOT=1;
int L[N],R[N];
void upd(int v,int l,int r,line cur){
//    cout<<v<<" "<<l<<" "<<r<<endl;
    ll mid=(l+r)/2;
    if (f(t[v],mid)>f(cur,mid)) swap(t[v],cur);
    if (cur.second==inf || l==r) return;
    if (f(t[v],l)>f(cur,l)){
        if (!L[v]) {
            L[v]=++TOT;
            t[TOT]={1e9,inf};
        }
        upd(L[v],l,mid,cur);
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40