Submission #462057

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
462057	2021-08-10 07:29:37	prvocislo	Palembang Bridges (APIO15_bridge)	C++17	100 / 100	293 ms	14384 KiB

bridge

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 <iostream>
#include <vector>
#include <algorithm>
#include <set>
typedef long long ll;
using namespace std;
multiset<int, greater<int>> small; multiset<int> big;
ll sumsmall = 0, sumbig = 0;
void addsmall(int x) { small.insert(x), sumsmall += x; }
void popsmall() { sumsmall -= *small.begin(), small.erase(small.begin()); }
void addbig(int x) { big.insert(x), sumbig += x; }
void popbig() { sumbig -= *big.begin(), big.erase(big.begin()); }
void insert(int x)
{
    int m = (big.empty() ? -1 : *big.begin());
    if (x < m) addsmall(x);
    else addbig(x);
    if (small.size() > big.size()) addbig(*small.begin()), popsmall();
    if (small.size() + 1 < big.size()) addsmall(*big.begin()), popbig();
}
struct segment { int l, r; };
vector<ll> solve(const vector<segment>& s) // l a r budu 1 indexovane
{
    int n = s.size() - 1;
    small.clear(), big.clear(), sumsmall = 0, sumbig = 0;
    vector<ll>ans(n + 1, 0);
    for (int i = 1; i <= n; i++)
    {
        insert(s[i].l), insert(s[i].r);
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 8 / 8
• Subtask 2: 14 / 14
• Subtask 3: 9 / 9
• Subtask 4: 32 / 32
• Subtask 5: 37 / 37