結果
| 問題 |
No.2933 Range ROT Query
|
| コンテスト | |
| ユーザー |
 Pedro Vinicius
|
| 提出日時 | 2024-10-24 04:44:39 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 7,060 bytes |
| コンパイル時間 | 4,516 ms |
| コンパイル使用メモリ | 277,728 KB |
| 実行使用メモリ | 435,600 KB |
| 最終ジャッジ日時 | 2024-10-24 04:44:55 |
| 合計ジャッジ時間 | 14,318 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 10 TLE * 1 -- * 39 |
ソースコード
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define int long long
#define all(x) x.begin(), x.end()
using namespace __gnu_pbds; using namespace std;
template<class T> using ordered_set = tree<T, null_type , less<T> , rb_tree_tag , tree_order_statistics_node_update>; template<class T> using ordered_multiset = tree<T, null_type , less_equal<T> , rb_tree_tag , tree_order_statistics_node_update>; typedef long long ll; typedef pair<int, int> ii; typedef tuple<int, int, int> iii; typedef tuple<int, int, int, int> iiii; typedef vector<int> vi;
const ll oo = 1987654321987654321;
template<class It> void db(It b, It e) { for (auto it = b; it != e; it++) cout << *it << ' '; cout<< endl; } template<typename A> istream& operator>>(istream& fin, vector<A>& v) { for (auto it = v.begin(); it != v.end(); ++it) fin >> *it; return fin; } template<typename A, typename B> istream& operator>>(istream& fin, pair<A, B>& p){ fin >> p.first >> p.second; return fin; } template<typename T> void chmin(T &a, T b){ a = min(a, b); } template<typename T> void chmax(T &a, T b){ a = max(a, b); } template <typename T, typename S> ostream& operator<<(ostream& os, const pair<T, S>& v) { os << "(" << v.first << "," << v.second << ")"; return os; }
const int P = 1e9 + 7;
mt19937 rmg((int)chrono::steady_clock::now().time_since_epoch().count());
int b = uniform_int_distribution<int>(0, P - 1)(rmg);
ll expbin(ll a, ll b) {
if (b == 0) return 1;
if (b & 1) return (a%P * expbin(a, b - 1))%P;
ll tmp = expbin(a, b / 2);
return (tmp * tmp)%P;
}
struct seghash{
struct item {
int isValid = 0;
vi val;
int sum = 0, sz = 0;
item() : val(26){
}
item operator+(item oth) {
item c = item();
c.sum = 0;
for (int i=0; i < 26; i++){
c.val[i] = (this->val[i] + (expbin(b, this->sz) * oth.val[i])%P)%P;
}
c.sum = (this->sum + expbin(b, this->sz) * oth.sum)%P;
c.sz = this->sz + oth.sz;
return c;
}
};
vector<item> seg;
int tamseg;
seghash(string &str){
int n = str.size();
seg.resize(4 * n);
tamseg = n;
buildseg(str, 0, 0, tamseg);
}
void buildseg(string &a, int pos, int lx, int rx) {
if (rx - lx == 1) {
if (lx < (int)a.size()) {
int id = a[lx] - 'a';
// cout << "Para " << a[lx] << " id: " << id << "\n";
fill(all(seg[pos].val), 0LL);
seg[pos].val[id] = 1;
seg[pos].sz = 1;
seg[pos].sum = a[lx];
}
return;
}
int mid = lx + (rx - lx) / 2;
buildseg(a, 2 * pos + 1, lx, mid);
buildseg(a, 2 * pos + 2, mid, rx);
seg[pos] = seg[2 * pos + 1] + seg[2 * pos + 2];
}
void push(int pos, int lx, int rx) {
if (rx - lx == 1) return;
while (seg[pos].isValid) {
for (int dx = 1; dx <= 2; dx++) {
(((seg[2 * pos + dx].sum -= ('z' - 'a') * seg[2 * pos + dx].val[25]) %= P) += P) %= P;
for (int i=0; i < 25; i++){
seg[2 * pos + dx].sum += seg[2 * pos + dx].val[i];
seg[2 * pos + dx].sum %= P;
}
vi tmp = seg[2 * pos + dx].val;
for (int i=0; i < 26; i++){
seg[2 * pos + dx].val[(i + 1) % 26] = tmp[i];
}
seg[2 * pos + dx].isValid++;
seg[2 * pos + dx].isValid %= 26;
}
seg[pos].isValid--;
}
seg[pos].isValid = 0;
}
void rot(int l, int r, int pos, int lx, int rx) {
push(pos, lx, rx);
if (lx >= r || rx <= l) return;
if (lx >= l && rx <= r) {
//cout << "[" << lx << "," << rx << ")\n";
// cout << "antes: " << seg[pos].sum << "\n";
(((seg[pos].sum -= (('z' - 'a') * seg[pos].val[25])) %= P) += P) %= P;
// cout << "-->: " << seg[pos].sum << "\n";
for (int i=0; i < 25; i++){
seg[pos].sum += seg[pos].val[i];
// cout << "adding: " << seg[pos].val[i] << "\n";
seg[pos].sum %= P;
}
vi tmp = seg[pos].val;
for (int i=0; i < 26; i++){
seg[pos].val[(i + 1) % 26] = tmp[i];
}
//cout << "depois: " << seg[pos].sum << "\n";
seg[pos].isValid++;
return;
}
int mid = lx + (rx - lx) / 2;
rot(l, r, 2 * pos + 1, lx, mid);
rot(l, r, 2 * pos + 2, mid, rx);
seg[pos] = seg[2 * pos + 1] + seg[2 * pos + 2];
}
void rot(int l, int r){
rot(l, r, 0, 0, tamseg);
}
item getseg(int l, int r, int pos, int lx, int rx) {
push(pos, lx, rx);
if (lx >= r || rx <= l) return item();
if (lx >= l && rx <= r) return seg[pos];
int mid = lx + (rx - lx) / 2;
return getseg(l, r, 2 * pos + 1, lx, mid) +
getseg(l, r, 2 * pos + 2, mid, rx);
}
int get(int l, int r){
return getseg(l, r, 0, 0, tamseg).sum;
}
string to_string(int l, int r){
string ans = "";
for (int i=l; i < r; i++){
ans += get(i, i + 1);
}
return ans;
}
};
signed main(){
cin.tie(0)->sync_with_stdio(0);
string s, t;
cin >> s >> t;
seghash segs(s), segt(t);
int q;
cin >> q;
while (q--){
int op;
cin >> op;
if (op == 1){
int l, r, x;
cin >> l >> r >> x;
--l;
// cout << "[" << l << "," << r << ")\n";
while (x--){
// cout << "[" << l << "," << r << ")\n";
segs.rot(l, r);
}
// cout << "s: " << segs.to_string(0, s.size()) << "\n";
}else if (op == 2){
int l, r, x;
cin >> l >> r >> x;
--l;
// cout << "[" << l << "," << r << ")\n";
while (x--){
segt.rot(l, r);
}
// cout << "t: " << segt.to_string(0, t.size()) << "\n";
}else{
int p;
cin >> p;
--p;
if (segs.get(p, s.size()) == segt.get(p, t.size())){
if (s.size() > t.size()){
cout << "Greater\n";
}else if (s.size() < t.size()){
cout << "'Lesser\n";
}else{
cout << "Equals\n";
}
continue;
}
int l = p - 1; // good
int r = min(s.size(), t.size()); // bad
while (r - l > 1){
int mid = l + (r - l)/2;
if (segs.get(p, mid + 1) == segt.get(p, mid + 1)) l = mid;
else r = mid;
}
// cout << "s': " << segs.to_string(p, s.size()) << "\n";
// cout << "t': " << segt.to_string(p, t.size()) << "\n";
if (segs.get(r, r + 1) > segt.get(r, r + 1)){
cout << "Greater\n";
}else{
cout << "Lesser\n";
}
}
}
}