oj.uz

답안 #554772

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
554772 2022-04-29T11:33:21 Z Koosha_mv Road Construction (JOI21_road_construction) C++14
59 / 100
 10000 ms 73908 KB 
#include <bits/stdc++.h>
using namespace std;
#define dbgv(v) cout<<#v<<" = "; f(i,0,v.size()) cout<<v[i]<<" "; cout<<endl
#define dbga(a,x,y) cout<<#a<<" = "; f(i,x,y) cout<<a[i]<<" "; cout<<endl
#define erorp(x) cout<<#x<<"={"<<x.F<<" , "<<x.S<<"}"<<endl
#define eror(x) cout<<#x<<'='<<(x)<<endl
#define f_(i,a,b) for(int i=a;i>=b;i--)
#define f(i,a,b) for(int i=a;i<b;i++)
#define nb(x) __builtin_popcount(x)
#define all(v) v.begin(),v.end()
#define bit(n,k) (((n)>>(k))&1)
#define Add(x,y) x=(x+y)%mod
#define maxm(a,b) a=max(a,b)
#define minm(a,b) a=min(a,b)
#define lst(x) x[x.size()-1]
#define sz(x) int(x.size())
#define mp make_pair
#define ll long long
#define pb push_back
#define S second
#define F first
#define int ll

typedef pair<int,int> pii;

const int N=1e6+99,inf=1e10;
const pii pinf={-10*inf,-1};

int n,k,a[N],b[N],pos[N];
pii seg[N];
vector<int> ans;
vector<pii> vec;
map<int,vector<int>> mark;

void add(int x){
	seg[x+n]={vec[x].F+vec[x].S,x};
	for(x+=n;x>1;x>>=1){
		seg[x>>1]=max(seg[x],seg[x^1]);
	}
}
void del(int x){
	seg[x+n]=pinf;
	for(x+=n;x>1;x>>=1){
		seg[x>>1]=max(seg[x],seg[x^1]);
	}
}
pii get(int l,int r){
	pii res=pinf;
	for(l+=n,r+=n;l<r;l>>=1,r>>=1){
		if(l&1) maxm(res,seg[l++]);
		if(r&1) maxm(res,seg[--r]);
	}
	return res;
}
bool check(int val,int type=0){
	fill(seg,seg+N,pinf);
	ans.clear();
	int cnt=0;
	for(auto p : mark){
		vector<int> v=p.S;
		for(auto x : v) add(x);
		for(auto x : v){
			int p=upper_bound(all(vec),mp(vec[x].F,-inf))-vec.begin();
			vector<int> op;
			for(pii e=get(0,p);vec[x].F+vec[x].S-e.F<=val;e=get(0,p)){
				cnt++;
				op.pb(e.S);
				del(e.S);
				if(type==1) ans.pb(vec[x].F+vec[x].S-e.F);
				if(cnt>=k) return 0;
			}
			for(auto id : op) add(id);
		}
	}
	return 1;
}
vector<int> solve(){
	f(i,0,n) vec.pb({a[i],b[i]});
	sort(all(vec));
	f(i,0,n) pos[i]=lower_bound(all(vec),mp(a[i],b[i]))-vec.begin();
	f(i,0,n) mark[b[i]].pb(pos[i]);
	
	int l=0,r=inf;
	while(l+1<r){
		int mid=(l+r)>>1;
		if(check(mid)) l=mid;
		else r=mid;
	}
	check(l,1);
	vec.clear();
	mark.clear();
	while(ans.size()<k) ans.pb(r);
	return ans;
}

int32_t main(){
	ios:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
	map<pair<int,int>,int> cnt;
	cin>>n>>k;
	f(i,0,n){
		cin>>a[i]>>b[i];
		if(++cnt[mp(a[i],b[i])]>1) assert(0);
	}
	vector<int> A,B;
	A=solve();
	f(i,0,n) a[i]=-a[i],swap(a[i],b[i]);
	B=solve();
	for(auto x : B) A.pb(x);
	sort(all(A));
	f(i,0,k) cout<<A[i]<<" ";
}
/*
3 2
0 1
0 0
2 0

3 2
-1 0
0 0
0 2
*/

Compilation message

road_construction.cpp: In function 'std::vector<long long int> solve()':
road_construction.cpp:92:18: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   92 |  while(ans.size()<k) ans.pb(r);
      |        ~~~~~~~~~~^~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3042 ms 26752 KB Output is correct
2 Correct 3016 ms 26756 KB Output is correct
3 Correct 1623 ms 26788 KB Output is correct
4 Correct 1363 ms 26772 KB Output is correct
5 Correct 2590 ms 25588 KB Output is correct
6 Correct 180 ms 16204 KB Output is correct

Subtask #2
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9393 ms 73908 KB Output is correct
2 Correct 9425 ms 73908 KB Output is correct
3 Correct 1049 ms 26612 KB Output is correct
4 Correct 8506 ms 73688 KB Output is correct
5 Execution timed out 10033 ms 72700 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6614 ms 69152 KB Output is correct
2 Correct 5113 ms 69196 KB Output is correct
3 Correct 137 ms 16076 KB Output is correct
4 Correct 5326 ms 69228 KB Output is correct
5 Correct 3148 ms 44124 KB Output is correct

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6614 ms 69152 KB Output is correct
2 Correct 5113 ms 69196 KB Output is correct
3 Correct 137 ms 16076 KB Output is correct
4 Correct 5326 ms 69228 KB Output is correct
5 Correct 3148 ms 44124 KB Output is correct
6 Correct 6797 ms 68992 KB Output is correct
7 Correct 7138 ms 69056 KB Output is correct
8 Correct 134 ms 16076 KB Output is correct
9 Correct 138 ms 15956 KB Output is correct
10 Correct 6924 ms 65960 KB Output is correct
11 Correct 5414 ms 69048 KB Output is correct
12 Correct 3225 ms 44032 KB Output is correct

Subtask #5
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3042 ms 26752 KB Output is correct
2 Correct 3016 ms 26756 KB Output is correct
3 Correct 1623 ms 26788 KB Output is correct
4 Correct 1363 ms 26772 KB Output is correct
5 Correct 2590 ms 25588 KB Output is correct
6 Correct 180 ms 16204 KB Output is correct
7 Correct 8651 ms 47224 KB Output is correct
8 Correct 8828 ms 47152 KB Output is correct
9 Correct 1291 ms 26796 KB Output is correct
10 Correct 7580 ms 46272 KB Output is correct
11 Correct 6107 ms 45488 KB Output is correct
12 Correct 5915 ms 38460 KB Output is correct
13 Correct 4883 ms 35836 KB Output is correct

Subtask #6
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3042 ms 26752 KB Output is correct
2 Correct 3016 ms 26756 KB Output is correct
3 Correct 1623 ms 26788 KB Output is correct
4 Correct 1363 ms 26772 KB Output is correct
5 Correct 2590 ms 25588 KB Output is correct
6 Correct 180 ms 16204 KB Output is correct
7 Correct 9393 ms 73908 KB Output is correct
8 Correct 9425 ms 73908 KB Output is correct
9 Correct 1049 ms 26612 KB Output is correct
10 Correct 8506 ms 73688 KB Output is correct
11 Execution timed out 10033 ms 72700 KB Time limit exceeded
12 Halted 0 ms 0 KB -