寝癖頭の解法

小学生の目線から、勉強中の覚え書きを投稿、更新していきます。

AtCoder Problems in C++ #C - イベント巡り (Event Hopping)

JOI 2020/2021 二次予選 過去問から、その提出コードの解答例です。
AtCoderとは、コンテストを通じて、プログラミングやアルゴリズムを学習するサービスです。
atcoder.jp
プログラミングコンテストとは、「与えられた問題をいかに素早く、正確に」解くことができるかを競うものです。
競技プログラミング」を略して、「競プロ」などと呼ばれています。

#C - イベント巡り (Event Hopping)

atcoder.jp

僕が作成、提出したコードは、以下のとおりです。

/*
AtCoder Problems in C++
#C - イベント巡り (Event Hopping)
https://atcoder.jp/contests/joi2021yo2/tasks/joi2021_yo2_c
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
pair<long,int> l[2<<17];
int dp[2][2<<17];
int main(void){
  int n;
  long d,k;
  cin>>n>>d>>k;
  for(int i=0;i<n;i++){
    cin>>l[i].second>>l[i].first;
    l[i].second--;
  }
  sort(l,l+n);
  for(int i=0;i<n;i++){
    auto[s,p]=l[i];
    for(int q=0;q<2;q++){
      int t=dp[q][i]+(p==q);
      dp[q][i+1]=max(dp[q][i+1],t);
      int j=upper_bound(l,l+n,make_pair(s+d+k*t,2))-l;
      dp[q^1][j]=max(dp[q^1][j],t);
    }
  }
  cout<<max(dp[0][n],dp[1][n])<<endl;
  return 0;
}