#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
#include <string>
#include <bitset>
#include <map>
#include <set>
#include <tuple>
#include <string.h>
#include <math.h>
#include <random>
#include <functional>
#include <assert.h>
#include <math.h>
#define all(x) (x).begin(), (x).end()
#define xx first
#define yy second
using namespace std;
using i64 = long long int;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;
class Mapping
{
public:
void init(const vector<i64>& raw, int base = 0)
{
start = base;
arr = raw;
sort(arr.begin(), arr.end());
arr.erase(unique(arr.begin(), arr.end()), arr.end());
for (int i = 0; i < arr.size(); i++)
idx[arr[i]] = base + i;
}
int get_idx(i64 k)
{
return idx[k];
}
i64 get_value(int idx)
{
return arr[idx - start];
}
private:
int start;
vector<i64> arr;
map<i64, int> idx;
};
class FenwickTree
{
public:
FenwickTree(int k)
{
data.resize(k);
}
i64 sum(int n)
{
i64 ans = 0;
while (n > 0)
{
ans += data[n];
n -= (n & -n);
}
return ans;
}
void add(int n, i64 num)
{
while (n < data.size())
{
data[n] += num;
n += (n & -n);
}
}
private:
vector<i64> data;
};
struct Edge
{
Edge() = default;
Edge(int start, int end, int cost)
: s(start), e(end), c(cost) {}
int s, e, c;
};
vector<Edge> edges;
int parent[200005];
int find(int x)
{
if (parent[x] == x)
return x;
return parent[x] = find(parent[x]);
}
void merge(int x, int y)
{
x = find(x);
y = find(y);
parent[x] = y;
}
struct Events
{
//l ~ r 영역(l에 +1, r에 -1)
vector<ii> area;
// xpos, idx
vector<ii> pos;
};
void buildGraph(Mapping& mapping, vector<Events>& events)
{
FenwickTree cover(1000005);
FenwickTree points(1000005);
for (auto& es : events)
{
sort(all(es.pos));
for (auto& area : es.area)
{
cover.add(mapping.get_idx(area.xx), 1);
cover.add(mapping.get_idx(area.yy), -1);
if (area.xx < area.yy)
{
points.add(mapping.get_idx(area.xx), 1);
points.add(mapping.get_idx(area.yy - 1), 1);
}
else
{
points.add(mapping.get_idx(area.xx - 1), -1);
points.add(mapping.get_idx(area.yy), -1);
}
}
if (es.pos.empty())
continue;
for (int i = 0; i < es.pos.size() - 1; i++)
{
int sx = mapping.get_idx(es.pos[i].xx);
int ex = mapping.get_idx(es.pos[i + 1].xx);
if (cover.sum(sx) > 0 || cover.sum(ex) > 0)
continue;
if (points.sum(ex) - points.sum(sx - 1) > 0)
continue;
edges.emplace_back(es.pos[i].yy, es.pos[i + 1].yy,
es.pos[i + 1].xx - es.pos[i].xx);
}
}
}
int main()
{
int n, m, c;
scanf("%d %d %d", &n, &m, &c);
vector<ii> towns(n + 1);
vector<ii> st(m), ed(m);
vector<i64> xpos, ypos;
// y 좌표, (해당 y에서 event)
vector<Events> xEvents(5 * n);
vector<Events> yEvents(5 * n);
for (int i = 1; i <= n; i++)
{
scanf("%d %d", &towns[i].xx, &towns[i].yy);
xpos.push_back(towns[i].xx);
ypos.push_back(towns[i].yy);
}
for (int i = 0; i < m; i++)
{
scanf("%d %d %d %d", &st[i].xx, &st[i].yy, &ed[i].xx, &ed[i].yy);
xpos.push_back(st[i].xx);
xpos.push_back(ed[i].xx);
xpos.push_back(ed[i].xx + 1);
ypos.push_back(st[i].yy);
ypos.push_back(ed[i].yy);
ypos.push_back(ed[i].yy + 1);
}
Mapping xMapping;
Mapping yMapping;
xMapping.init(xpos, 1);
yMapping.init(ypos, 1);
for (int i = 1; i <= n; i++)
{
xEvents[yMapping.get_idx(towns[i].yy)].pos.emplace_back(towns[i].xx, i);
yEvents[xMapping.get_idx(towns[i].xx)].pos.emplace_back(towns[i].yy, i);
}
for (int i = 0; i < m; i++)
{
xEvents[yMapping.get_idx(st[i].yy)].area.emplace_back(st[i].xx, ed[i].xx + 1);
xEvents[yMapping.get_idx(ed[i].yy + 1)].area.emplace_back(ed[i].xx + 1, st[i].xx);
yEvents[xMapping.get_idx(st[i].xx)].area.emplace_back(st[i].yy, ed[i].yy + 1);
yEvents[xMapping.get_idx(ed[i].xx + 1)].area.emplace_back(ed[i].yy + 1, st[i].yy);
}
buildGraph(xMapping, xEvents);
buildGraph(yMapping, yEvents);
sort(all(edges), [](const Edge& l, const Edge& r)
{
return l.c < r.c;
});
vector<int> used;
for (int i = 1; i <= n; i++)
parent[i] = i;
for (auto& e : edges)
{
if (find(e.s) == find(e.e))
continue;
merge(e.s, e.e);
used.push_back(e.c);
}
int minNeed = 0;
for (int i = 1; i <= n; i++)
{
if (find(i) != i)
continue;
minNeed++;
}
used.push_back(0); // sentry
sort(all(used));
vector<i64> usedSum(used.size());
for (int i = 1; i < used.size(); i++)
usedSum[i] = usedSum[i - 1] + used[i];
for (int i = 0; i < c; i++)
{
i64 b, h;
scanf("%lld %lld", &b, &h);
if (h < minNeed)
{
printf("-1\n");
continue;
}
// 이분 탐색으로, 코스트가 b이상인 맨 왼쪽 간선 찾는다.
// b이상인것 전부 제외하면 됨
int ignore = lower_bound(all(used), b) - used.begin();
int setup = used.size() - ignore;
int setupMax = h - minNeed;
setup = min(setup, setupMax);
ignore = used.size() - setup;
i64 total = usedSum[ignore - 1]
+ (minNeed + setup) * b;
printf("%lld\n", total);
}
return 0;
}
Compilation message
construction.cpp: In member function 'void Mapping::init(const std::vector<long long int>&, int)':
construction.cpp:38:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < arr.size(); i++)
~~^~~~~~~~~~~~
construction.cpp: In member function 'void FenwickTree::add(int, i64)':
construction.cpp:81:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (n < data.size())
~~^~~~~~~~~~~~~
construction.cpp: In function 'void buildGraph(Mapping&, std::vector<Events>&)':
construction.cpp:159:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < es.pos.size() - 1; i++)
~~^~~~~~~~~~~~~~~~~~~
construction.cpp: In function 'int main()':
construction.cpp:265:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 1; i < used.size(); i++)
~~^~~~~~~~~~~~~
construction.cpp:179:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d", &n, &m, &c);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
construction.cpp:191:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &towns[i].xx, &towns[i].yy);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
construction.cpp:198:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d %d", &st[i].xx, &st[i].yy, &ed[i].xx, &ed[i].yy);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
construction.cpp:271:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld %lld", &b, &h);
~~~~~^~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
96 ms |
22212 KB |
Output is correct |
| 2 |
Correct |
1264 ms |
142516 KB |
Output is correct |
| 3 |
Correct |
1213 ms |
145884 KB |
Output is correct |
| 4 |
Correct |
537 ms |
131508 KB |
Output is correct |
| 5 |
Correct |
1319 ms |
145368 KB |
Output is correct |
| 6 |
Correct |
1131 ms |
145804 KB |
Output is correct |
| 7 |
Correct |
336 ms |
130872 KB |
Output is correct |
| 8 |
Correct |
710 ms |
146676 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5077 ms |
260492 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1331 ms |
149276 KB |
Output is correct |
| 2 |
Correct |
1435 ms |
149060 KB |
Output is correct |
| 3 |
Correct |
1482 ms |
158288 KB |
Output is correct |
| 4 |
Correct |
673 ms |
140100 KB |
Output is correct |
| 5 |
Correct |
1444 ms |
163188 KB |
Output is correct |
| 6 |
Correct |
1684 ms |
163880 KB |
Output is correct |
| 7 |
Correct |
1500 ms |
160600 KB |
Output is correct |
| 8 |
Correct |
1453 ms |
159592 KB |
Output is correct |
| 9 |
Correct |
527 ms |
141680 KB |
Output is correct |
| 10 |
Correct |
1035 ms |
146920 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5047 ms |
260364 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
