結果

問題 No.2933 Range ROT Query
ユーザー amesyuamesyu
提出日時 2024-09-06 08:27:37
言語 C++23
(gcc 12.3.0 + boost 1.83.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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 2 ms
6,816 KB
testcase_02 AC 2 ms
6,820 KB
testcase_03 AC 2 ms
6,816 KB
testcase_04 AC 2 ms
6,816 KB
testcase_05 AC 3 ms
6,816 KB
testcase_06 AC 2 ms
6,816 KB
testcase_07 AC 2 ms
6,820 KB
testcase_08 AC 3 ms
6,820 KB
testcase_09 AC 2 ms
6,816 KB
testcase_10 AC 2 ms
6,820 KB
testcase_11 AC 2 ms
6,820 KB
testcase_12 AC 1,059 ms
81,364 KB
testcase_13 AC 1,047 ms
81,284 KB
testcase_14 AC 1,050 ms
81,312 KB
testcase_15 AC 1,051 ms
81,228 KB
testcase_16 AC 1,054 ms
81,296 KB
testcase_17 AC 1,225 ms
81,244 KB
testcase_18 AC 1,262 ms
81,304 KB
testcase_19 AC 1,267 ms
81,328 KB
testcase_20 AC 1,262 ms
81,188 KB
testcase_21 AC 879 ms
81,236 KB
testcase_22 AC 886 ms
81,232 KB
testcase_23 AC 883 ms
81,316 KB
testcase_24 AC 870 ms
81,272 KB
testcase_25 AC 872 ms
81,320 KB
testcase_26 AC 1,436 ms
81,252 KB
testcase_27 AC 1,420 ms
81,268 KB
testcase_28 AC 1,435 ms
81,124 KB
testcase_29 AC 1,424 ms
81,304 KB
testcase_30 AC 1,428 ms
81,248 KB
testcase_31 AC 1,455 ms
81,284 KB
testcase_32 AC 1,167 ms
74,624 KB
testcase_33 AC 1,226 ms
43,648 KB
testcase_34 AC 1,300 ms
44,400 KB
testcase_35 AC 863 ms
44,248 KB
testcase_36 AC 1,355 ms
44,424 KB
testcase_37 AC 898 ms
44,988 KB
testcase_38 AC 884 ms
74,660 KB
testcase_39 AC 1,035 ms
45,024 KB
testcase_40 AC 1,118 ms
44,340 KB
testcase_41 AC 1,223 ms
76,292 KB
testcase_42 AC 988 ms
42,660 KB
testcase_43 AC 1,199 ms
43,660 KB
testcase_44 AC 1,366 ms
43,224 KB
testcase_45 AC 1,285 ms
75,616 KB
testcase_46 AC 1,429 ms
43,400 KB
testcase_47 AC 1,076 ms
44,076 KB
testcase_48 AC 919 ms
76,436 KB
testcase_49 AC 1,064 ms
76,504 KB
testcase_50 AC 922 ms
45,620 KB
testcase_51 AC 1,167 ms
74,748 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
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