Submission #386411

#	Time	Username	Problem	Language	Result	Execution time	Memory
386411		haojiandan	Road Construction (JOI21_road_construction)	C++14	65 / 100	10150 ms	771616 KiB

road_construction

#include <bits/stdc++.h>
using namespace std;
template <typename T> void read(T &t) {
	t=0; char ch=getchar(); int f=1;
	while (ch<'0'||ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
	do { (t*=10)+=ch-'0'; ch=getchar(); } while ('0'<=ch&&ch<='9'); t*=f;
}
template <typename T> void write(T t) {
	if (t<0) { putchar('-'); write(-t); return; }
	if (t>9) write(t/10);
	putchar('0'+t%10);
}
template <typename T> void writeln(T t) {
	write(t);
	puts("");
}
typedef long long ll;
const int INF=2000000010;
const int maxn=250010;
const int maxm=(8e7)+10;
int n,k,y[maxn],lsh[maxn],lsh2[maxn],N,N2;
struct Node { int l,r,root; };
pair<int,int> cmin(pair<int,int> &A,pair<int,int> &B) {
	if (A>B) return B;
	return A;
}
namespace Seg {
	pair<int,int> tr[maxm];
	int ls[maxm],rs[maxm],tot;
	void clear() {
		tot=0; tr[0]=make_pair(INF,INF);
	}
	int top,st[100],tmp;
	void newnode(int &root) {
		if (!root) root=++tot,ls[tot]=rs[tot]=0,tr[tot]=make_pair(INF,INF);
	}
	void add(int x,int delta,int pos,int &root) {
		newnode(root);
		int l=1,r=n,mid; top=0; tmp=root;
		pair<int,int> T=make_pair(delta,pos);
		while (1) {
		//	printf("%d %d %d\n",l,r,tmp);
			if (l==r) {
				tr[tmp]=cmin(tr[tmp],T);
				break;
			}
			mid=(l+r)>>1; st[++top]=tmp;
			if (x<=mid) r=mid,newnode(ls[tmp]),tmp=ls[tmp];
			else l=mid+1,newnode(rs[tmp]),tmp=rs[tmp];
		}
		for (int i=top;i>=1;i--) {
			tmp=st[i];
			tr[tmp]=cmin(tr[ls[tmp]],tr[rs[tmp]]);
		}
	}
	/*void add(int x,int l,int r,int &root,int delta,int pos) {
		if (!root) root=++tot,ls[tot]=rs[tot]=0,tr[tot]=make_pair(INF,INF);
		if (l==r) {
			tr[root]=min(tr[root],make_pair(delta,pos));
			return;
		}
		int mid=(l+r)>>1;
		if (x<=mid) add(x,l,mid,ls[root],delta,pos);
		else add(x,mid+1,r,rs[root],delta,pos);
		tr[root]=min(tr[ls[root]],tr[rs[root]]);
	}
	void query(int L,int R,int l,int r,int root,pair<int,int> &res) {
		if (!root) return;
		if (L<=l&&r<=R) {
			if (res>tr[root]) res=tr[root];
			return;
		}
		int mid=(l+r)>>1;
		if (L<=mid) query(L,R,l,mid,ls[root],res);
		if (mid<R) query(L,R,mid+1,r,rs[root],res);
	}*/
	int hd,tl;
	Node Q[10000];
	void query(int L,int R,int root,pair<int,int> &res) {
		if (!root) return;
		if (L>R) return;
		int l,r,mid; Q[hd=tl=1]=(Node){1,n,root};
		if (L<=1&&n<=R) { res=min(res,tr[root]); return; }
		while (hd<=tl) {
			l=Q[hd].l,r=Q[hd].r,root=Q[hd].root; hd++;
			mid=(l+r)>>1;
			if (L<=mid&&ls[root]) {
				if (L<=l&&mid<=R) res=cmin(res,tr[ls[root]]);
				else Q[++tl]=(Node){l,mid,ls[root]};
			}
			if (mid<R&&rs[root]) {
				if (L<=mid+1&&r<=R) res=cmin(res,tr[rs[root]]);
				else Q[++tl]=(Node){mid+1,r,rs[root]};
			}
		}
	}
};
int rt1[maxn],rt2[maxn];
void add1(int x,int y,int delta,int i) {
	for (;y<=N;y+=y&(-y)) Seg::add(x,delta,i,rt1[y]);
}
void add2(int x,int y,int delta,int i) {
	y=N-y+1;
	for (;y<=N;y+=y&(-y)) Seg::add(x,delta,i,rt2[y]);
}
pair<int,int> query1(int l,int r,int x) {
	pair<int,int> res=make_pair(INF,INF);
	for (;x;x-=x&(-x)) Seg::query(l,r,rt1[x],res);
	return res;
}
pair<int,int> query2(int l,int r,int x) {
	x=N-x+1;
	pair<int,int> res=make_pair(INF,INF);
	for (;x;x-=x&(-x)) Seg::query(l,r,rt2[x],res);
	return res;
}
pair<int,int> d[maxn],t1,t2;
int Y[maxn];
ll T1,T2;
struct node {
	int l,r,x,mid;
	ll ans;
	void init(int _l,int _r,int _x) {
		l=_l,r=_r,x=_x;
		t1=query1(l,r,Y[x]),t2=query2(l,r,Y[x]+1);
		T1=(ll)t1.first+d[x].first+d[x].second,T2=(ll)t2.first+d[x].first-d[x].second;
		//printf("%lld %lld\n",T1,T2);
		if (t1.first==INF) T1=(ll)INF*10;
		if (t2.first==INF) T2=(ll)INF*10;
		if (T1>T2) {
			ans=T2,mid=t2.second;
		}
		else ans=T1,mid=t1.second;
		//printf("find%lld %d %d %d\n",ans,l,r,x);
	}
} A,B;
struct cmp {
	bool operator() (node A,node B) { return A.ans>B.ans; }
};
priority_queue<node,vector<node>,cmp> q;
int main() {
	//freopen("1.txt","r",stdin);
	read(n),read(k);
	for (int i=1;i<=n;i++) {
		read(d[i].first),read(d[i].second);
		lsh[++N]=d[i].second;
		lsh2[++N2]=d[i].first;
	}
	sort(lsh+1,lsh+N+1),N=unique(lsh+1,lsh+N+1)-lsh-1;
	sort(lsh2+1,lsh2+N2+1),N2=unique(lsh2+1,lsh2+N2+1)-lsh2-1;
	if (N>N2) {
		for (int i=1;i<=n;i++) swap(d[i].first,d[i].second);
		N=N2;
		for (int i=1;i<=N;i++) lsh[i]=lsh2[i];
	}
	
	sort(d+1,d+n+1);
	Seg::clear();
	for (int i=1;i<=n;i++) {
		Y[i]=lower_bound(lsh+1,lsh+N+1,d[i].second)-lsh;
		add1(i,Y[i],-d[i].first-d[i].second,i);
		add2(i,Y[i],d[i].second-d[i].first,i);
	}
	assert(Seg::tot<maxm);
//	printf("%d\n",Seg::tot); return 0;
	
	// 4.5s
	for (int i=2;i<=n;i++) {
		A.init(1,i-1,i);
	//	printf("%d\n",i);
		q.push(A);
	}
	// 7s
	//if (n>2000) return 0;
	int x,l,r,mid;
	while (k--) {
		A=q.top(); q.pop();
		writeln(A.ans);
		//printf("%d\n",k);
		x=A.x,l=A.l,mid=A.mid,r=A.r;
		if (mid!=l) {
			B.init(l,mid-1,x);
			if (B.mid!=INF) q.push(B);
		}
		if (mid!=r) {
			B.init(mid+1,r,x);
			if (B.mid!=INF) q.push(B);
		}
	}
	return 0;
}
/*
  0. Enough array size? Enough array size? Enough array size? Integer overflow?
  
  1. Think TWICE, Code ONCE!
  Are there any counterexamples to your algo?
    
  2. Be careful about the BOUNDARIES!
  N=1? P=1? Something about 0?
    
  3. Do not make STUPID MISTAKES!
  Time complexity? Memory usage? Precision error?
*/

• Subtask 1: 5 / 5
• Subtask 2: 6 / 6
• Subtask 3: 7 / 7
• Subtask 4: 20 / 20
• Subtask 5: 27 / 27
• Subtask 6: 0 / 35