Submission #1165519

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
1165519	2025-03-12 02:14:12	windowwife	Building Bridges (CEOI17_building)	C++17	100 / 100	64 ms	12132 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
//fully dynamic convex hull trick/ linecontainer practice uwu :3
#include<bits/stdc++.h>
#define ll long long
#define task ""
using namespace std;
const int maxn = 1e5 + 4;
ll n, h[maxn], w[maxn], tw, dp[maxn];
struct Line
{
    bool type;
    long double i;
    ll x, y;
};
bool operator < (const Line& A, const Line& B)
{
    if (A.type || B.type) return A.i < B.i; //for binary search
    return A.x > B.x; //for the convex hull, change to < if asking for max
}
set<Line> hull;
bool has_prev (set<Line>::iterator it)
{
    return it != hull.begin();
}
bool has_next (set<Line>::iterator it)
{
    return it != hull.end() && next(it) != hull.end();
}
long double isect (set<Line>::iterator A, set<Line>::iterator B)
{
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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