| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 787328 |
2023-07-19T05:37:50 Z |
반딧불(#10031) |
도로 건설 사업 (JOI13_construction) |
C++17 |
|
0 ms |
0 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], y1[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], &y1[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], y1[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);
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];
}
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] + (n-ans+1)*a);
}
}
Compilation message
construction.cpp:32:26: error: 'int y1 [200002]' redeclared as different kind of entity
32 | int x1[200002], y1[200002], x2[200002], y2[200002];
| ^
In file included from /usr/include/features.h:461,
from /usr/include/x86_64-linux-gnu/c++/10/bits/os_defines.h:39,
from /usr/include/x86_64-linux-gnu/c++/10/bits/c++config.h:518,
from /usr/include/c++/10/cassert:43,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
from construction.cpp:1:
/usr/include/x86_64-linux-gnu/bits/mathcalls.h:221:1: note: previous declaration 'double y1(double)'
221 | __MATHCALL (y1,, (_Mdouble_));
| ^~~~~~~~~~
construction.cpp: In function 'void input()':
construction.cpp:41:43: warning: pointer to a function used in arithmetic [-Wpointer-arith]
41 | scanf("%d %d %d %d", &x1[i], &y1[i], &x2[i], &y2[i]);
| ^
construction.cpp:41:20: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'double (*)(double) noexcept' [-Wformat=]
41 | scanf("%d %d %d %d", &x1[i], &y1[i], &x2[i], &y2[i]);
| ~^ ~~~~~~
| | |
| int* double (*)(double) noexcept
construction.cpp: In function 'void makeEdges()':
construction.cpp:117:55: warning: pointer to a function used in arithmetic [-Wpointer-arith]
117 | vec.push_back(Query(-1, x1[i], x2[i], y1[i]));
| ^
construction.cpp:117:55: error: invalid conversion from 'double (*)(double) noexcept' to 'int' [-fpermissive]
117 | vec.push_back(Query(-1, x1[i], x2[i], y1[i]));
| ~~~~^
| |
| double (*)(double) noexcept
construction.cpp:81:39: note: initializing argument 4 of 'Query::Query(int, int, int, int)'
81 | Query(int type, int l, int r, int t): type(type), l(l), r(r), t(t){}
| ~~~~^
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], &y1[i], &x2[i], &y2[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
construction.cpp: In function 'void answerQuery()':
construction.cpp:178:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
178 | scanf("%lld %d", &a, &b);
| ~~~~~^~~~~~~~~~~~~~~~~~~
