| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 787333 |
2023-07-19T05:42:40 Z |
반딧불(#10031) |
도로 건설 사업 (JOI13_construction) |
C++17 |
|
20 ms |
1488 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void input();
void makeEdges();
void getMST();
void answerQuery();
int main(){
input();
makeEdges();
getMST();
answerQuery();
}
struct Point{
int x, y, idx;
Point(){}
Point(int x, int y): x(x), y(y){}
bool operator<(const Point &r)const{
if(y != r.y) return y<r.y;
return x<r.x;
}
};
int n, k, q;
Point arr[200002];
int x1[200002], y_1[200002], x2[200002], y2[200002];
void input(){
scanf("%d %d %d", &n, &k, &q);
for(int i=1; i<=n; i++){
scanf("%d %d", &arr[i].x, &arr[i].y);
arr[i].idx = i;
}
for(int i=1; i<=k; i++){
scanf("%d %d %d %d", &x1[i], &y_1[i], &x2[i], &y2[i]);
}
}
struct segTree{
ll tree[1<<21], lazy[1<<21];
void propagate(int i, int l, int r){
tree[i] += lazy[i] * (r-l+1);
if(l!=r) lazy[i*2] += lazy[i], lazy[i*2+1] += lazy[i];
lazy[i] = 0;
}
void update(int i, int l, int r, int s, int e, int v){
propagate(i, l, r);
if(r<s || e<l) return;
if(s<=l && r<=e){
lazy[i] += v;
propagate(i, l, r);
return;
}
int m = (l+r)>>1;
update(i*2, l, m, s, e, v);
update(i*2+1, m+1, r, s, e, v);
tree[i] = tree[i*2] + tree[i*2+1];
}
ll query(int i, int l, int r, int s, int e){
propagate(i, l, r);
if(r<s || e<l) return 0;
if(s<=l && r<=e) return tree[i];
int m = (l+r)>>1;
return query(i*2, l, m, s, e) + query(i*2+1, m+1, r, s, e);
}
} tree;
struct Query{
int type;
int l, r, t, pa, pb;
Query(){}
Query(int type, int l, int r, int t): type(type), l(l), r(r), t(t){}
bool operator<(const Query &nxt)const{
if(t != nxt.t) return t < nxt.t;
return type < nxt.type;
}
};
struct Edge{
int x, y; ll w;
Edge(){}
Edge(int x, int y, ll w): x(x), y(y), w(w){}
bool operator<(const Edge &r)const{
return w<r.w;
}
};
vector<Edge> edges;
void makeEdges(){
vector<Query> vec;
vector<Point> points (arr+1, arr+n+1);
vector<int> xCoord;
int L;
int done = 0;
while(1){
sort(points.begin(), points.end());
for(int i=0; i<n-1; i++){
if(points[i].y == points[i+1].y){
vec.push_back(Query(0, points[i].x, points[i+1].x, points[i].y));
vec.back().pa = points[i].idx;
vec.back().pb = points[i+1].idx;
}
}
for(int i=1; i<=k; i++){
vec.push_back(Query(-1, x1[i], x2[i], y_1[i]));
vec.push_back(Query( 1, x1[i], x2[i], y2[i]));
}
for(Query p: vec) xCoord.push_back(p.l), xCoord.push_back(p.r);
sort(xCoord.begin(), xCoord.end());
xCoord.erase(unique(xCoord.begin(), xCoord.end()), xCoord.end());
L = (int)xCoord.size();
for(Query &p: vec){
p.l = lower_bound(xCoord.begin(), xCoord.end(), p.l) - xCoord.begin();
p.r = lower_bound(xCoord.begin(), xCoord.end(), p.r) - xCoord.begin();
}
sort(vec.begin(), vec.end());
for(Query &p: vec){
if(p.type == 0){
ll v = tree.query(1, 0, L-1, p.l, p.r);
if(!v) edges.push_back(Edge(p.pa, p.pb, xCoord[p.r]-xCoord[p.l]));
}
else tree.update(1, 0, L-1, p.l, p.r, -p.type);
}
if(++done == 2) return;
for(Point &p: points) swap(p.x, p.y);
for(int i=1; i<=k; i++) swap(x1[i], y_1[i]), swap(x2[i], y2[i]);
xCoord.clear();
vec.clear();
}
}
struct unionFind{
int par[200002];
void init(int n){
for(int i=1; i<=n; i++) par[i] = i;
}
int find(int x){
if(x==par[x]) return x;
return par[x] = find(par[x]);
}
void merge(int x, int y){
x=find(x), y=find(y);
par[x] = y;
}
} dsu;
int l;
ll weight[200002];
ll sum[200002];
int MIN;
void getMST(){
dsu.init(n);
sort(edges.begin(), edges.end());
for(Edge p: edges){
if(dsu.find(p.x) == dsu.find(p.y)) continue;
dsu.merge(p.x, p.y);
weight[++l] = p.w;
}
MIN = n-l;
for(int i=1; i<=l; i++) sum[i] = sum[i-1] + weight[i];
#ifdef TEST
printf("%d roads: ", l);
for(int i=1; i<=l; i++) printf("%lld ", weight[i]);
puts("");
#endif
}
void answerQuery(){
while(q--){
ll a; int b;
scanf("%lld %d", &a, &b);
if(b < MIN){
puts("-1");
continue;
}
b -= MIN;
int L = max(l-b+1, 1), R = l, ans = l+1;
while(L<=R){
int M=(L+R)/2;
if(weight[M] > a) ans = M, R = M-1;
else L = M+1;
}
printf("%lld\n", sum[ans-1] + ll(n-ans+1)*a);
}
}
Compilation message
construction.cpp: In function 'void input()':
construction.cpp:35:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
35 | scanf("%d %d %d", &n, &k, &q);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
construction.cpp:37:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
37 | scanf("%d %d", &arr[i].x, &arr[i].y);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
construction.cpp:41:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
41 | scanf("%d %d %d %d", &x1[i], &y_1[i], &x2[i], &y2[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
construction.cpp: In function 'void answerQuery()':
construction.cpp:185:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
185 | scanf("%lld %d", &a, &b);
| ~~~~~^~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
20 ms |
1488 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
20 ms |
1488 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
20 ms |
1488 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
20 ms |
1488 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
