Submission #1116103

#	Time	Username	Problem	Language	Result	Execution time	Memory
1116103		epicci23	Autobahn (COI21_autobahn)	C++17	0 / 100	1 ms	504 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+1);
    zip.push_back(zip[i]+X-1);
  }
 
  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;
  };

  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 - 1;
    ans = max(ans, T[Get(r)] - T[Get(l)-1]);
    l = u - X + 1, r = u;
    ans = max(ans, T[Get(r)] - T[Get(l)-1]);
  }
 
  cout << ans << '\n';
}
 
int32_t main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tc=1;//cin >> tc;
  while(tc--) _();
  return 0;
}

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