結果

問題 No.945 YKC饅頭
コンテスト
ユーザー Gandalfr
提出日時 2023-04-06 10:33:50
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 327 ms / 2,000 ms
コード長 7,744 bytes
コンパイル時間 2,607 ms
コンパイル使用メモリ 206,212 KB
最終ジャッジ日時 2025-02-11 23:16:41
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 74
権限があれば一括ダウンロードができます

ソースコード

diff # 

#line 1 "freespace/main.cpp"
#include <bits/stdc++.h>
#line 1 "library/gandalfr/data_structure/dual_segment_tree.hpp"


#line 7 "library/gandalfr/data_structure/dual_segment_tree.hpp"
#include <optional>

/*
 * verify : https://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=7627486#1
 */
template<class T>
class dual_segment_tree{
  private:
    int n, vec_size;
    const T e;
    const std::function< T(T, T) > op;
    std::vector<T> v;

  public:
    // 要素の配列 vec で初期化
    dual_segment_tree(const std::vector<T> &vec, const std::function< T(T, T) > &f, T _e) : vec_size(vec.size()), op(f), e(_e) {
        int siz = vec.size();
        n = 1;
        while(n < siz) n *= 2;
        v.resize(2 * n - 1, e);
        for(int i = 0; i < siz; i++) v[i + n - 1] = vec[i];
    }

    // 長さ siz の単位元の配列で初期化
    dual_segment_tree(int siz, const std::function< T(T, T) > &f, T _e) : vec_size(siz), op(f), e(_e) {
        n = 1;
        while(n < siz) n *= 2;
        v.resize(2 * n - 1, e);
    }

    // pos 番目の値を得る
    T get(int pos){
        pos += n - 1;
        T ret = v[pos];
        while(pos > 0){
            pos = (pos - 1) / 2;
            ret = op(ret, v[pos]);
        }
        return ret;
    }

    // [l, r) に action を作用する 
    void act(int l, int r, T action){
        assert(0 <= l && l <= r && r <= vec_size);
        if(l == r) return;
        act(l, r, 0, 0, n, action);
    }

    void print(){
        for(int i = 0; i < vec_size; i++){
            std::cout << get(i) << (i == vec_size - 1 ? "" : " ");
        }
        std::cout << std::endl;
    }

  private:
    void act(int a, int b, int k, int l, int r, T action){
        if(r <= a || b <= l) return;
        if(a <= l && r <= b){
            v[k] = op(v[k], action);
            return;
        }
        act(a, b, 2 * k + 1, l, (l + r) / 2, action);
        act(a, b, 2 * k + 2, (l + r) / 2, r, action);
    }
};

template<class T>
struct RAQ_dual_segment_tree : public dual_segment_tree<T>{
    RAQ_dual_segment_tree(int size) : RAQ_dual_segment_tree<T>::dual_segment_tree(size, [](T a, T b){ return a + b; }, 0) {};
    RAQ_dual_segment_tree(const std::vector<T> &vec) : RAQ_dual_segment_tree<T>::dual_segment_tree(vec, [](T a, T b){ return a + b; }, 0) {};
};

/* 
 * verify : https://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=7627473#1
 */
template<class T>
class RUQ_dual_segment_tree{
  private:
    int n, tm = 0, vec_size;
    std::vector<std::pair<int, T>> v;

  public:
    // 要素の配列 vec で初期化
    RUQ_dual_segment_tree(const std::vector<T> &vec) : vec_size(vec.size()) {
        int siz = vec.size();
        n = 1;
        while(n < siz) n *= 2;
        v.resize(2 * n - 1);
        for(auto &x : v) x.first = -1;
        for(int i = 0; i < siz; i++) v[i + n - 1].second = vec[i];
    }

    // 長さ siz の単位元の配列で初期化
    RUQ_dual_segment_tree(int siz) : vec_size(siz) {
        n = 1;
        while(n < siz) n *= 2;
        v.resize(2 * n - 1);
        for(auto &x : v) x.first = -1;
    }

    // pos 番目の値を得る
    T get(int pos){
        pos += n - 1;
        std::pair<int, T> ret = v[pos];
        while(pos > 0){
            pos = (pos - 1) / 2;
            ret = std::max(ret, v[pos]);
        }
        return ret.second;
    }

    // [l, r) に action を作用する 
    void act(int l, int r, T action){
        assert(0 <= l && l <= r && r <= vec_size);
        if(l == r) return;
        act(l, r, 0, 0, n, {tm, action});
        tm++;
    }

    void print(){
        for(int i = 0; i < vec_size; i++){
            std::cout << get(i) << (i == vec_size - 1 ? "" : " ");
        }
        std::cout << std::endl;
    }

