oj.uz

Submission #647105

# Submission time Handle Problem Language Result Execution time Memory
647105 2022-10-01T15:21:24 Z ByeWorld Autobahn (COI21_autobahn) C++14
100 / 100
 351 ms 33752 KB 
#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

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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 2 ms 596 KB Output is correct
13 Correct 2 ms 596 KB Output is correct
14 Correct 2 ms 596 KB Output is correct
15 Correct 2 ms 596 KB Output is correct
16 Correct 2 ms 596 KB Output is correct
17 Correct 2 ms 596 KB Output is correct
18 Correct 2 ms 596 KB Output is correct
19 Correct 2 ms 596 KB Output is correct
20 Correct 2 ms 596 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 2 ms 596 KB Output is correct
13 Correct 2 ms 596 KB Output is correct
14 Correct 2 ms 596 KB Output is correct
15 Correct 2 ms 596 KB Output is correct
16 Correct 2 ms 596 KB Output is correct
17 Correct 2 ms 596 KB Output is correct
18 Correct 2 ms 596 KB Output is correct
19 Correct 2 ms 596 KB Output is correct
20 Correct 2 ms 596 KB Output is correct
21 Correct 351 ms 31004 KB Output is correct
22 Correct 345 ms 33692 KB Output is correct
23 Correct 341 ms 33732 KB Output is correct
24 Correct 314 ms 33752 KB Output is correct
25 Correct 324 ms 33672 KB Output is correct
26 Correct 320 ms 33720 KB Output is correct
27 Correct 317 ms 33616 KB Output is correct
28 Correct 319 ms 33664 KB Output is correct
29 Correct 327 ms 33572 KB Output is correct