test/yukicoder/yuki_945.test.cpp

• View this file on GitHub
• Last update: 2022-07-17 07:03:54+09:00
• Problem: https://yukicoder.me/problems/no/945

Depends on

• 双対スパーステーブル (data_structure/sequence/dual_sparse_table.hpp)

Code

#define PROBLEM "https://yukicoder.me/problems/no/945"
#include <bits/stdc++.h>
using namespace std;
const int INF = 1000000;
#include "../../data_structure/sequence/dual_sparse_table.hpp"
int main(){
  int N, M;
  cin >> N >> M;
  dual_sparse_table<pair<int, int>> ST(N, [](pair<int, int> a, pair<int, int> b){return min(a, b);}, make_pair(INF, 0));
  for (int i = 0; i < M; i++){
    int L, R;
    char T;
    cin >> L >> R >> T;
    L--;
    if (T == 'Y'){
      ST.apply(L, R, make_pair(i, 0));
    }
    if (T == 'K'){
      ST.apply(L, R, make_pair(i, 1));
    }
    if (T == 'C'){
      ST.apply(L, R, make_pair(i, 2));
    }
  }
  vector<pair<int, int>> A = ST.get();
  vector<int> ans(3, 0);
  for (int i = 0; i < N; i++){
    if (A[i].first != INF){
      ans[A[i].second]++;
    }
  }
  cout << ans[0] << ' ' << ans[1] << ' ' << ans[2] << endl;
}

#line 1 "test/yukicoder/yuki_945.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/945"
#include <bits/stdc++.h>
using namespace std;
const int INF = 1000000;
#line 2 "data_structure/sequence/dual_sparse_table.hpp"
/**
 * @brief 双対スパーステーブル
*/
template <typename T>
struct dual_sparse_table{
  vector<vector<T>> ST;
  function<T(T, T)> f;
  T E;
  dual_sparse_table(){
  }
  dual_sparse_table(int N, function<T(T, T)> f, T E): f(f), E(E){
    int LOG = 32 - __builtin_clz(N);
    ST = vector<vector<T>>(LOG, vector<T>(N, E));
  }
  dual_sparse_table(vector<T> &A, function<T(T, T)> f, T E): f(f), E(E){
    int N = A.size();
    int LOG = 32 - __builtin_clz(N);
    ST = vector<vector<T>>(LOG, vector<T>(N, E));
    ST[0] = A;
  }
  void apply(int L, int R, T x){
    if (L == R){
      return;
    }
    int d = 31 - __builtin_clz(R - L);
    ST[d][L] = f(ST[d][L], x);
    ST[d][R - (1 << d)] = f(ST[d][R - (1 << d)], x);
  }
  vector<T> get(){
    int LOG = ST.size();
    int N = ST[0].size();
    for (int i = LOG - 2; i >= 0; i--){
      for (int j = 0; j < N - (1 << i); j++){
        ST[i][j] = f(ST[i][j], ST[i + 1][j]);
        ST[i][j + (1 << i)] = f(ST[i][j + (1 << i)], ST[i + 1][j]);
      }
    }
    return ST[0];
  }
};
#line 6 "test/yukicoder/yuki_945.test.cpp"
int main(){
  int N, M;
  cin >> N >> M;
  dual_sparse_table<pair<int, int>> ST(N, [](pair<int, int> a, pair<int, int> b){return min(a, b);}, make_pair(INF, 0));
  for (int i = 0; i < M; i++){
    int L, R;
    char T;
    cin >> L >> R >> T;
    L--;
    if (T == 'Y'){
      ST.apply(L, R, make_pair(i, 0));
    }
    if (T == 'K'){
      ST.apply(L, R, make_pair(i, 1));
    }
    if (T == 'C'){
      ST.apply(L, R, make_pair(i, 2));
    }
  }
  vector<pair<int, int>> A = ST.get();
  vector<int> ans(3, 0);
  for (int i = 0; i < N; i++){
    if (A[i].first != INF){
      ans[A[i].second]++;
    }
  }
  cout << ans[0] << ' ' << ans[1] << ' ' << ans[2] << endl;
}

Back to top page