#include <stdio.h>
#include <algorithm>
#include <assert.h>
#include <bitset>
#include <cmath>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits.h>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <time.h>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#pragma warning(disable:4996)
#pragma comment(linker, "/STACK:336777216")
using namespace std;
#define mp make_pair
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define szz(x) ((int)(x).size())
#define rep(i, n) for(int i=0;i<n;i++)
#define all(x) (x).begin(), (x).end()
#define ldb ldouble
typedef tuple<int, int, int> t3;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair <ll, int> pli;
typedef pair <db, db> pdd;
int IT_MAX = 1 << 19;
const ll MOD = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
const db PI = acos(-1);
const db ERR = 1E-11;
class Node {
public:
int mx;
int v;
Node() {
mx = v = 0;
}
};
Node indt[1100000];
void propagate(int n) {
indt[2 * n].mx += indt[n].v;
indt[2 * n].v += indt[n].v;
indt[2 * n + 1].mx += indt[n].v;
indt[2 * n + 1].v += indt[n].v;
indt[n].v = 0;
}
void update(int st, int en, int S, int E, int n, int v) {
if (st > en) return;
if (st == S && en == E) {
indt[n].mx += v;
indt[n].v += v;
return;
}
propagate(n);
int M = (S + E) / 2;
update(st, min(M, en), S, M, 2 * n, v);
update(max(M + 1, st), en, M + 1, E, 2 * n + 1, v);
indt[n].mx = max(indt[2 * n].mx, indt[2 * n + 1].mx);
}
int getmx(int st, int en, int S, int E, int n) {
if (st > en) return 0;
if (st == S && en == E) return indt[n].mx;
propagate(n);
int M = (S + E) / 2;
return max(getmx(st, min(M, en), S, M, 2 * n), getmx(max(M + 1, st), en, M + 1, E, 2 * n + 1));
}
int in1[200050][2];
int in2[200050][4];
vector <int> Vx;
vector <int> Vy;
int u[200050];
vector <pair<pii, pii>> Vq;
vector <pair<ll, pii>> Ve;
vector <ll> Vv;
ll sum[200050];
int r[200050];
int root(int x) {
return (x == r[x]) ? x : (r[x] = root(r[x]));
}
int main() {
int N, M, C, i, j;
scanf("%d %d %d", &N, &M, &C);
for (i = 1; i <= N; i++) {
scanf("%d %d", &in1[i][0], &in1[i][1]);
}
for (i = 1; i <= M; i++) {
scanf("%d %d %d %d", &in2[i][0], &in2[i][1], &in2[i][2], &in2[i][3]);
Vx.push_back(in2[i][0]);
Vx.push_back(in2[i][2]);
Vy.push_back(in2[i][1]);
Vy.push_back(in2[i][3]);
}
sort(all(Vx));
sort(all(Vy));
Vx.erase(unique(all(Vx)), Vx.end());
Vy.erase(unique(all(Vy)), Vy.end());
for (i = 1; i <= N; i++) u[i] = i;
// X same
sort(u + 1, u + N + 1, [](int a, int b) {
return pii(in1[a][0], in1[a][1]) < pii(in1[b][0], in1[b][1]);
});
for (i = 1; i <= M; i++) {
Vq.emplace_back(pii(in2[i][0], 1), pii(in2[i][1], in2[i][3]));
Vq.emplace_back(pii(in2[i][2] + 1, -1), pii(in2[i][1], in2[i][3]));
}
sort(all(Vq));
for (i = 1, j = 0; i < N; i++) {
if (in1[u[i]][0] != in1[u[i + 1]][0]) continue;
while (j < Vq.size()) {
if (Vq[j].first.first > in1[u[i]][0]) break;
int p1 = lower_bound(all(Vy), Vq[j].second.first) - Vy.begin() + 1;
int p2 = lower_bound(all(Vy), Vq[j].second.second) - Vy.begin();
update(p1, p2, 1, IT_MAX, 1, Vq[j].first.second);
j++;
}
int p1 = lower_bound(all(Vy), in1[u[i]][1] + 1) - Vy.begin();
p1 = max(p1, 1);
int p2 = lower_bound(all(Vy), in1[u[i + 1]][1]) - Vy.begin();
if (getmx(p1, p2, 1, IT_MAX, 1) == 0) Ve.emplace_back(in1[u[i + 1]][1] - in1[u[i]][1], pii(u[i], u[i + 1]));
}
Vq.clear();
for (i = 1; i < 2 * IT_MAX; i++) indt[i] = Node();
// for (auto it : Ve) printf("(%d, %d)\n", it.second.first, it.second.second);
// printf("----------------------------------\n");
// Y same
sort(u + 1, u + N + 1, [](int a, int b) {
return pii(in1[a][1], in1[a][0]) < pii(in1[b][1], in1[b][0]);
});
for (i = 1; i <= M; i++) {
Vq.emplace_back(pii(in2[i][1], 1), pii(in2[i][0], in2[i][2]));
Vq.emplace_back(pii(in2[i][3] + 1, -1), pii(in2[i][0], in2[i][2]));
}
sort(all(Vq));
for (i = 1, j = 0; i < N; i++) {
if (in1[u[i]][1] != in1[u[i + 1]][1]) continue;
while (j < Vq.size()) {
if (Vq[j].first.first > in1[u[i]][1]) break;
int p1 = lower_bound(all(Vx), Vq[j].second.first) - Vx.begin() + 1;
int p2 = lower_bound(all(Vx), Vq[j].second.second) - Vx.begin();
update(p1, p2, 1, IT_MAX, 1, Vq[j].first.second);
j++;
}
int p1 = lower_bound(all(Vx), in1[u[i]][0] + 1) - Vx.begin();
p1 = max(p1, 1);
int p2 = lower_bound(all(Vx), in1[u[i + 1]][0]) - Vx.begin();
if (getmx(p1, p2, 1, IT_MAX, 1) == 0) Ve.emplace_back(in1[u[i + 1]][0] - in1[u[i]][0], pii(u[i], u[i + 1]));
}
Vq.clear();
for (i = 1; i < 2 * IT_MAX; i++) indt[i] = Node();
// for (auto it : Ve) printf("(%d, %d)\n", it.second.first, it.second.second);
sort(all(Ve));
Vv.push_back(0);
for (i = 1; i <= N; i++) r[i] = i;
for (auto it : Ve) {
if (root(it.second.first) == root(it.second.second)) continue;
Vv.push_back(it.first);
r[root(it.second.first)] = root(it.second.second);
}
while (Vv.size() < N) Vv.push_back(LL_INF);
for (i = 1; i <= N; i++) sum[i] = min(sum[i - 1] + Vv[i], LL_INF);
while (C--) {
int t1, t2;
scanf("%d %d", &t1, &t2);
int t3 = N - t2;
if (Vv[t3] == LL_INF) {
printf("-1\n");
continue;
}
int st = t3 + 1, en = N - 1, mi, rv = t3;
while (st <= en) {
mi = (st + en) / 2;
if (Vv[mi] < t1) {
rv = mi;
st = mi + 1;
}
else en = mi - 1;
}
printf("%lld\n", sum[rv] + (N - rv) * t1);
}
return 0;
}
Compilation message
construction.cpp:23:0: warning: ignoring #pragma warning [-Wunknown-pragmas]
#pragma warning(disable:4996)
^
construction.cpp:24:0: warning: ignoring #pragma comment [-Wunknown-pragmas]
#pragma comment(linker, "/STACK:336777216")
^
construction.cpp: In function 'int main()':
construction.cpp:143:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (j < Vq.size()) {
^
construction.cpp:174:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (j < Vq.size()) {
^
construction.cpp:200:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (Vv.size() < N) Vv.push_back(LL_INF);
^
construction.cpp:113:31: 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:115:41: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &in1[i][0], &in1[i][1]);
^
construction.cpp:118:71: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d %d", &in2[i][0], &in2[i][1], &in2[i][2], &in2[i][3]);
^
construction.cpp:205:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &t1, &t2);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
33 ms |
19056 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1689 ms |
34920 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
563 ms |
24680 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1869 ms |
34920 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
