oj.uz

Submission #386411

# Submission time Handle Problem Language Result Execution time Memory
386411 2021-04-06T14:03:50 Z haojiandan Road Construction (JOI21_road_construction) C++14
65 / 100
 10000 ms 771616 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 385 ms 5988 KB Output is correct
2 Correct 408 ms 6112 KB Output is correct
3 Correct 275 ms 4996 KB Output is correct
4 Correct 251 ms 4664 KB Output is correct
5 Correct 299 ms 4108 KB Output is correct
6 Correct 8 ms 876 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 584 ms 28240 KB Output is correct
2 Correct 582 ms 28216 KB Output is correct
3 Correct 85 ms 3004 KB Output is correct
4 Correct 308 ms 28068 KB Output is correct
5 Correct 327 ms 28332 KB Output is correct
6 Correct 391 ms 28380 KB Output is correct
7 Correct 313 ms 27472 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5202 ms 765700 KB Output is correct
2 Correct 5297 ms 765868 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 206 ms 27204 KB Output is correct
5 Correct 1116 ms 153224 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5202 ms 765700 KB Output is correct
2 Correct 5297 ms 765868 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 206 ms 27204 KB Output is correct
5 Correct 1116 ms 153224 KB Output is correct
6 Correct 5476 ms 765572 KB Output is correct
7 Correct 5642 ms 765468 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 5526 ms 752260 KB Output is correct
11 Correct 208 ms 27228 KB Output is correct
12 Correct 1090 ms 153140 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 385 ms 5988 KB Output is correct
2 Correct 408 ms 6112 KB Output is correct
3 Correct 275 ms 4996 KB Output is correct
4 Correct 251 ms 4664 KB Output is correct
5 Correct 299 ms 4108 KB Output is correct
6 Correct 8 ms 876 KB Output is correct
7 Correct 6473 ms 282372 KB Output is correct
8 Correct 6613 ms 282144 KB Output is correct
9 Correct 257 ms 4712 KB Output is correct
10 Correct 2172 ms 264248 KB Output is correct
11 Correct 3402 ms 264264 KB Output is correct
12 Correct 1431 ms 79976 KB Output is correct
13 Correct 1159 ms 64864 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 385 ms 5988 KB Output is correct
2 Correct 408 ms 6112 KB Output is correct
3 Correct 275 ms 4996 KB Output is correct
4 Correct 251 ms 4664 KB Output is correct
5 Correct 299 ms 4108 KB Output is correct
6 Correct 8 ms 876 KB Output is correct
7 Correct 584 ms 28240 KB Output is correct
8 Correct 582 ms 28216 KB Output is correct
9 Correct 85 ms 3004 KB Output is correct
10 Correct 308 ms 28068 KB Output is correct
11 Correct 327 ms 28332 KB Output is correct
12 Correct 391 ms 28380 KB Output is correct
13 Correct 313 ms 27472 KB Output is correct
14 Correct 5202 ms 765700 KB Output is correct
15 Correct 5297 ms 765868 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 206 ms 27204 KB Output is correct
18 Correct 1116 ms 153224 KB Output is correct
19 Correct 5476 ms 765572 KB Output is correct
20 Correct 5642 ms 765468 KB Output is correct
21 Correct 1 ms 364 KB Output is correct
22 Correct 1 ms 364 KB Output is correct
23 Correct 5526 ms 752260 KB Output is correct
24 Correct 208 ms 27228 KB Output is correct
25 Correct 1090 ms 153140 KB Output is correct
26 Correct 6473 ms 282372 KB Output is correct
27 Correct 6613 ms 282144 KB Output is correct
28 Correct 257 ms 4712 KB Output is correct
29 Correct 2172 ms 264248 KB Output is correct
30 Correct 3402 ms 264264 KB Output is correct
31 Correct 1431 ms 79976 KB Output is correct
32 Correct 1159 ms 64864 KB Output is correct
33 Execution timed out 10150 ms 771616 KB Time limit exceeded
34 Halted 0 ms 0 KB -