Submission #389180

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
389180	2021-04-13 20:39:16	couplefire	Road Construction (JOI21_road_construction)	C++17	100 / 100	3688 ms	36820 KiB

road_construction

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 INF 1000000000000000009ll
#define ll long long
int n, k;
vector<ll> ans;
set<pair<ll, ll>> st;
map<ll, vector<ll>> mp;
queue<pair<ll, ll>> active;
bool check(ll mid){
    ans.clear();
    st.clear();
    active = queue<pair<ll, ll>>();
    for(auto &i : mp){
        vector<ll> &v = i.second;
        ll x = i.first;
        while(!active.empty() && active.front().second < x-mid) st.erase(active.front()), active.pop();
        for(auto &y : v){
            auto it = st.lower_bound({y-mid, -INF});
            while(it != st.end() && (*it).first <= y+mid){
                ans.push_back(max(abs((*it).first-y),abs(x-(*it).second)));
                if((int)ans.size() > k) return 0;
                it = next(it);
            }
            st.insert({y, x});
            active.push({y, x});
        }
    }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 5 / 5
• Subtask 2: 6 / 6
• Subtask 3: 7 / 7
• Subtask 4: 20 / 20
• Subtask 5: 27 / 27
• Subtask 6: 35 / 35