#856716 (C++17) No.945 YKC饅頭

提出ソース

結果

問題	No.945 YKC饅頭
ユーザー	Gandalfr
提出日時	2023-04-06 10:33:50
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	287 ms / 2,000 ms
コード長	7,744 bytes
コンパイル時間	2,307 ms
コンパイル使用メモリ	206,836 KB
実行使用メモリ	7,584 KB
最終ジャッジ日時	2024-04-10 08:58:05
合計ジャッジ時間	11,736 ms
ジャッジサーバーID （参考情報）	judge4 / judge3

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 6,816 KB
testcase_01	AC	1 ms 6,816 KB
testcase_02	AC	2 ms 6,940 KB
testcase_03	AC	2 ms 6,940 KB
testcase_04	AC	2 ms 6,944 KB
testcase_05	AC	2 ms 6,944 KB
testcase_06	AC	2 ms 6,944 KB
testcase_07	AC	3 ms 6,940 KB
testcase_08	AC	2 ms 6,940 KB
testcase_09	AC	2 ms 6,940 KB
testcase_10	AC	2 ms 6,940 KB
testcase_11	AC	2 ms 6,944 KB
testcase_12	AC	2 ms 6,940 KB
testcase_13	AC	2 ms 6,944 KB
testcase_14	AC	3 ms 6,944 KB
testcase_15	AC	2 ms 6,944 KB
testcase_16	AC	2 ms 6,940 KB
testcase_17	AC	2 ms 6,940 KB
testcase_18	AC	2 ms 6,944 KB
testcase_19	AC	2 ms 6,940 KB
testcase_20	AC	2 ms 6,940 KB
testcase_21	AC	2 ms 6,944 KB
testcase_22	AC	2 ms 6,944 KB
testcase_23	AC	2 ms 6,944 KB
testcase_24	AC	3 ms 6,944 KB
testcase_25	AC	2 ms 6,940 KB
testcase_26	AC	3 ms 6,940 KB
testcase_27	AC	2 ms 6,944 KB
testcase_28	AC	2 ms 6,944 KB
testcase_29	AC	2 ms 6,940 KB
testcase_30	AC	1 ms 6,940 KB
testcase_31	AC	20 ms 6,940 KB
testcase_32	AC	27 ms 6,940 KB
testcase_33	AC	85 ms 7,432 KB
testcase_34	AC	144 ms 6,940 KB
testcase_35	AC	233 ms 7,500 KB
testcase_36	AC	143 ms 6,940 KB
testcase_37	AC	139 ms 6,944 KB
testcase_38	AC	136 ms 6,944 KB
testcase_39	AC	52 ms 6,940 KB
testcase_40	AC	58 ms 7,472 KB
testcase_41	AC	29 ms 6,944 KB
testcase_42	AC	192 ms 6,940 KB
testcase_43	AC	119 ms 6,944 KB
testcase_44	AC	182 ms 7,344 KB
testcase_45	AC	207 ms 6,940 KB
testcase_46	AC	17 ms 6,940 KB
testcase_47	AC	140 ms 6,940 KB
testcase_48	AC	29 ms 6,944 KB
testcase_49	AC	77 ms 6,940 KB
testcase_50	AC	220 ms 6,940 KB
testcase_51	AC	287 ms 7,300 KB
testcase_52	AC	281 ms 7,512 KB
testcase_53	AC	281 ms 7,456 KB
testcase_54	AC	276 ms 7,440 KB
testcase_55	AC	279 ms 7,332 KB
testcase_56	AC	36 ms 7,356 KB
testcase_57	AC	37 ms 7,292 KB
testcase_58	AC	160 ms 7,280 KB
testcase_59	AC	200 ms 7,396 KB
testcase_60	AC	93 ms 7,284 KB
testcase_61	AC	173 ms 7,476 KB
testcase_62	AC	165 ms 7,284 KB
testcase_63	AC	41 ms 7,304 KB
testcase_64	AC	95 ms 7,372 KB
testcase_65	AC	82 ms 7,296 KB
testcase_66	AC	75 ms 7,512 KB
testcase_67	AC	126 ms 7,584 KB
testcase_68	AC	93 ms 7,268 KB
testcase_69	AC	52 ms 7,336 KB
testcase_70	AC	58 ms 7,456 KB
testcase_71	AC	58 ms 7,432 KB
testcase_72	AC	113 ms 7,496 KB
testcase_73	AC	184 ms 7,544 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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;


}

yukicoder

結果

テストケース

ソースコード