Submission #1285505

#	Time	Username	Problem	Language	Result	Execution time	Memory
1285505		kerem	도로 건설 사업 (JOI13_construction)	C++20	100 / 100	2178 ms	226408 KiB

construction

#include <bits/stdc++.h>
using namespace std;
//~ #define int int64_t
#define pb push_back
#define fr first
#define sc second
#define all(x) x.begin(),x.end()
#define sp << " " <<
#define N 200000
#define inf (int)1e15
typedef pair<int,int> pii;
typedef tuple<int,int,int,int> iiii;
typedef tuple<int,int,int> iii;

struct Node{
	int val;
	Node *l,*r;
	Node(){val=0;l=r=0;}
	Node(Node *ll,Node *rr){val=0;l=ll;r=rr;}
};

Node *root;
map<int,pii> mp;
vector<iii> edge;
int dsu[N+5];

void clear(Node *node){
	if(!node) return;
	clear(node->l);clear(node->r);
	delete node;
}
Node* update(Node *node,int l,int r,int ql,int qr,int val){
	if(r<ql || qr<l) return node;
	if(!node) node=new Node();
	if(ql<=l && r<=qr){
		node->val+=val;
		return node;
	}
	int mid=(l+r)/2;
	node->l=update(node->l,l,mid,ql,qr,val);
	node->r=update(node->r,mid+1,r,ql,qr,val);
	return node;
}
int query(Node *node,int l,int r,int qx){
	if(!node || r<qx || qx<l) return 0;
	if(l==r) return node->val;
	int mid=(l+r)/2;
	return node->val+query(node->l,l,mid,qx)+query(node->r,mid+1,r,qx);
}
void calc(vector<iiii> &v){
	sort(all(v));
	mp.clear();
	clear(root);
	root=new Node();
	//~ cerr << "--------\n";
	for(auto [x,l,r,t]:v){
		//~ cerr << x sp l sp r sp t << "\n";
		if(l>1e9){
			int y=r,i=t;
			if(mp.find(y)!=mp.end())
				edge.pb({x-mp[y].fr,mp[y].sc,i});
			if(query(root,0,1e9,y)==0)
				mp[y]={x,i};
		}
		else{
			if(t)
				root=update(root,0,1e9,l,r,-1);
			else{
				if(mp.lower_bound(l)!=mp.end())
					mp.erase(mp.lower_bound(l),mp.upper_bound(r));
				root=update(root,0,1e9,l,r,1);
			}
		}
	}
}
int find(int x){
	if(dsu[x]<0)
		return x;
	return dsu[x]=find(dsu[x]);
}
bool comb(int x,int y){
	x=find(x);y=find(y);
	if(x==y) return false;
	dsu[y]=x;
	return true;
}
void solve(){
	memset(dsu,-1,sizeof(dsu));
	int n,m,q;
	cin >> n >> m >> q;
	vector<iiii> vx,vy;
	for(int i=0;i<n;i++){
		int x,y;
		cin >> x >> y;
		vx.pb({x,1e9+1,y,i});
		vy.pb({y,1e9+1,x,i});
	}
	for(int i=0;i<m;i++){
		int x1,y1,x2,y2;
		cin >> x1 >> y1 >> x2 >> y2;
		vx.pb({x1,y1,y2,0});
		vx.pb({x2,y1,y2,1});
		vy.pb({y1,x1,x2,0});
		vy.pb({y2,x1,x2,1});
	}
	calc(vx);
	calc(vy);
	
	int64_t cost[n+1],ind=n-1;
	memset(cost,-1,sizeof(cost));
	cost[n]=0;
	sort(all(edge));
	for(auto [d,a,b]:edge){
		if(comb(a,b)){
			cost[ind]=cost[ind+1]+d;
			ind--;
		}
	}
	while(q--){
		int d,h;
		cin >> d >> h;
		if(h<=ind){
			cout << -1 << "\n";
			continue;
		}
		int l=ind+1,r=n;
		while(l<r){
			int mid=(l+r+1)/2;
			if(cost[mid-1]-cost[mid]>d)
				l=mid;
			else r=mid-1;
		}
		h=min(h,l);
		cout << 1LL*h*d+cost[h] << "\n";
	}
}
int32_t main(){
	//~ freopen("hopscotch.in","r",stdin);
	//~ freopen("hopscotch.out","w",stdout);
	
	cout << fixed << setprecision(0);
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);cout.tie(NULL);
	
	int test=1;
	//~ cin >> test;
	while(test--) solve();
}

• Subtask 1: 10 / 10
• Subtask 2: 30 / 30
• Subtask 3: 30 / 30
• Subtask 4: 30 / 30