超初心者が競プロに挑む

初心者からの競プロ練習記録

ABC017C解いてみた

一つ取らない宝石を決めた時、もっともスコアが良い取り方はその宝石を取らない区間を持つ遺跡をできるだけ訪れた時だから、これは遺跡で集められる宝石の右端がその宝石より小さい遺跡すべてと、左端がその宝石より大きい遺跡すべてを訪れれば良い。遺跡で集められる宝石の両端でソートして点数の累積和を調べておけば、これはO(log(n))でもとまるから、全体ではO(Mlog(n))でもとまる。
詰まったところ
std::pairの比較でデフォルトの比較演算子ではstd::pairのfirstとsecondをともに利用して辞書順にするということをやっていた。これはstd::pairのfirstだけで比較したい時たまに面倒くさいことになるので下記のような関数を用意しておけば良い。

#include <cstdio>
#include <utility>
#include <algorithm>
#include <functional>

using namespace std;

typedef pair<int,int> P;

bool compOnFirst(const P& a, const P&b) {
  return a.first < b.first;
}

int N,M;
P ls[100010];
P rs[100010];
int INF=5000*200010;
int main() {
  scanf("%d%d", &N, &M);
  for(int i=0;i<N;++i) {
    int l,r,s;
    scanf("%d%d%d", &l,&r,&s);
    ls[i] = P(l,s);
    rs[i] = P(r,s);
  }
  sort(ls, ls+N, compOnFirst);
  sort(rs, rs+N, compOnFirst);
  for(int i=0;i<N-1;++i) {
    ls[i+1].second += ls[i].second;
    rs[i+1].second += rs[i].second;
  }
  int score=-1;
  for(int i=1;i<=M;++i) {
    int current = 0;
    auto last=upper_bound(rs, rs + N, P(i - 1,0), compOnFirst);
    if(last != rs) {
      current += (last-1)->second;
    }
    auto first = lower_bound(ls, ls + N, P(i + 1,0), compOnFirst);
    if(first!=(ls+N)) {
      current += (ls + N - 1)->second - (first - 1)->second;
    }

    score = max(score, current);
  }
  printf("%d\n", score);
  return 0;
}