#include<bits/stdc++.h>
using namespace std;
#define y1 y11
#define double long double
#define int long long
#define fi first
#define se second
#define pb push_back
//#define mp make_pair
#define foru(i, l, r) for(int i = l; i <= r; i++)
#define ford(i, r, l) for(int i = r; i >= l; i--)
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
const int N = 5e5 + 5;
const int oo = 1e18 + 7, mod = 1e9 + 7;
int n, m, c;
int x[N], y[N];
int a[N], b[N], ccc[N], d[N];
map<int, vector<ii>> mp1, mp2;
vector<pair<int, ii>> edges;
int cc[N], mx[N];
int tol[N];
int sz[N], root[N];
int rt(int x){
return (x == root[x] ? x : rt(root[x]));
}
bool merge(int x, int y){
x = rt(x), y = rt(y);
if(x == y) return 0;
if(sz[x] < sz[y]) swap(x, y);
sz[x] += sz[y];
root[y] = x;
return 1;
}
vector<int> vc1, vc2;
map<int, int> m1, m2;
int IT[N << 2], lazy[N << 2];
void laz(int id, int l, int r){
int t = lazy[id];
int mid = (l + r) >> 1;
lazy[id << 1] += t;
lazy[id << 1 | 1] += t;
IT[id << 1] += t * (mid - l + 1);
IT[id << 1 | 1] += t * (r - mid);
lazy[id] = 0;
}
void upd(int id, int l, int r, int L, int R, int val){
if(l > R || r < L) return;
if(l >= L && r <= R){
IT[id] += val * (r - l + 1);
lazy[id] += val;
return;
}
laz(id, l, r);
int mid = (l + r) >> 1;
upd(id << 1, l, mid, L, R, val);
upd(id << 1 | 1, mid + 1, r, L, R, val);
IT[id] = IT[id << 1] + IT[id << 1 | 1];
}
int get(int id, int l, int r, int L, int R){
if(l > R || r < L) return 0;
if(l >= L && r <= R) return IT[id];
laz(id, l, r);
int mid = (l + r) >> 1;
return get(id << 1, l, mid, L, R) + get(id << 1 | 1, mid + 1, r, L, R);
}
void process(){
cin >> n >> m >> c;
for(int i = 1; i <= n; i++){
cin >> x[i] >> y[i];
mp1[x[i]].pb({y[i], i});
mp2[y[i]].pb({x[i], i});
vc1.pb(x[i]), vc2.pb(y[i]);
}
vector<iii> events;
for(int i = 1; i <= m; i++){
cin >> a[i] >> b[i] >> ccc[i] >> d[i];
events.pb({{a[i], i}, 1});
events.pb({{ccc[i] + 1, i}, -1});
vc1.pb(a[i]);
vc2.pb(b[i]);
vc1.pb(ccc[i]);
vc2.pb(d[i]);
}
sort(vc1.begin(), vc1.end());
sort(vc2.begin(), vc2.end());
for(int i = 0; i < vc1.size(); i++) m1[vc1[i]] = i + 1;
for(int i = 0; i < vc2.size(); i++) m2[vc2[i]] = i + 1;
sort(events.begin(), events.end());
int itr = 0;
//return;
for(map<int, vector<ii>>::iterator it = mp1.begin(); it != mp1.end(); it++){
while(itr < events.size() && events[itr].fi.fi <= (*it).fi){
int ind = events[itr].fi.se;
upd(1, 1, vc2.size(), m2[b[ind]], m2[d[ind]], events[itr].se);
itr++;
}
vector<ii> temp = (*it).se;
sort(temp.begin(), temp.end());
for(int i = 1; i < temp.size(); i++){
//cout << (*it).fi << " " << temp[i - 1].fi << " " << temp[i].fi << "\n";
if(get(1, 1, vc2.size(), m2[temp[i - 1].fi], m2[temp[i].fi]) > 0) continue;
//cout << (*it).fi << " " << temp[i - 1].fi << " " << temp[i].fi << "\n";
//cout << "1 " << temp[i].se << " " << temp[i - 1].se << "\n";
edges.pb({temp[i].fi - temp[i - 1].fi, {temp[i].se, temp[i - 1].se}});
}
}
for(int i = 1; i <= (vc2.size() << 2); i++) IT[i] = lazy[i] = 0;
events.clear();
for(int i = 1; i <= m; i++){
events.pb({{b[i], i}, 1});
events.pb({{d[i] + 1, i}, -1});
}
sort(events.begin(), events.end());
itr = 0;
for(map<int, vector<ii>>::iterator it = mp2.begin(); it != mp2.end(); it++){
while(itr < events.size() && events[itr].fi.fi <= (*it).fi){
int ind = events[itr].fi.se;
upd(1, 1, vc1.size(), m1[a[ind]], m1[ccc[ind]], events[itr].se);
itr++;
}
vector<ii> temp = (*it).se;
sort(temp.begin(), temp.end());
for(int i = 1; i < temp.size(); i++){
//cout << (*it).fi << " " << temp[i - 1].fi << " " << temp[i].fi << "\n";
if(get(1, 1, vc1.size(), m1[temp[i - 1].fi], m1[temp[i].fi]) > 0) continue;
//cout << (*it).fi << " " << temp[i - 1].fi << " " << temp[i].fi << "\n";
//cout << "2 " << (*it).fi << " " << temp[i].se << " " << temp[i - 1].se << "\n";
edges.pb({temp[i].fi - temp[i - 1].fi, {temp[i].se, temp[i - 1].se}});
}
}
//return;
sort(edges.begin(), edges.end());
int cnt = n;
for(int i = 1; i <= n; i++){
sz[i] = 1, root[i] = i;
}
for(auto it : edges){
//cout << it.se.fi << " " << it.se.se << "\n";
//continue;
if(merge(it.se.fi, it.se.se)){
cnt--;
assert(cnt >= 0);
tol[cnt] = tol[cnt + 1] + it.fi;
//cout << cnt << " " << tol[cnt] << "\n";
}
}
//return;
for(int i = 0; i < cnt; i++) tol[i] = oo;
//for(int i = 0; i <= n; i++) cout << tol[i] << "\n";
for(int i = 1; i <= c; i++){
cin >> cc[i] >> mx[i];
int answer = oo;
for(int j = 0; j <= mx[i]; j++) answer = min(answer, cc[i] * j + tol[j]);
cout << (answer == oo ? -1 : answer) << "\n";
}
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int t = 1;
//cin >> t;
while(t--) process();
}
Compilation message
construction.cpp: In function 'void process()':
construction.cpp:107:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
107 | for(int i = 0; i < vc1.size(); i++) m1[vc1[i]] = i + 1;
| ~~^~~~~~~~~~~~
construction.cpp:108:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
108 | for(int i = 0; i < vc2.size(); i++) m2[vc2[i]] = i + 1;
| ~~^~~~~~~~~~~~
construction.cpp:113:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
113 | while(itr < events.size() && events[itr].fi.fi <= (*it).fi){
| ~~~~^~~~~~~~~~~~~~~
construction.cpp:120:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
120 | for(int i = 1; i < temp.size(); i++){
| ~~^~~~~~~~~~~~~
construction.cpp:128:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
128 | for(int i = 1; i <= (vc2.size() << 2); i++) IT[i] = lazy[i] = 0;
| ~~^~~~~~~~~~~~~~~~~~~~
construction.cpp:137:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
137 | while(itr < events.size() && events[itr].fi.fi <= (*it).fi){
| ~~~~^~~~~~~~~~~~~~~
construction.cpp:144:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
144 | for(int i = 1; i < temp.size(); i++){
| ~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
56 ms |
4768 KB |
Output is correct |
| 2 |
Correct |
740 ms |
68032 KB |
Output is correct |
| 3 |
Correct |
722 ms |
66732 KB |
Output is correct |
| 4 |
Correct |
461 ms |
45716 KB |
Output is correct |
| 5 |
Correct |
722 ms |
68996 KB |
Output is correct |
| 6 |
Correct |
674 ms |
66844 KB |
Output is correct |
| 7 |
Correct |
269 ms |
42544 KB |
Output is correct |
| 8 |
Correct |
411 ms |
69456 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
56 ms |
4768 KB |
Output is correct |
| 2 |
Correct |
740 ms |
68032 KB |
Output is correct |
| 3 |
Correct |
722 ms |
66732 KB |
Output is correct |
| 4 |
Correct |
461 ms |
45716 KB |
Output is correct |
| 5 |
Correct |
722 ms |
68996 KB |
Output is correct |
| 6 |
Correct |
674 ms |
66844 KB |
Output is correct |
| 7 |
Correct |
269 ms |
42544 KB |
Output is correct |
| 8 |
Correct |
411 ms |
69456 KB |
Output is correct |
| 9 |
Runtime error |
2269 ms |
262144 KB |
Execution killed with signal 11 |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
56 ms |
4768 KB |
Output is correct |
| 2 |
Correct |
740 ms |
68032 KB |
Output is correct |
| 3 |
Correct |
722 ms |
66732 KB |
Output is correct |
| 4 |
Correct |
461 ms |
45716 KB |
Output is correct |
| 5 |
Correct |
722 ms |
68996 KB |
Output is correct |
| 6 |
Correct |
674 ms |
66844 KB |
Output is correct |
| 7 |
Correct |
269 ms |
42544 KB |
Output is correct |
| 8 |
Correct |
411 ms |
69456 KB |
Output is correct |
| 9 |
Execution timed out |
5039 ms |
67928 KB |
Time limit exceeded |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
56 ms |
4768 KB |
Output is correct |
| 2 |
Correct |
740 ms |
68032 KB |
Output is correct |
| 3 |
Correct |
722 ms |
66732 KB |
Output is correct |
| 4 |
Correct |
461 ms |
45716 KB |
Output is correct |
| 5 |
Correct |
722 ms |
68996 KB |
Output is correct |
| 6 |
Correct |
674 ms |
66844 KB |
Output is correct |
| 7 |
Correct |
269 ms |
42544 KB |
Output is correct |
| 8 |
Correct |
411 ms |
69456 KB |
Output is correct |
| 9 |
Runtime error |
2269 ms |
262144 KB |
Execution killed with signal 11 |
| 10 |
Halted |
0 ms |
0 KB |
- |
