結果

問題 No.2154 あさかつの参加人数
コンテスト
ユーザー akinyan
提出日時 2022-12-09 21:52:27
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,002 ms / 2,000 ms
コード長 8,067 bytes
コンパイル時間 4,517 ms
コンパイル使用メモリ 265,304 KB
実行使用メモリ 7,152 KB
最終ジャッジ日時 2024-10-14 21:41:31
合計ジャッジ時間 24,551 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ch = char;
using ll = long long;
using ld = long double;
using db = double;
using st = string;
using vdb = vector<db>;
using vvdb = vector<vdb>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vvvl = vector<vvl>;
using vd = vector<ld>;
using vvd = vector<vd>;
using vs = vector<st>;
using vvs = vector<vs>;
using vc = vector<ch>;
using vvc = vector<vc>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vvvb = vector<vvb>;
const ll mod = 998244353;
const ll MOD = 1000000007;
const ll INF = 1000000000000000000LL;
using pall = pair<ll,ll>;
using vp = vector<pall>;
namespace my{
    void fix(){
      cout<<fixed<<setprecision(20);
    }
    vl fact,inv_fact,inv;
    void init(const ll MAX, ll m) {
        fact.resize(MAX);
        inv_fact.resize(MAX);
        inv.resize(MAX);
        fact[0] = 1;
        fact[1] = 1;
        inv[0] = 1;
        inv[1] = 1;
        inv_fact[0] = 1;
        inv_fact[1] = 1;
        for(int i=2; i<MAX; i++){
            fact[i] = fact[i - 1] * i % m;
            inv[i] = m - inv[m%i] * (m / i) % m;
            inv_fact[i] = inv_fact[i - 1] * inv[i] % m;
        }
    }
    ll nCk(ll n, ll k, ll m) {
        ll x = fact[n];
        ll y = inv_fact[n-k];
        ll z = inv_fact[k];
        if (n < k) return 0;
        if (n < 0 || k < 0) return 0;
        return x * ((y * z) % m) % m;
    }
    // RMQ：[0,n-1] について、区間ごとの最小値を管理する構造体
    //  set(int i, T x), build(): i番目の要素をxにセット。まとめてセグ木を構築する。O(n)
    //  update(i,x): i 番目の要素を x に更新。O(log(n))
    //  query(a,b): [a,b) での最小の要素を取得。O(log(n))
    //  find_rightest(a,b,x): [a,b) で x以下の要素を持つ最右位置を求める。O(log(n))
    //  find_leftest(a,b,x): [a,b) で x以下の要素を持つ最左位置を求める。O(log(n))
    template <typename T>
    struct RMQ {
        const T e = 0;
        function<T(T, T)> fx = [](T x1, T x2) -> T { return max(x1,x2); };
        ll n;
        vector<T> dat;
        RMQ(ll n_) : n(), dat(n_ * 4, e) {
            ll x = 1;
            while (n_ > x) {
                x *= 2;
            }
            n = x;
        }
     
        void set(ll i, T x) { dat[i + n - 1] = x; }
        void build() {
            for (ll k = n - 2; k >= 0; k--) dat[k] = fx(dat[2 * k + 1], dat[2 * k + 2]);
        }
     
        void update(ll i, T x) {
            i += n - 1;
            dat[i] = x;
            while (i > 0) {
                i = (i - 1) / 2;  // parent
                dat[i] = fx(dat[i * 2 + 1], dat[i * 2 + 2]);
            }
        }
     
        // the minimum element of [a,b)
        T query(ll a, ll b) { return query_sub(a, b, 0, 0, n); }
        T query_sub(ll a, ll b, ll k, ll l, ll r) {
            if (r <= a || b <= l) {
                return e;
            } else if (a <= l && r <= b) {
                return dat[k];
            } else {
                T nl = query_sub(a, b, k * 2 + 1, l, (l + r) / 2);
                T nr = query_sub(a, b, k * 2 + 2, (l + r) / 2, r);
                return fx(nl, nr);
            }
        }
     
