Submission #647105

#	Time	Username	Problem	Language	Result	Execution time	Memory
647105		ByeWorld	Autobahn (COI21_autobahn)	C++14	100 / 100	351 ms	33752 KiB

autobahn

#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define int long long
using namespace std;
typedef pair<int,int> pii;
typedef pair<int,pii> ipii;
typedef pair<pii,int> piii;

const int MAXN = 1e6+10;

int l[MAXN], r[MAXN], c[MAXN];
vector <int> v;
int cnt[MAXN];
int prefval[MAXN];
int val[MAXN]; //yg bisa kena happy hour

signed main(){
	int n, k, w; cin >> n >> k >> w;
	v.pb(-1);
	for(int i=1; i<=n; i++){
		cin >> l[i] >> c[i] >> r[i]; r[i]++; c[i] += l[i];
		v.pb(l[i]-w); v.pb(l[i]+w); v.pb(c[i]-w); v.pb(c[i]+w); v.pb(r[i]-w); v.pb(r[i]+w);
		v.pb(l[i]); v.pb(r[i]); v.pb(c[i]);
	}
	sort(v.begin(), v.end());
	v.resize(unique(v.begin(), v.end())-v.begin());//value
	for(int i=1; i<=n; i++){
		l[i] = lower_bound(v.begin(), v.end(), l[i]) - v.begin();
		c[i] = lower_bound(v.begin(), v.end(), c[i]) - v.begin();
		r[i] = lower_bound(v.begin(), v.end(), r[i]) - v.begin();
	}

	for(int i=1; i<=n; i++){
		cnt[l[i]]++; cnt[r[i]]--;//k
		prefval[c[i]]++; prefval[r[i]]--;//prefix diff
	}
	for(int i=1; i<v.size(); i++){//ngebuat prefix bnrnnya
		cnt[i] += cnt[i-1]; prefval[i] += prefval[i-1];
	}
	for(int i=1; i<v.size(); i++){//suatu idx kalo lebih besar sama dengan k kita kenain
		if(cnt[i-1] >= k) val[i] = prefval[i-1]*(v[i]-v[i-1]);
	}
	for(int i=1; i<v.size(); i++){//val jd prefix
		val[i] += val[i-1];
	}
	int ans = 0;
	for(int i=0; i<v.size(); i++){//val jd prefix
		int nw = i;
		int dep = lower_bound(v.begin(), v.end(), v[i]+w) - v.begin();
		int bel = lower_bound(v.begin(), v.end(), v[i]-w) - v.begin();
		if(dep < v.size() && v[dep] == v[i]+w){//ada
			ans = max(ans, val[dep] - val[i]);
		}
		if(bel < v.size() && v[bel] == v[i]-w){//ada
			ans = max(ans, val[i]-val[bel]);
		}
	}
	cout << ans << '\n';
	/*for(int i=1; i<v.size(); i++){
		cout << v[i] << ' ' << cnt[i] << ' ' << prefval[i] << ' ' << val[i] << '\n';
	}*/
}

Compilation message (stderr)

autobahn.cpp: In function 'int main()':
autobahn.cpp:39:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |  for(int i=1; i<v.size(); i++){//ngebuat prefix bnrnnya
      |               ~^~~~~~~~~
autobahn.cpp:42:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |  for(int i=1; i<v.size(); i++){//suatu idx kalo lebih besar sama dengan k kita kenain
      |               ~^~~~~~~~~
autobahn.cpp:45:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |  for(int i=1; i<v.size(); i++){//val jd prefix
      |               ~^~~~~~~~~
autobahn.cpp:49:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |  for(int i=0; i<v.size(); i++){//val jd prefix
      |               ~^~~~~~~~~
autobahn.cpp:53:10: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |   if(dep < v.size() && v[dep] == v[i]+w){//ada
      |      ~~~~^~~~~~~~~~
autobahn.cpp:56:10: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |   if(bel < v.size() && v[bel] == v[i]-w){//ada
      |      ~~~~^~~~~~~~~~
autobahn.cpp:50:7: warning: unused variable 'nw' [-Wunused-variable]
   50 |   int nw = i;
      |       ^~

• Subtask 1: 20 / 20
• Subtask 2: 30 / 30
• Subtask 3: 50 / 50