結果

問題 No.2933 Range ROT Query
コンテスト
ユーザー amesyu
提出日時 2024-09-06 08:27:37
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,455 ms / 3,000 ms
コード長 2,234 bytes
コンパイル時間 6,673 ms
コンパイル使用メモリ 318,228 KB
実行使用メモリ 81,364 KB
最終ジャッジ日時 2024-10-02 00:25:56
合計ジャッジ時間 56,350 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 50
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function 'int main()':
main.cpp:99:9: warning: 't' may be used uninitialized [-Wmaybe-uninitialized]
   99 |         if(s < t) std::cout << "Lesser" << std::endl;
      |         ^~
main.cpp:94:42: note: 't' was declared here
   94 |         int s = imos.prod(0, q+1)%sigma, t;
      |                                          ^

ソースコード

diff # 

#include <bits/stdc++.h>
#include <atcoder/all>

const int sigma = 26;
using Monoid = std::array<int, sigma>;

Monoid op(Monoid x, Monoid y) {
  Monoid arr;
  for(int i=0;i<sigma;++i) {
    arr[i] = x[i] + y[i];
  }
  return arr;
}

Monoid e() {
  Monoid x;
  for(int i=0;i<sigma;++i) x[i] = 0;
  return x;
}

Monoid mapping(int f, Monoid x) {
  Monoid arr;
  f %= sigma;
  if(f < sigma) f += sigma;
  for(int i=0;i<sigma;++i) {
    arr[(i+f)%sigma] = x[i];
  }
  return arr;
}

bool f(Monoid x) {
  int sum = std::accumulate(x.begin(), x.end(), 0);
  return sum == x[0];
}

// Dual Segment Tree
int zero() { return 0; }
int add(int f, int g) { return f + g; }

int main() {
  std::string S, T;
  std::cin >> S >> T;
  int N = (int)std::min(S.size(), T.size());

  std::vector<Monoid> init(N);

  for(int i=0;i<N;++i) {
    init[i][(sigma+S[i]-T[i])%sigma]++;
  }
  
  atcoder::lazy_segtree<Monoid, op, e, int, mapping, add, zero> seg(init);
  atcoder::segtree<int, add, zero> imos(N + 1);

  for(int i=0;i<N;++i) {
    imos.set(i, imos.get(i) + (S[i]-'a')%sigma);
	imos.set(i+1, imos.get(i+1) - (S[i]-'a')%sigma);
  } 

  int Q;
  std::cin >> Q;
  while(Q--) {
    int query_t;
    std::cin >> query_t;

    if (query_t == 1) {
      int l, r, x;
      std::cin >> l >> r >> x;
      if(N < l) continue;
      r = std::min(r, N);
      seg.apply(l-1, r, x);
      imos.set(l-1, imos.get(l-1) + x);
      imos.set(r, imos.get(r) - x);

    } else if (query_t == 2) {
      int l, r, x;
      std::cin >> l >> r >> x;
      if(N < l) continue;
      r = std::min(r, N);
      seg.apply(l-1, r, -x);

    } else {
      int p, q;
      std::cin >> p; p--;
      q = seg.max_right<f>(p);
      if(q == N) {
        if(S.size() == T.size()) {
          std::cout << "Equals" << std::endl;
        } else if(S.size() < T.size()) {
          std::cout << "Lesser" << std::endl;
        } else {
          std::cout << "Greater" << std::endl;
        }
      } else {
        int s = imos.prod(0, q+1)%sigma, t;
		Monoid rot = seg.get(q);
		for(int i=0;i<sigma;++i) {
			if(rot[i]) t = (sigma + s - i) % sigma;
		}
        if(s < t) std::cout << "Lesser" << std::endl;
        else std::cout << "Greater" << std::endl;
      }
    }
  }
}
0