oj.uz

Submission #554757

# Submission time Handle Problem Language Result Execution time Memory
554757 2022-04-29T11:15:17 Z Koosha_mv Road Construction (JOI21_road_construction) C++14
32 / 100
 8361 ms 58388 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();
	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)){
				ans.pb(vec[x].F+vec[x].S-e.F);
				op.pb(e.S);
				del(e.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=inf;
	//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, long long int)':
road_construction.cpp:68: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]
   68 |     if(ans.size()>=k) return 0;
      |        ~~~~~~~~~~^~~
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

# Verdict Execution time Memory Grader output
1 Correct 2837 ms 26756 KB Output is correct
2 Correct 2856 ms 26672 KB Output is correct
3 Correct 1584 ms 26660 KB Output is correct
4 Correct 1271 ms 26752 KB Output is correct
5 Correct 2471 ms 25600 KB Output is correct
6 Correct 163 ms 16100 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 8352 ms 58388 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 5320 ms 53180 KB Output is correct
2 Correct 3952 ms 53168 KB Output is correct
3 Correct 130 ms 15992 KB Output is correct
4 Correct 4846 ms 53056 KB Output is correct
5 Correct 2633 ms 28008 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5320 ms 53180 KB Output is correct
2 Correct 3952 ms 53168 KB Output is correct
3 Correct 130 ms 15992 KB Output is correct
4 Correct 4846 ms 53056 KB Output is correct
5 Correct 2633 ms 28008 KB Output is correct
6 Correct 6184 ms 53072 KB Output is correct
7 Correct 6363 ms 53252 KB Output is correct
8 Correct 132 ms 15956 KB Output is correct
9 Correct 131 ms 15988 KB Output is correct
10 Correct 6653 ms 50180 KB Output is correct
11 Correct 5437 ms 53472 KB Output is correct
12 Correct 2917 ms 28488 KB Output is correct

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2837 ms 26756 KB Output is correct
2 Correct 2856 ms 26672 KB Output is correct
3 Correct 1584 ms 26660 KB Output is correct
4 Correct 1271 ms 26752 KB Output is correct
5 Correct 2471 ms 25600 KB Output is correct
6 Correct 163 ms 16100 KB Output is correct
7 Correct 8247 ms 41020 KB Output is correct
8 Correct 8361 ms 42676 KB Output is correct
9 Correct 1276 ms 26820 KB Output is correct
10 Correct 7237 ms 41792 KB Output is correct
11 Incorrect 5886 ms 40956 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2837 ms 26756 KB Output is correct
2 Correct 2856 ms 26672 KB Output is correct
3 Correct 1584 ms 26660 KB Output is correct
4 Correct 1271 ms 26752 KB Output is correct
5 Correct 2471 ms 25600 KB Output is correct
6 Correct 163 ms 16100 KB Output is correct
7 Incorrect 8352 ms 58388 KB Output isn't correct
8 Halted 0 ms 0 KB -