Submission #1116098

#	Time	Username	Problem	Language	Result	Execution time	Memory
1116098		epicci23	Autobahn (COI21_autobahn)	C++17	50 / 100	253 ms	44452 KiB

autobahn

#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 (stderr)

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

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