| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 74842 | cubecube1000 | 도로 건설 사업 (JOI13_construction) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef unsigned long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
const int MAX=1<<18;
const ll INFLL=0x3f3f3f3f3f3f3f;
struct vill{
int x,y,idx;
};
vill v[MAX];
struct edge{
int x,y,d;
bool operator<(const edge &a)const{
return d<a.d;
}
};
struct area{int x1,y1,x2,y2;};
area h[MAX];
vector<int> ixcp,iycp,ex[MAX],ey[MAX],val2;
vector<edge> mst;
vector<pii> conn[MAX];
map<int,int> xcp,ycp;
multiset<int> pos;
vector<pii> ch;
vector<ll> val;
int chk[MAX],n,m,c,par[MAX];
ll cum;
int fnd(int x){
if(par[x]!=x) return par[x]=fnd(par[x]);
return x;
}
void uni(int x,int y){
x=fnd(x), y=fnd(y);
par[x]=y;
}
bool cmpx(vill a,vill b){
if(a.x!=b.x) return a.x<b.x;
return a.y<b.y;
}
bool cmpy(vill a,vill b){
if(a.y!=b.y) return a.y<b.y;
return a.x<b.x;
}
bool cmpidx(vill a,vill b){
return a.idx<b.idx;
}
int exist(int x,int y){
set<int>::iterator it=pos.lower_bound(x);
if(it==pos.end()) return false;
if(*it<=y) return true;
return false;
}
int main(){
scanf("%d%d%d",&n,&m,&c);
for(int i=0;i<n;i++){scanf("%d%d",&v[i].x,&v[i].y),v[i].idx=i;}
for(int i=0;i<m;i++){scanf("%d%d%d%d",&h[i].x1,&h[i].y1,&h[i].x2,&h[i].y2),h[i].x2++,h[i].y2++;}
for(int i=0;i<n;i++) {
if(xcp.find(h[i].x1)==xcp.end()) ixcp.push_back(h[i].x1), xcp[h[i].x1]=0;
if(xcp.find(h[i].x2)==xcp.end()) ixcp.push_back(h[i].x2), xcp[h[i].x2]=0;
if(ycp.find(h[i].y1)==ycp.end()) iycp.push_back(h[i].y1), ycp[h[i].y1]=0;
if(ycp.find(h[i].y2)==ycp.end()) iycp.push_back(h[i].y2), ycp[h[i].y2]=0;
}
sort(ixcp.begin(),ixcp.end());
sort(iycp.begin(),iycp.end());
for(int i=0;i<ixcp.size();i++) xcp[ixcp[i]]=i;
for(int i=0;i<iycp.size();i++) ycp[iycp[i]]=i;
for(int i=0;i<m;i++){
ex[xcp[h[i].x1]].push_back(i), ey[ycp[h[i].y1]].push_back(i);
ex[xcp[h[i].x2]].push_back(i), ey[ycp[h[i].y2]].push_back(i);
}
sort(v,v+n,cmpx);
for(int i=1,pt=0;i<n;i++){
if(v[i-1].x==v[i].x){
for(;ixcp[pt]<=v[i].x&&pt<ixcp.size();pt++){
for(int j=0;j<ex[pt].size();j++) {
if(chk[ex[pt][j]]) pos.erase(h[ex[pt][j]].y1),pos.erase(h[ex[pt][j]].y2-1);
else pos.insert(h[ex[pt][j]].y1),pos.insert(h[ex[pt][j]].y2-1);
chk[ex[pt][j]]^=1;
}
}
if(!exist(v[i-1].y,v[i].y)){
int dist=v[i].y-v[i-1].y;
conn[v[i].idx].push_back(make_pair(v[i-1].idx,dist));
conn[v[i-1].idx].push_back(make_pair(v[i].idx,dist));
}
}
}
pos.clear();
for(int i=0;i<m;i++) chk[i]=0;
sort(v,v+n,cmpy);
for(int i=1,pt=0;i<n;i++){
if(v[i-1].y==v[i].y){
for(;iycp[pt]<=v[i].y&&pt<iycp.size();pt++){
for(int j=0;j<ey[pt].size();j++) {
if(chk[ey[pt][j]]) pos.erase(h[ey[pt][j]].x1),pos.erase(h[ey[pt][j]].x2-1);
else pos.insert(h[ey[pt][j]].x1),pos.insert(h[ey[pt][j]].x2-1);
chk[ey[pt][j]]^=1;
}
}
//printf("%d %d %d\n",pos.size(),v[i].y,iycp.size());
if(!exist(v[i-1].x,v[i].x)){
int dist=v[i].x-v[i-1].x;
conn[v[i].idx].push_back(make_pair(v[i-1].idx,dist));
conn[v[i-1].idx].push_back(make_pair(v[i].idx,dist));
}
}
}
for(int i=0;i<n;i++){
for(int j=0;j<conn[i].size();j++) {
if(i<conn[i][j].x) mst.push_back({i,conn[i][j].x,conn[i][j].y});
//printf("%d %d %d\n",i,conn[i][j].x,conn[i][j].y);
}
}
for(int i=0;i<n;i++) par[i]=i;
sort(mst.begin(),mst.end());
val.push_back(0ll),val2.push_back(0);
for(int i=0;i<mst.size();i++){
if(fnd(mst[i].x)!=fnd(mst[i].y)) cum+=(ll)mst[i].d, val.push_back(cum), val2.push_back(mst[i].d), uni(mst[i].x,mst[i].y);
}
vector<int>::iterator it;
for(int i=0;i<c;i++){
int t1,t2;
scanf("%d%d",&t1,&t2);
if(n-val.size()>=t2){
printf("-1\n");
}
else{
it=lower_bound(val2.begin(),val2.end(),t1);
int idx=max(it-val2.begin()-1,n-t2);
printf("%lld\n",(ll)val[idx]+t1*(n-idx));
}
}
}