oj.uz

Submission #647104

# Submission time Handle Problem Language Result Execution time Memory
647104 2022-10-01T15:20:10 Z ByeWorld Autobahn (COI21_autobahn) C++14
50 / 100
 283 ms 22404 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 = 2e5+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 1 ms 340 KB Output is correct
11 Correct 1 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 1 ms 340 KB Output is correct
11 Correct 1 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 576 KB Output is correct
18 Correct 2 ms 596 KB Output is correct
19 Correct 3 ms 568 KB Output is correct
20 Correct 2 ms 596 KB Output is correct

Subtask #3
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 1 ms 340 KB Output is correct
11 Correct 1 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 576 KB Output is correct
18 Correct 2 ms 596 KB Output is correct
19 Correct 3 ms 568 KB Output is correct
20 Correct 2 ms 596 KB Output is correct
21 Runtime error 283 ms 22404 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -