| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 787393 |
2023-07-19T06:46:16 Z |
박영우(#10035) |
도로 건설 사업 (JOI13_construction) |
C++17 |
|
243 ms |
10532 KB |
#include <bits/stdc++.h>
#include <cassert>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define MAX 1001010
#define MAXS 20
#define INF 1000000000000000001
#define bb ' '
#define ln '\n'
#define Ln '\n'
vector<pair<int, pii>> hst, vst;
pii edges[MAX];
int W[MAX];
pii point[MAX];
int p[MAX];
int find(int a) {
if (p[a] == a) return a;
return p[a] = find(p[a]);
}
bool uni(int a, int b) {
a = find(a);
b = find(b);
if (a == b) return false;
p[a] = b;
return true;
}
int cv[MAX];
ll psum[MAX];
signed main() {
ios::sync_with_stdio(false), cin.tie(0);
int N, M, C;
cin >> N >> M >> C;
int i, a, b, c, d;
for (i = 1; i <= N; i++) cin >> point[i].first >> point[i].second;
for (i = 1; i <= M; i++) {
cin >> a >> b >> c >> d;
hst.emplace_back(b, pii(a, c));
hst.emplace_back(d, pii(a, c));
vst.emplace_back(a, pii(b, d));
vst.emplace_back(c, pii(b, d));
}
sort(hst.begin(), hst.end());
sort(vst.begin(), vst.end());
map<int, int> mp;
vector<int> v;
for (i = 1; i <= N; i++) v.push_back(i);
sort(v.begin(), v.end(), [&](int a, int b) {return point[a].first < point[b].first; });
int cnt = 0, ptr;
ptr = 0;
for (auto x : v) {
while (ptr < M * 2 && point[x].first >= vst[ptr].first) {
auto [l, r] = vst[ptr++].second;
while (1) {
auto it = mp.lower_bound(l);
if (it == mp.end()) break;
if (it->first > r) break;
mp.erase(it);
}
}
if (mp.find(point[x].second) != mp.end()) edges[++cnt] = pii(x, mp[point[x].second]);
mp[point[x].second] = x;
}
mp.clear();
sort(v.begin(), v.end(), [&](int a, int b) {return point[a].second < point[b].second; });
ptr = 0;
for (auto x : v) {
while (ptr < M * 2 && point[x].second >= hst[ptr].first) {
auto [l, r] = hst[ptr++].second;
while (1) {
auto it = mp.lower_bound(l);
if (it == mp.end()) break;
if (it->first > r) break;
mp.erase(it);
}
}
if (mp.find(point[x].first) != mp.end()) edges[++cnt] = pii(x, mp[point[x].first]);
mp[point[x].first] = x;
}
for (i = 1; i <= cnt; i++) W[i] = abs(point[edges[i].first].first - point[edges[i].second].first) + abs(point[edges[i].first].second - point[edges[i].second].second);
for (i = 1; i <= N; i++) p[i] = i;
vector<int> ev;
for (i = 1; i <= cnt; i++) ev.push_back(i);
sort(ev.begin(), ev.end(), [&](int a, int b) {return W[a] < W[b]; });
int ecnt = 0;
for (auto e : ev) if (uni(edges[e].first, edges[e].second)) cv[++ecnt] = W[e], psum[ecnt] = psum[ecnt - 1] + cv[ecnt];
int h;
while (C--) {
cin >> b >> h;
if (ecnt + h < N) {
cout << -1 << ln;
continue;
}
int ind = lower_bound(cv + 1, cv + ecnt + 1, b) - cv;
ll ans = 1ll * (N - ind + 1) * b;
ans += psum[ind - 1];
cout << ans << ln;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
768 KB |
Output is correct |
| 2 |
Incorrect |
243 ms |
10532 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
768 KB |
Output is correct |
| 2 |
Incorrect |
243 ms |
10532 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
768 KB |
Output is correct |
| 2 |
Incorrect |
243 ms |
10532 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
768 KB |
Output is correct |
| 2 |
Incorrect |
243 ms |
10532 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
