oj.uz

Submission #1116098

# Submission time Handle Problem Language Result Execution time Memory
1116098 2024-11-21T09:02:57 Z epicci23 Autobahn (COI21_autobahn) C++17
50 / 100
 253 ms 44452 KB 
#include "bits/stdc++.h"
#define int long long
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
using namespace std;

void _(){
  int n,k,X;
  cin >> n >> k >> X;

  array<int,3> ar[n+5];
  for(int i=1;i<=n;i++) cin >> ar[i][0] >> ar[i][1] >> ar[i][2];

  vector<int> zip,rev;
  for(int i=1;i<=n;i++){
    zip.push_back(ar[i][0]);
    zip.push_back(ar[i][0]+ar[i][1]);
    zip.push_back(ar[i][2]);
    zip.push_back(ar[i][2]+1);
  }

  sort(all(zip));
  zip.erase(unique(all(zip)),zip.end());
  
  vector<int> sor = zip;

  int _u = sz(zip);
  for(int i=0;i<_u;i++){
  	zip.push_back(zip[i]-X);
  	zip.push_back(zip[i]+X);
  }

  sort(all(zip));
  zip.erase(unique(all(zip)),zip.end());
   
  rev.resize(sz(zip)+5);
  for(int i=1;i<=sz(zip);i++) rev[i] = zip[i-1];

  auto Get = [&](int u){
    int it = lower_bound(all(zip),u) - zip.begin();
    return it + 1;
  };

  int cur = 0;
  vector<int> pre(sz(zip)+5,0);
  for(int i=1;i<=n;i++){
    pre[Get(ar[i][0])]++;
    pre[Get(ar[i][2]+1)]--;
  }

  for(int i=1;i<=sz(zip);i++) pre[i] += pre[i-1];
  for(int i=1;i<=sz(zip);i++) pre[i] = (pre[i] >= k);
  
  vector<int> T(sz(zip)+5,0);
  for(int i=1;i<=n;i++){
    int l = ar[i][0] + ar[i][1];
    int r = ar[i][2] + 1;
    T[Get(l)]++,T[Get(r)]--;
  }  

  for(int i=1;i<=sz(zip);i++) T[i]+=T[i-1];
  for(int i=1;i<=sz(zip);i++){
  	T[i] *= pre[i];
  	if(i<sz(zip)) T[i] *= (rev[i + 1] - rev[i]);
  }
  for(int i=1;i<=sz(zip);i++) T[i]+=T[i-1];
  int ans = 0;
  
  for(int u:sor){
  	int l = u , r = u + X;
    ans = max(ans, T[Get(r)] - T[Get(l)]);
    l = u - X , r = u;
    ans = max(ans, T[Get(r)] - T[Get(l)]);
  }

  cout << ans << '\n';
}

int32_t main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tc=1;//cin >> tc;
  while(tc--) _();
  return 0;
}

Compilation message

autobahn.cpp: In function 'void _()':
autobahn.cpp:44:7: warning: unused variable 'cur' [-Wunused-variable]
   44 |   int cur = 0;
      |       ^~~

Subtask #1
20.0 / 20.0

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

Subtask #2
30.0 / 30.0

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

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 2 ms 508 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 1 ms 336 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Correct 2 ms 336 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Correct 2 ms 336 KB Output is correct
19 Correct 2 ms 760 KB Output is correct
20 Correct 1 ms 336 KB Output is correct
21 Incorrect 253 ms 44452 KB Output isn't correct
22 Halted 0 ms 0 KB -