  private:
    void act(int a, int b, int k, int l, int r, std::pair<int, T> action){
        if(r <= a || b <= l) return;
        if(a <= l && r <= b){
            v[k] = std::max(v[k], action);
            return;
        }
        act(a, b, 2 * k + 1, l, (l + r) / 2, action);
        act(a, b, 2 * k + 2, (l + r) / 2, r, action);
    }
};





#line 1 "library/gandalfr/other/io_supporter.hpp"


#line 7 "library/gandalfr/other/io_supporter.hpp"

std::ostream &operator<<(std::ostream &dest, __uint128_t value) {
	std::ostream::sentry s(dest);
	if (s) {
		__uint128_t tmp = value;
		char buffer[128];
		char *d = std::end(buffer);
		do {
			--d;
			*d = "0123456789"[tmp % 10];
			tmp /= 10;
		} while (tmp != 0);
		int len = std::end(buffer) - d;
		if (dest.rdbuf()->sputn(d, len) != len) {
			dest.setstate(std::ios_base::badbit);
		}
	}
	return dest;
}

std::ostream &operator<<(std::ostream &dest, __int128_t value) {
	std::ostream::sentry s(dest);
	if (s) {
		__int128_t tmp = value < 0 ? -value : value;
		char buffer[128];
		char *d = std::end(buffer);
		do {
			--d;
			*d = "0123456789"[tmp % 10];
			tmp /= 10;
		} while (tmp != 0);
		if (value < 0) {
			--d;
			*d = '-';
		}
		int len = std::end(buffer) - d;
		if (dest.rdbuf()->sputn(d, len) != len) {
			dest.setstate(std::ios_base::badbit);
		}
	}
	return dest;
}

template<typename T>
std::ostream &operator<<(std::ostream &os, const std::vector<T> &v) {
    for(int i=0; i<(int)v.size(); i++) os << v[i] << (i+1 != (int)v.size() ? " " : "");
    return os;
}
template<typename T>
std::istream &operator>>(std::istream &is, std::vector<T> &v){
    for(T &in : v) is >> in;
    return is;
}

template<typename T1, typename T2>
std::ostream &operator<<(std::ostream &os, const std::pair<T1, T2>& p) {
    os << p.first << " " << p.second;
    return os;
}
template<typename T1, typename T2>
std::istream &operator>>(std::istream &is, std::pair<T1, T2> &p) {
    is >> p.first >> p.second;
    return is;
}

template<typename T>
std::ostream &operator<<(std::ostream &os, std::queue<T> v) {
    int N = v.size();
    for(int i=0; i<N; i++) {
        os << v.front() << (i+1 != N ? " " : "");
        v.pop();
    }
    return os;
}
template<typename T>
std::istream &operator>>(std::istream &is, std::queue<T> &v) {
    for(T &in : is) v.push(is);
    return is;
}

template<typename T>
std::ostream &operator<<(std::ostream &os, const std::set<T> &st) {
    for(const T &x : st){
        std::cout << x << " ";
    }
    return os;
}

template<typename T>
std::ostream &operator<<(std::ostream &os, const std::multiset<T> &st) {
    for(const T &x : st){
        std::cout << x << " ";
    }
    return os;
}



#line 4 "freespace/main.cpp"
using namespace std;
using ll = long long;
const int INF = 1001001001;
const int MAXINT = std::numeric_limits<int>::max();
const int MININT = std::numeric_limits<int>::min();
const ll INFL = 1001001001001001001;
const ll MAXLL = std::numeric_limits<ll>::max();
const ll MINLL = std::numeric_limits<ll>::min();
const ll MOD  = 1000000007;
const ll _MOD = 998244353;
#define rep(i, j, n) for(ll i = (ll)(j); i < (ll)(n); i++)
#define rrep(i, j, n) for(ll i = (ll)(n-1); i >= (ll)(j); i--)
#define fore(i,a) for(auto &i : a)
#define all(a) (a).begin(),(a).end()
#define lr(a, l, r) (a).begin()+(l),(a).begin()+(r)
#define LF cout << endl

int main(void){

    /*ifstream in("input.txt");
    cin.rdbuf(in.rdbuf());
    ofstream fout("output.txt");*/

    //input

    int N, M;
    cin >> N >> M;
    dual_segment_tree<pair<int, char>> seg(N, [](pair<int, char> a, pair<int, char> b){ return max(a, b); }, {MININT, 'S'});
    rep(i,0,M){
        int l, r;
        char c;
        cin >> l >> r >> c;
        l--;
        seg.act(l, r, {-i, c});
    }

    //calculate

    vector<int> cnt(3, 0);
    rep(i,0,N){
        if(seg.get(i).second == 'Y') cnt[0]++;
        if(seg.get(i).second == 'K') cnt[1]++;
        if(seg.get(i).second == 'C') cnt[2]++;
    }
    cout << cnt << endl;


}
0