Submission #1167181

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
1167181	2025-03-15 13:42:28	spycoderyt	Harbingers (CEOI09_harbingers)	C++20	100 / 100	94 ms	24648 KiB

harbingers

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
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 3e5 + 5;
struct Line
{
    int a, b;
    int operator()(int x) { return a * x + b; };
} lines[N];
vector<pair<int, int>> A[N];
int dis[N], prep[N], v[N], dp[N];
int sz = 1;
long double inter(Line x, Line y)
{
    return (long double)(x.b - y.b) / (long double)(y.a - x.a);
}
stack<tuple<int, int, Line>> his;
void add(Line nw)
{
    int pos = sz, l = 1, r = sz - 1;
    while (l <= r)
    {
        int mid = (l + r) / 2;
        if (inter(lines[mid - 1], nw) >= inter(lines[mid], nw))
        {
            pos = mid;
            r = mid - 1;
        }
        else
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 100 / 100