Submission #389177

#TimeUTC-0UsernameProblemLanguageResultExecution timeMemory
3891772021-04-13 20:10:50couplefireRoad Construction (JOI21_road_construction)C++17
6 / 100
2893 ms48956 KiB
#include <bits/stdc++.h>
using namespace std;
#define MAXN 250000
#define INF 1000000000000000009ll
#define ll long long
int n, k;
vector<ll> ans;
set<pair<ll, ll>> st;
map<ll, vector<ll>> mp;
bool check(ll mid){
ans.clear();
st.clear();
for(auto &i : mp){
vector<ll> &v = i.second;
ll x = i.first;
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),x-(*it).second));
if((int)ans.size() > k) return 0;
it = next(it);
}
st.insert({y, x});
}
if(!mp.count(x-mid)) continue;
vector<ll> &tmp = mp[x-mid];
for(auto &y : tmp) st.erase({y, x-mid});
}
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...