        ll find_rightest(ll a, ll b, T x) { return find_rightest_sub(a, b, x, 0, 0, n); }
        ll find_leftest(ll a, ll b, T x) { return find_leftest_sub(a, b, x, 0, 0, n); }
        ll find_rightest_sub(ll a, ll b, T x, ll k, ll l, ll r) {
            if (dat[k] > x || r <= a || b <= l) {  // 自分の値がxより大きい or [a,b)が[l,r)の範囲外ならreturn a-1
                return a - 1;
            } else if (k >= n - 1) {  // 自分が葉ならその位置をreturn
                return (k - (n - 1));
            } else {
                int nr = find_rightest_sub(a, b, x, 2 * k + 2, (l + r) / 2, r);
                if (nr != a - 1) {  // 右の部分木を見て a-1 以外ならreturn
                    return nr;
                } else {  // 左の部分木を見て値をreturn
                    return find_rightest_sub(a, b, x, 2 * k + 1, l, (l + r) / 2);
                }
            }
        }
        ll find_leftest_sub(ll a, ll b, T x, ll k, ll l, ll r) {
            if (dat[k] > x || r <= a || b <= l) {  // 自分の値がxより大きい or [a,b)が[l,r)の範囲外ならreturn b
                return b;
            } else if (k >= n - 1) {  // 自分が葉ならその位置をreturn
                return (k - (n - 1));
            } else {
                ll nl = find_leftest_sub(a, b, x, 2 * k + 1, l, (l + r) / 2);
                if (nl != b) {  // 左の部分木を見て b 以外ならreturn
                    return nl;
                } else {  // 右の部分木を見て値をreturn
                    return find_leftest_sub(a, b, x, 2 * k + 2, (l + r) / 2, r);
                }
            }
        }
    };
    ll modpow(ll a, ll n, ll m) {
        ll res = 1;
        while (n > 0) {
            if (n & 1) res = res * a % m;
            a = a * a % m;
            n >>= 1;
        }
        return res;
    }
    ll modinv(ll a, ll b, ll m) {
        // a/bを返す
        return modpow(b, m - 2, m) * a % m;
    }
    vl zaatu(vl A){
        //0はじまり
        vl B=A;
        sort(B.begin(), B.end());
        B.erase(unique(B.begin(), B.end()), B.end());
        vl R(A.size());
        ll asize=A.size();
        for(int i=0; i<asize; i++){
            R[i] = lower_bound(B.begin(), B.end(), A[i]) - B.begin();
        }
        return R;
    }
    bool sosuu(ll a){
        for(ll i=2; i*i<=a; i++){
            if(a%i==0){
                return false;
            }
        }
        return true;
    }
    vl yakusuu(ll a){
        vl ANS;
        for(ll i=1; i*i<=a; i++){
            if(a%i==0){
                ANS.push_back(i);
                if(a/i!=i){
                    ANS.push_back(a/i);
                }
            }
        }
        sort(ANS.begin(),ANS.end());
        return ANS;
    }
    ll yakusuu_kosuu(ll a){
        ll ans=0;
        for(ll i=1; i*i<=a; i++){
            if(a%i==0){
                ans++;
                if(a/i!=i){
                    ans++;
                }
            }
        }
        return ans;
    }
    vp bunkai(ll N){
        vp res;
        for (long long a = 2; a * a <= N; ++a) {
            if (N % a != 0) continue;
            long long ex = 0;
            while (N % a == 0) {
                ++ex;
                N /= a;
            }
            res.push_back({a, ex});
        }
        if (N != 1) res.push_back({N, 1});
        return res;
    }
    ll ran(ll A,ll B){
        random_device a;
        mt19937 b(a());
        uniform_int_distribution<> c(A,B);
        return c(b);
    }
    ll pow(ll a, ll n){
        ll ans=1;
        for(int i=0; i<n; i++){
            ans*=a;
        }
        return ans;
    }
    ll digsum(ll n) {
        ll res = 0;
        while(n > 0) {
            res += n%10;
            n /= 10;
        }
        return res;
    }
    vector<pair<char, int>> encode(const string& str) {
        int n = (int)str.size();
        vector<pair<char, int>> ret;
        for (int l = 0; l < n;) {
            int r = l + 1;
            for (; r < n && str[l] == str[r]; r++) {};
            ret.push_back({str[l], r - l});
            l = r;
        }
        return ret;
    }
    string decode(const vector<pair<char, int>>& code) {
        string ret = "";
        for (auto p : code) {
            for (int i = 0; i < p.second; i++) {
                ret.push_back(p.first);
            }
        }
        return ret;
    }
    template <typename T>
    T max0(T a){
         return max(a,T(0)); 
    }
    template <typename T>
    T min0(T a){
        return min(a,T(0));
    }
}

int main(){
    ll N,M;
    cin>>N>>M;
    vl A(N+2);
    for(int i=0; i<M; i++){
        ll a,b;
        cin>>a>>b;
        A[b]++;
        A[a+1]--;
    }
    for(int i=1; i<=N; i++){
        A[i]+=A[i-1];
    }
    for(int i=N; i>0; i--){
        cout<<A[i]<<endl;
    }
}
0