#include <cstdio>
#include <vector>
#include <algorithm>
#include <utility>
using namespace std;
typedef pair<int,int> pi;
int n,m,c;
int x[200005], y[200005];
struct point{
int x,y,num;
};
bool cmp1(point a, point b){return a.x != b.x ? (a.x < b.x) : (a.y < b.y);}
bool cmp2(point a, point b){return a.y != b.y ? (a.y < b.y) : (a.x < b.x);}
struct edge_hori{
int sx, ex, y;
int s,e;
};
struct edge_vert{
int sy, ey, x;
int s,e;
};
struct kill_hori{
int y, sx, ex, dx;
};
struct kill_vert{
int x, sy, ey, dx;
};
bool cmp3(edge_hori a, edge_hori b){return a.y < b.y;}
bool cmp4(edge_vert a, edge_vert b){return a.x < b.x;}
bool cmp5(kill_hori a, kill_hori b){return a.y < b.y;}
bool cmp6(kill_vert a, kill_vert b){return a.x < b.x;}
struct node{
node(){
sum = 0, lazy = 0;
ls = rs = NULL;
}
long long sum, lazy;
node *ls, *rs;
}*root;
void lazydown(int ps, int pe, node *p){
if(!p->ls) p->ls = new node();
if(!p->rs) p->rs = new node();
if(p->lazy == 0) return;
p->ls->lazy += p->lazy;
p->rs->lazy += p->lazy;
int pm = (ps+pe)/2;
p->ls->sum += p->lazy * (pm - ps + 1);
p->rs->sum += p->lazy * (pe - pm);
p->lazy = 0;
}
void add(int s, int e, int x, int ps, int pe, node *p){
if(e < ps || pe < s) return;
if(s <= ps && pe <= e){
p->sum += (pe - ps + 1) * x;
p->lazy += x;
return;
}
lazydown(ps,pe,p);
int pm = (ps+pe)/2;
add(s,e,x,ps,pm,p->ls);
add(s,e,x,pm+1,pe,p->rs);
p->sum = p->ls->sum + p->rs->sum;
}
long long sum(int s, int e, int ps, int pe, node *p){
if(e < ps || pe < s) return 0;
if(s <= ps && pe <= e) return p->sum;
lazydown(ps,pe,p);
int pm = (ps+pe)/2;
return sum(s,e,ps,pm,p->ls) + sum(s,e,pm+1,pe,p->rs);
}
vector<edge_hori> eh;
vector<edge_vert> ev;
vector<kill_hori> kh;
vector<kill_vert> kv;
void initialize(){
point hor[200005];
point vert[200005];
scanf("%d %d %d",&n,&m,&c);
for (int i=0; i<n; i++) {
scanf("%d %d",&x[i],&y[i]);
}
for (int i=0; i<n; i++) {
hor[i] = {x[i],y[i],i};
vert[i] = {x[i],y[i],i};
}
sort(hor,hor+n,cmp2);
sort(vert,vert+n,cmp1);
for (int i=0; i<n-1; i++) {
if(hor[i].y == hor[i+1].y){
eh.push_back({hor[i].x,hor[i+1].x,hor[i].y,hor[i].num,hor[i+1].num});
}
}
for (int i=0; i<n-1; i++) {
if(vert[i].x == vert[i+1].x){
ev.push_back({vert[i].y,vert[i+1].y,vert[i].x,vert[i].num,vert[i+1].num});
}
}
for (int i=0; i<m; i++) {
int p,q,r,s;
scanf("%d %d %d %d",&p,&q,&r,&s);
kh.push_back({q,p,r,1});
kh.push_back({s+1,p,r,-1});
kv.push_back({p,q,s,1});
kv.push_back({r+1,q,s,-1});
}
sort(eh.begin(),eh.end(),cmp3);
sort(ev.begin(),ev.end(),cmp4);
sort(kh.begin(),kh.end(),cmp5);
sort(kv.begin(),kv.end(),cmp6);
}
struct edge{int s,e,x;};
bool cmp7(edge a, edge b){return a.x < b.x;}
vector<edge> ret_edge;
void graph_retrieval(){
root = new node();
int p1 = 0, p2 = 0;
while (p1 < eh.size() && p2 < kh.size()) {
if(eh[p1].y < kh[p2].y){
if(sum(eh[p1].sx,eh[p1].ex,0,1e9,root) == 0){
ret_edge.push_back({eh[p1].s,eh[p1].e,eh[p1].ex - eh[p1].sx});
}
p1++;
}
else{
add(kh[p2].sx,kh[p2].ex,kh[p2].dx,0,1e9,root);
p2++;
}
}
while (p1 < eh.size()) {
ret_edge.push_back({eh[p1].s,eh[p1].e,eh[p1].ex - eh[p1].sx});
p1++;
}
root = new node();
p1 = 0, p2 = 0;
while (p1 < ev.size() && p2 < kv.size()) {
if(ev[p1].x < kv[p2].x){
if(sum(ev[p1].sy,ev[p1].ey,0,1e9,root) == 0){
ret_edge.push_back({ev[p1].s,ev[p1].e,ev[p1].ey - ev[p1].sy});
}
p1++;
}
else{
add(kv[p2].sy,kv[p2].ey,kv[p2].dx,0,1e9,root);
p2++;
}
}
while (p1 < ev.size()) {
ret_edge.push_back({ev[p1].s,ev[p1].e,ev[p1].ey - ev[p1].sy});
p1++;
}
}
struct disj{
int pa[200005], r[200005];
void init(int n){
for(int i=0; i<=n; i++){
pa[i] = i;
}
}
int find(int x){
if(pa[x] == x) return x;
return pa[x] = find(pa[x]);
}
bool uni(int x, int y){
x = find(x);
y = find(y);
if(x == y) return 0;
if(r[x] < r[y]) pa[y] = x;
else pa[x] = y;
if(r[x] == r[y]) r[x]++;
return 1;
}
}disj;
vector<int> ret;
vector<long long> psum;
void tree_retrieval(){
disj.init(n);
sort(ret_edge.begin(),ret_edge.end(),cmp7);
for(edge i : ret_edge){
if(disj.uni(i.s,i.e)){
ret.push_back(i.x);
psum.push_back(i.x + (psum.empty() ? 0 : psum.back()));
}
}
}
inline long long get_sum(int x){
if(x == 0) return 0;
return psum[x-1];
}
void process_query(){
while (c--) {
int b,k;
scanf("%d %d",&b,&k);
k = min(k,n);
if(k + ret.size() < n) puts("-1");
else{
auto x = upper_bound(ret.begin(),ret.end(),b);
int cnt = (int)(x - ret.begin());
if(cnt + k < n){
printf("%lld\n",get_sum(n-k) + 1ll * b * k);
}
else{
printf("%lld\n",get_sum(cnt) + 1ll * (n - cnt) * b);
}
}
}
}
int main(){
initialize();
graph_retrieval();
tree_retrieval();
process_query();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
94 ms |
45980 KB |
Output is correct |
| 2 |
Memory limit exceeded |
697 ms |
262144 KB |
Memory limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Memory limit exceeded |
1065 ms |
262144 KB |
Memory limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1049 ms |
262060 KB |
Output is correct |
| 2 |
Memory limit exceeded |
689 ms |
262144 KB |
Memory limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Memory limit exceeded |
1077 ms |
262144 KB |
Memory limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
