oj.uz

Submission #944981

# Submission time Handle Problem Language Result Execution time Memory
944981 2024-03-13T09:27:23 Z Xiaoyang Road Construction (JOI21_road_construction) C++17
6 / 100
 370 ms 26400 KB 
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
typedef long long ll;
 
#define fi first 
#define se second 
#define pll pair<ll,ll>
#define pb push_back
#define debug(x) cerr<<#x<<"="<<x<<endl;
#define MP make_pair
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define SZ(x) (ll)x.size()
#define ALL(x) x.begin(),x.end()
#define endl "\n"
const ll inf=1e18;
ll lowbit(ll x){return x&(-x);}

const ll maxn=255555;
ll x[maxn],y[maxn];

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	ll n,k;cin>>n>>k;
	rep(i,1,n+1)cin>>x[i]>>y[i];
	sort(x+1,x+n+1);
	multiset<pair<ll,pll>>s;
	rep(i,1,n){
		s.insert(MP(x[i+1]-x[i],MP(i,i+1)));
	}
	vector<ll>ans;
	while(ans.size()<k){
		auto tmp=*s.begin();
		ans.pb(tmp.fi);
		ll l=tmp.se.fi,r=tmp.se.se;
		s.erase(tmp);
		if(r<n){
			s.insert(MP(x[r+1]-x[l],MP(l,r+1)));
		}
	}
	for(auto w:ans)cout<<w<<endl;
	
	return 0;
}

Compilation message

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

Subtask #1
0 / 5.0

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

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 337 ms 23244 KB Output is correct
2 Correct 370 ms 26400 KB Output is correct
3 Correct 52 ms 6988 KB Output is correct
4 Correct 158 ms 26048 KB Output is correct
5 Correct 169 ms 26184 KB Output is correct
6 Correct 169 ms 26300 KB Output is correct
7 Correct 186 ms 25628 KB Output is correct

Subtask #3
0 / 7.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 27.0

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

Subtask #6
0 / 35.0

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