이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#define X first
#define Y second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<ll,pll> plll;
ll n, m, q, par[200005];
pll a[200005];
vector<ll> xcp, ycp, wgt, sum;
vector<plll> edg;
struct world {
ll mx, idx[200005];
vector<ll> xl[200005];
vector<pll> c, swp[200005];
set<ll> exi;
void solve (vector<ll> &B) {
for(ll i=0;i<c.size();i++) {
xl[c[i].X].push_back(i);
mx = max(mx, c[i].X);
}
for(ll i=0;i<=mx;i++) {
for(auto &T : swp[i]) {
ll S = T.X, E = T.Y;
while(true) {
auto it = exi.lower_bound(S);
if(it == exi.end() || (*it) >= E) break;
exi.erase(it);
}
}
for(auto &T : xl[i]) {
if(exi.find(c[T].Y) != exi.end()) {
ll L = B[c[T].X] - B[c[idx[c[T].Y]].X];
edg.push_back({L, {T, idx[c[T].Y]}});
}
exi.insert(c[T].Y);
idx[c[T].Y] = T;
}
}
}
} w1, w2;
void compr (ll &X, vector<ll> &V) {
X = lower_bound(V.begin(), V.end(), X) - V.begin();
}
ll Find (ll X) {
if(par[X] == X) return X;
return par[X] = Find(par[X]);
}
int main()
{
scanf("%lld%lld%lld",&n,&m,&q);
for(ll i=1;i<=n;i++) {
scanf("%lld%lld",&a[i].X,&a[i].Y);
xcp.push_back(a[i].X);
ycp.push_back(a[i].Y);
}
sort(xcp.begin(), xcp.end());
xcp.erase(unique(xcp.begin(), xcp.end()), xcp.end());
sort(ycp.begin(), ycp.end());
ycp.erase(unique(ycp.begin(), ycp.end()), ycp.end());
for(ll i=1;i<=n;i++) {
compr(a[i].X, xcp);
compr(a[i].Y, ycp);
w1.c.push_back({a[i].X, a[i].Y});
w2.c.push_back({a[i].Y, a[i].X});
}
for(ll i=1;i<=m;i++) {
ll xs, xe, ys, ye;
scanf("%lld%lld%lld%lld",&xs,&ys,&xe,&ye);
xe++; ye++;
compr(xs, xcp); compr(xe, xcp);
compr(ys, ycp); compr(ye, ycp);
w1.swp[xs].push_back({ys, ye});
w2.swp[ys].push_back({xs, xe});
}
w1.solve(xcp);
w2.solve(ycp);
sort(edg.begin(), edg.end());
for(ll i=0;i<n;i++) par[i] = i;
for(auto &T : edg) {
ll A = T.Y.X, B = T.Y.Y, C = T.X;
A = Find(A); B = Find(B);
if(A != B) {
par[A] = B;
wgt.push_back(C);
}
}
sort(wgt.begin(), wgt.end());
for(auto &T : wgt) {
sum.push_back((sum.empty()?0:sum.back()) + T);
}
for(ll i=1;i<=q;i++) {
ll A, B;
scanf("%lld%lld",&A,&B); B--;
if(wgt.size() + B < n-1) {puts("-1"); continue;}
ll I = A; compr(I, wgt);
ll C = max(n-1-B, I);
printf("%lld\n",(C?sum[C-1]:0)+(n-C)*A);
}
}
컴파일 시 표준 에러 (stderr) 메시지
construction.cpp: In member function 'void world::solve(std::vector<long long int>&)':
construction.cpp:20:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(ll i=0;i<c.size();i++) {
^
construction.cpp: In function 'int main()':
construction.cpp:100:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(wgt.size() + B < n-1) {puts("-1"); continue;}
^
construction.cpp:56:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld%lld",&n,&m,&q);
^
construction.cpp:58:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld",&a[i].X,&a[i].Y);
^
construction.cpp:74:44: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld%lld%lld",&xs,&ys,&xe,&ye);
^
construction.cpp:99:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld",&A,&B); B--;
^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |