oj.uz

Submission #554755

# Submission time Handle Problem Language Result Execution time Memory
554755 2022-04-29T11:11:10 Z Koosha_mv Road Construction (JOI21_road_construction) C++14
32 / 100
 10000 ms 60964 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){
	fill(seg,seg+N,pinf);
	ans.clear();
	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;
			while(vec[x].F+vec[x].S-get(0,p).F<=val){
				ans.pb(vec[x].F+vec[x].S-get(0,p).F);
				op.pb(get(0,p).S);
				//cout<<x<<" - "<<op.back()<<" "<<get(0,p).F<<endl;
				del(get(0,p).S);
				if(ans.size()>=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=4e9;
	//cout<<check(3000000000)<<"CC"<<endl;
	//return ans;
	while(l+1<r){
		int mid=(l+r)>>1;
		if(check(mid)) l=mid;
		else r=mid;
	}
	//check(l);
	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);
	cin>>n>>k;
	f(i,0,n) cin>>a[i]>>b[i];
	vector<int> A,B;
	A=solve();
	//dbgv(A);
	f(i,0,n) a[i]=-a[i],swap(a[i],b[i]);
	B=solve();
	//dbgv(B);
	for(auto x : B) A.pb(x);
	sort(all(A));
	//cout<<"ANS : ";
	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 'bool check(long long int)':
road_construction.cpp:69: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]
   69 |     if(ans.size()>=k) return 0;
      |        ~~~~~~~~~~^~~
road_construction.cpp: In function 'std::vector<long long int> solve()':
road_construction.cpp:93: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]
   93 |  while(ans.size()<k) ans.pb(r);
      |        ~~~~~~~~~~^~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3766 ms 26712 KB Output is correct
2 Correct 3784 ms 26852 KB Output is correct
3 Correct 2063 ms 26728 KB Output is correct
4 Correct 1704 ms 26640 KB Output is correct
5 Correct 3318 ms 25564 KB Output is correct
6 Correct 172 ms 16084 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 8989 ms 60964 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5614 ms 55692 KB Output is correct
2 Correct 4322 ms 58240 KB Output is correct
3 Correct 123 ms 15992 KB Output is correct
4 Correct 4993 ms 56156 KB Output is correct
5 Correct 1982 ms 33396 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5614 ms 55692 KB Output is correct
2 Correct 4322 ms 58240 KB Output is correct
3 Correct 123 ms 15992 KB Output is correct
4 Correct 4993 ms 56156 KB Output is correct
5 Correct 1982 ms 33396 KB Output is correct
6 Correct 6117 ms 58208 KB Output is correct
7 Correct 6475 ms 58220 KB Output is correct
8 Correct 122 ms 15956 KB Output is correct
9 Correct 133 ms 16000 KB Output is correct
10 Correct 6382 ms 55144 KB Output is correct
11 Correct 4838 ms 56020 KB Output is correct
12 Correct 2135 ms 33512 KB Output is correct

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3766 ms 26712 KB Output is correct
2 Correct 3784 ms 26852 KB Output is correct
3 Correct 2063 ms 26728 KB Output is correct
4 Correct 1704 ms 26640 KB Output is correct
5 Correct 3318 ms 25564 KB Output is correct
6 Correct 172 ms 16084 KB Output is correct
7 Execution timed out 10003 ms 36792 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3766 ms 26712 KB Output is correct
2 Correct 3784 ms 26852 KB Output is correct
3 Correct 2063 ms 26728 KB Output is correct
4 Correct 1704 ms 26640 KB Output is correct
5 Correct 3318 ms 25564 KB Output is correct
6 Correct 172 ms 16084 KB Output is correct
7 Incorrect 8989 ms 60964 KB Output isn't correct
8 Halted 0 ms 0 KB -