| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 787343 |
2023-07-19T05:55:59 Z |
박상훈(#10032) |
도로 건설 사업 (JOI13_construction) |
C++17 |
|
17 ms |
1512 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr ll INF = 4e18;
struct Event{
int x, l, r, typ;
Event(){}
Event(int _x, int _l, int _r, int _t): x(_x), l(_l), r(_r), typ(_t) {}
bool operator < (const Event &E)const{
return tie(x, typ) < tie(E.x, E.typ);
}
};
struct Seg{
int tree[400400], sz;
set<pair<int, int>> st;
void init(int n){
sz = n;
fill(tree, tree+sz*2, 0);
st.clear();
}
void update(int l, int r, int x){
if (x < 0){
auto iter = st.lower_bound(pair<int, int>(l, -1));
while(iter!=st.end() && iter->first <= r){
// printf(" delete %d %d\n", iter->first, iter->second);
iter = st.erase(iter);
}
}
++r;
for (l+=sz, r+=sz;l<r;l>>=1, r>>=1){
if (l&1){
tree[l] += x;
l++;
}
if (r&1){
--r;
tree[r] += x;
}
}
}
void push(int p, int x){
auto iter = st.lower_bound(pair<int, int>(p, -1));
if (iter!=st.end() && iter->first==p) st.erase(iter);
st.emplace(p, x);
}
int query(int p){
int o = p;
int ret = 0;
for (p+=sz;p;p>>=1) ret += tree[p];
if (ret < 0) return ret;
p = o;
auto iter = st.lower_bound(pair<int, int>(p, -1));
if (iter!=st.end() && iter->first==p) return iter->second;
return 0;
}
}tree;
struct Edge{
int u, v, w;
Edge(){}
Edge(int _u, int _v, int _w): u(_u), v(_v), w(_w) {}
bool operator < (const Edge &E) const{
return w < E.w;
}
};
struct DSU{
int path[200200];
void init(int n){
for (int i=1;i<=n;i++) path[i] = i;
}
int find(int s){
if (s==path[s]) return s;
return path[s] = find(path[s]);
}
bool merge(int s, int v){
s = find(s), v = find(v);
if (s==v) return false;
path[v] = s;
return true;
}
}dsu;
int x[200200], y[200200], Px[200200], Py[200200], Qx[200200], Qy[200200];
vector<int> Cx, Cy;
vector<Edge> E;
ll f[200200];
int lim;
inline int dist(int i, int j){return abs(x[i] - x[j]) + abs(y[i] - y[j]);}
void compress(vector<int> &a){
sort(a.begin(), a.end());
a.erase(unique(a.begin(), a.end()), a.end());
}
int getidx(const vector<int> &a, int x){return lower_bound(a.begin(), a.end(), x) - a.begin();}
void sweep(int n, int m){
vector<Event> Q;
for (int i=1;i<=n;i++){
Q.emplace_back(x[i], getidx(Cy, y[i]), i, 1);
}
for (int i=1;i<=m;i++){
Q.emplace_back(Px[i], getidx(Cy, Py[i]), getidx(Cy, Qy[i]), 0);
Q.emplace_back(Qx[i], getidx(Cy, Py[i]), getidx(Cy, Qy[i]), 2);
}
tree.init(Cy.size() + 10);
sort(Q.begin(), Q.end());
for (auto &[_, l, r, typ]:Q){
// printf(" Event at x = %d: %d %d %d\n", _, l, r, typ);
if (typ==0){
tree.update(l, r, -1);
}
else if (typ==1){
int tmp = tree.query(l);
if (tmp > 0){
// printf(" ok %d %d %d\n", tmp, r, dist(tmp, r));
E.emplace_back(tmp, r, dist(tmp, r));
}
if (tmp >= 0){
tree.push(l, r);
}
}
else{
tree.update(l, r, 1);
}
}
// printf("ok done\n");
}
void run(int n){
dsu.init(n);
sort(E.begin(), E.end());
lim = n;
f[lim] = 0;
for (auto &[u, v, w]:E){
// printf(" ok edge %d %d %d\n", u, v, w);
if (dsu.merge(u, v)){
--lim;
f[lim] = f[lim+1] + w;
}
}
}
ll calc(int x, ll c){
return c*x + f[x];
}
ll query(int c, int mx){
int l = lim, r = mx;
ll ans = INF;
while(r-l>=4){
int m1 = (l+r)>>1;
int m2 = m1+1;
if (calc(m1, c) > calc(m2, c)) l = m1+1;
else r = m1-1;
}
for (int i=l;i<=r;i++) ans = min(ans, calc(i, c));
return ans==INF?-1:ans;
}
int main(){
int n, m, q;
scanf("%d %d %d", &n, &m, &q);
for (int i=1;i<=n;i++){
scanf("%d %d", x+i, y+i);
Cx.push_back(x[i]);
Cy.push_back(y[i]);
}
for (int i=1;i<=m;i++){
scanf("%d %d %d %d", Px+i, Py+i, Qx+i, Qy+i);
Cx.push_back(Px[i]);
Cx.push_back(Qx[i]);
Cy.push_back(Py[i]);
Cy.push_back(Qy[i]);
}
compress(Cx); compress(Cy);
sweep(n, m);
// flip xy
for (int i=1;i<=n;i++){
swap(x[i], y[i]);
}
for (int i=1;i<=m;i++){
swap(Px[i], Py[i]);
swap(Qx[i], Qy[i]);
}
swap(Cx, Cy);
sweep(n, m);
// get mst
run(n);
while(q--){
int b, h;
scanf("%d %d", &b, &h);
printf("%lld\n", query(b, h));
}
}
Compilation message
construction.cpp: In function 'int main()':
construction.cpp:185:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
185 | scanf("%d %d %d", &n, &m, &q);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
construction.cpp:188:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
188 | scanf("%d %d", x+i, y+i);
| ~~~~~^~~~~~~~~~~~~~~~~~~
construction.cpp:194:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
194 | scanf("%d %d %d %d", Px+i, Py+i, Qx+i, Qy+i);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
construction.cpp:223:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
223 | scanf("%d %d", &b, &h);
| ~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
1512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
1512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
1512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
1512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
