oj.uz

Submission #554759

# Submission time Handle Problem Language Result Execution time Memory
554759 2022-04-29T11:17:19 Z Koosha_mv Road Construction (JOI21_road_construction) C++14
32 / 100
 9230 ms 74264 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);
	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();
	//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 2757 ms 26776 KB Output is correct
2 Correct 2768 ms 26760 KB Output is correct
3 Correct 1498 ms 26708 KB Output is correct
4 Correct 1257 ms 26892 KB Output is correct
5 Correct 2393 ms 25660 KB Output is correct
6 Correct 166 ms 16156 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 8319 ms 74264 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 5507 ms 69108 KB Output is correct
2 Correct 4159 ms 68988 KB Output is correct
3 Correct 134 ms 15956 KB Output is correct
4 Correct 5073 ms 69092 KB Output is correct
5 Correct 2886 ms 43952 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5507 ms 69108 KB Output is correct
2 Correct 4159 ms 68988 KB Output is correct
3 Correct 134 ms 15956 KB Output is correct
4 Correct 5073 ms 69092 KB Output is correct
5 Correct 2886 ms 43952 KB Output is correct
6 Correct 6307 ms 68984 KB Output is correct
7 Correct 6596 ms 69084 KB Output is correct
8 Correct 133 ms 15996 KB Output is correct
9 Correct 133 ms 15992 KB Output is correct
10 Correct 6461 ms 65832 KB Output is correct
11 Correct 5611 ms 68780 KB Output is correct
12 Correct 3040 ms 43660 KB Output is correct

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2757 ms 26776 KB Output is correct
2 Correct 2768 ms 26760 KB Output is correct
3 Correct 1498 ms 26708 KB Output is correct
4 Correct 1257 ms 26892 KB Output is correct
5 Correct 2393 ms 25660 KB Output is correct
6 Correct 166 ms 16156 KB Output is correct
7 Correct 8381 ms 46952 KB Output is correct
8 Correct 9230 ms 46896 KB Output is correct
9 Correct 1348 ms 26676 KB Output is correct
10 Correct 7731 ms 46020 KB Output is correct
11 Incorrect 5939 ms 45180 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2757 ms 26776 KB Output is correct
2 Correct 2768 ms 26760 KB Output is correct
3 Correct 1498 ms 26708 KB Output is correct
4 Correct 1257 ms 26892 KB Output is correct
5 Correct 2393 ms 25660 KB Output is correct
6 Correct 166 ms 16156 KB Output is correct
7 Incorrect 8319 ms 74264 KB Output isn't correct
8 Halted 0 ms 0 KB -