oj.uz

Submission #554781

# Submission time Handle Problem Language Result Execution time Memory
554781 2022-04-29T11:43:37 Z Koosha_mv Road Construction (JOI21_road_construction) C++14
65 / 100
 10000 ms 64636 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=6e5+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;
vector<vector<int>> mvec;

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 v : mvec){
		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]);
	for(auto p : mark) mvec.pb(p.S);
	
	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();
	mvec.clear();
	while(ans.size()<k) ans.pb(r);
	return ans;
}

int32_t main(){
	ios:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin>>n>>k;
	f(i,0,n) cin>>a[i]>>b[i];
	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:94: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]
   94 |  while(ans.size()<k) ans.pb(r);
      |        ~~~~~~~~~~^~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3172 ms 20480 KB Output is correct
2 Correct 3149 ms 20432 KB Output is correct
3 Correct 1527 ms 20476 KB Output is correct
4 Correct 1219 ms 20456 KB Output is correct
5 Correct 2442 ms 19328 KB Output is correct
6 Correct 105 ms 9812 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7325 ms 64444 KB Output is correct
2 Correct 7115 ms 64420 KB Output is correct
3 Correct 891 ms 20232 KB Output is correct
4 Correct 6073 ms 64420 KB Output is correct
5 Correct 6767 ms 64444 KB Output is correct
6 Correct 6855 ms 64472 KB Output is correct
7 Correct 6347 ms 64432 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4596 ms 60624 KB Output is correct
2 Correct 3542 ms 60616 KB Output is correct
3 Correct 62 ms 9684 KB Output is correct
4 Correct 3742 ms 60600 KB Output is correct
5 Correct 2809 ms 23800 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4596 ms 60624 KB Output is correct
2 Correct 3542 ms 60616 KB Output is correct
3 Correct 62 ms 9684 KB Output is correct
4 Correct 3742 ms 60600 KB Output is correct
5 Correct 2809 ms 23800 KB Output is correct
6 Correct 5487 ms 60664 KB Output is correct
7 Correct 5170 ms 60636 KB Output is correct
8 Correct 72 ms 9684 KB Output is correct
9 Correct 65 ms 9716 KB Output is correct
10 Correct 5463 ms 55960 KB Output is correct
11 Correct 3851 ms 60672 KB Output is correct
12 Correct 2884 ms 23864 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3172 ms 20480 KB Output is correct
2 Correct 3149 ms 20432 KB Output is correct
3 Correct 1527 ms 20476 KB Output is correct
4 Correct 1219 ms 20456 KB Output is correct
5 Correct 2442 ms 19328 KB Output is correct
6 Correct 105 ms 9812 KB Output is correct
7 Correct 7480 ms 40032 KB Output is correct
8 Correct 7639 ms 39992 KB Output is correct
9 Correct 1224 ms 20448 KB Output is correct
10 Correct 6597 ms 36052 KB Output is correct
11 Correct 5409 ms 34688 KB Output is correct
12 Correct 5611 ms 25728 KB Output is correct
13 Correct 4532 ms 23940 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3172 ms 20480 KB Output is correct
2 Correct 3149 ms 20432 KB Output is correct
3 Correct 1527 ms 20476 KB Output is correct
4 Correct 1219 ms 20456 KB Output is correct
5 Correct 2442 ms 19328 KB Output is correct
6 Correct 105 ms 9812 KB Output is correct
7 Correct 7325 ms 64444 KB Output is correct
8 Correct 7115 ms 64420 KB Output is correct
9 Correct 891 ms 20232 KB Output is correct
10 Correct 6073 ms 64420 KB Output is correct
11 Correct 6767 ms 64444 KB Output is correct
12 Correct 6855 ms 64472 KB Output is correct
13 Correct 6347 ms 64432 KB Output is correct
14 Correct 4596 ms 60624 KB Output is correct
15 Correct 3542 ms 60616 KB Output is correct
16 Correct 62 ms 9684 KB Output is correct
17 Correct 3742 ms 60600 KB Output is correct
18 Correct 2809 ms 23800 KB Output is correct
19 Correct 5487 ms 60664 KB Output is correct
20 Correct 5170 ms 60636 KB Output is correct
21 Correct 72 ms 9684 KB Output is correct
22 Correct 65 ms 9716 KB Output is correct
23 Correct 5463 ms 55960 KB Output is correct
24 Correct 3851 ms 60672 KB Output is correct
25 Correct 2884 ms 23864 KB Output is correct
26 Correct 7480 ms 40032 KB Output is correct
27 Correct 7639 ms 39992 KB Output is correct
28 Correct 1224 ms 20448 KB Output is correct
29 Correct 6597 ms 36052 KB Output is correct
30 Correct 5409 ms 34688 KB Output is correct
31 Correct 5611 ms 25728 KB Output is correct
32 Correct 4532 ms 23940 KB Output is correct
33 Execution timed out 10091 ms 64636 KB Time limit exceeded
34 Halted 0 ms 0 KB -