ABC014 -C - AtColor

imos法みたいなことをやる。みたいなっていうかそのもの？

問題

atcoder.jp

考えたこと

全部の色の絵の具について購入してもいい人の人数を入れる箱を用意しておく。クエリで与えられる「購入してもいい色の範囲」について、その箱をプラスしていけば良さそう。

→ でもそれだと時間が足りないはず。たとえば、0 ~ 1000000の絵の具を買っていいという人が100000人いたら？

まずは先頭と終わりだけ＋１、ー１を入れておいて、購入してもいい人リストを頭からナメていけば良さそう。

解答

#include <bits/stdc++.h>

using namespace std;

#define rep(i,n)      for(long long(i)=0;(i)<(n);(i)++)
#define kiriage(a,b)  ((a)+(b)-1)/(b)

int main(){

    long s = 1000000;
    vector<long> ank(s + 1,0);
    
    long n;
    cin >> n;    
    rep(i,n){
        long lhs,rhs;
        cin >> lhs >> rhs;

        ank[lhs] += 1;
        ank[rhs + 1] -= 1;
    }

    long ans = 0;
    rep(i,s){
        ank[i + 1] = ank[i] + ank[i + 1];
    }

    long pop = 0;
    rep(i,s + 1){
        if(pop < ank[i]){
            pop = ank[i];
        }
    }

    cout << pop << endl;
    return 0;
}

感想

今だったら緑diffくらい？ひょっとしたら茶色かも。