QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#386744#7782. Ursa MinorSamponYWWA 554ms275868kbC++144.8kb2024-04-11 19:47:492024-04-15 23:33:24

Judging History

你现在查看的是最新测评结果

  • [2024-04-15 23:33:24]
  • 管理员手动重测该提交记录
  • 测评结果:WA
  • 用时:554ms
  • 内存:275868kb
  • [2024-04-11 19:47:49]
  • 提交

answer

#include <bits/stdc++.h>
#define db double
#define il inline
#define re register
#define ll long long
#define ui unsigned
#define ull ui ll
#define i128 __int128
#define pii pair<int, int>
#define fi first
#define se second
#define eb emplace_back
#define SZ(v) (int)v.size()
#define ALL(v) v.begin(), v.end()
#define mems(v, x) memset(v, x, sizeof(v))
#define memc(a, b) memcpy(a, b, sizeof(a))
#define FOR(i, L, R) for(re int i = (L); i <= (R); ++i)
#define ROF(i, R, L) for(re int i = (R); i >= (L); --i)
#define LS i << 1, l, mid
#define RS i << 1 | 1, mid + 1, r
#define popc(x) __builtin_popcount(x)
using namespace std;
bool pDEB, DEB; int tim;
#define N 200005
const int B = 200;
#define P 998244353
il int add(int x, int y) {return x + y < P ? x + y : x + y - P;}
il void addr(int &x, int y) {(x += y) >= P && (x -= P);}
int be[N], L[N], R[N], pw[N];
int n, m, q, a[N], b[N], c[N];
struct sma {
  int B, v[N], s[N];
  il void build(int k) {
    B = k;
    FOR(i, 1, n) {
      v[i] = 1ll * pw[i % B] * c[i] % P;
      addr(s[be[i]], v[i]);
    }
  }
  il void upd(int x, int k) {
    k = 1ll * k * pw[x % B] % P;
    addr(v[x], k), addr(s[be[x]], k);
  }
  il int query(int l, int r) {
    int a = be[l], b = be[r], ns = 0;
    if(a == b) {FOR(i, l, r) addr(ns, v[i]); return ns;}
    FOR(i, l, R[a]) addr(ns, v[i]);
    FOR(i, a + 1, b - 1) addr(ns, s[i]);
    FOR(i, L[b], r) addr(ns, v[i]);
    return ns;
  }
} T[B + 5];
struct info {
  int v, L;
} v[N], s[N], pre[N], suf[N];
il info merge(info A, info B) {
  return {(A.v + 1ll * pw[A.L] * B.v) % P, A.L + B.L};
}
namespace big {
  il void reb(int t) {
    info k = {0, 0};
    FOR(i, L[t], R[t])
      k = merge(k, v[i]), pre[i] = k;
    s[t] = k, k = {0, 0};
    ROF(i, R[t], L[t])
      k = merge(v[i], k), suf[i] = k;
  }
  il void build() {
    FOR(i, 1, n) v[i] = {c[i], 1};
    FOR(i, 1, be[n]) reb(i);
  }
  il void upd(int x, int k) {addr(v[x].v, k), reb(be[x]);}
  il info query(int l, int r) {
    // if(DEB) cout << "query=" << l << "+" << r << ",";
    if(l > r) return {0, 0}; info k = {0, 0};
    if(be[l] == be[r]) {
      // if(DEB) cout << "brt,";
      FOR(i, l, r) k = merge(k, v[i]); return k;}
    // if(DEB) cout << "nb,";
    k = merge(k, suf[l]);
    FOR(i, be[l] + 1, be[r] - 1) k = merge(k, s[i]);
    k = merge(k, pre[r]); return k;
  }
}
il void upd(int x, int k) {
  int d = (k - c[x] + P) % P; c[x] = k;
  FOR(i, 1, B) T[i].upd(x, d); big::upd(x, d);
}
namespace rmq {
  int st[20][N];
  il void build() {
    FOR(i, 1, m) st[0][i] = b[i];
    FOR(i, 1, 19) FOR(j, 1, m - (1 << i) + 1)
      st[i][j] = __gcd(st[i - 1][j], st[i - 1][j + (1 << i - 1)]);
  }
  il int query(int l, int r) {
    int t = __lg(r - l + 1);
    return __gcd(st[t][l], st[t][r - (1 << t) + 1]);
  }
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  cin >> n >> m >> q;
  FOR(i, 1, n) cin >> a[i];
  pDEB = n == 2e5 && a[1] == 793134805;
  FOR(i, 1, n) c[i] = add(a[i % n + 1], P - a[i]);
  FOR(i, 1, m) cin >> b[i]; rmq::build();
  pw[0] = 1; FOR(i, 1, n) pw[i] = 19260817ll * pw[i - 1] % P;
  FOR(i, 1, n) {
    be[i] = (i - 1) / B + 1, R[be[i]] = i;
    if(be[i] != be[i - 1]) L[be[i]] = i;
  }
  FOR(i, 1, B) T[i].build(i); big::build();
  tim = 0;
  while(q--) {
    char op; cin >> op;
    if(op == 'U') {
      int x, v; cin >> x >> v, a[x] = v;
      upd(x, add(a[x % n + 1], P - a[x]));
      --x; if(!x) x = n;
      upd(x, add(a[x % n + 1], P - a[x]));
    }
    else {
      ++tim;
      DEB = pDEB && tim == 49;
      int l, r, s, t; cin >> l >> r >> s >> t;
      if(l == r) {cout << "Yes\n"; continue;}
      int g = __gcd(r - l + 1, rmq::query(s, t)), ns = 0;
      if(DEB) cout << l << "," << r << ",";
      // if(DEB && tim == 49) cout << g << "," << B << " ";
      if(g <= B) ns = add(T[g].query(l, r - 1), 1ll * pw[r % g] * add(a[l], P - a[r]) % P);
      else {
        if(DEB) {
          cout << "nm,";
          FOR(i, l, r - 1) addr(ns, 1ll * pw[(i - l) % g] * add(a[i + 1], P - a[i]) % P);
          addr(ns, 1ll * pw[(r - l) % g] * add(a[r], P - a[l]) % P);
        }
        else {
          // FOR(i, l, r) addr(ns, 1ll * pw[(i - l) % g] * add(a[(i - l) % g + 1 + l - 1], P - a[i]) % P);
        while(l + g - 1 <= r - 1) {
          auto k = big::query(l, l + g - 1);
          addr(ns, k.v), l += g;
        }
        auto k = big::query(l, r - 1);
        // if(DEB) cout << k.L << ",";
        // if(k.L != g) k = merge(k, {add(a[l], P - a[r]), 1}), addr(ns, k.v);
        // else addr(ns, k.v), addr(ns, add(a[l], P - a[r]));
        k = merge(k, {add(a[l], P - a[r]), 1}), addr(ns, k.v);
        }
      }
      // if(DEB) cout << ns << ",";
      if(!ns) cout << "Yes\n"; else cout << "No\n";
    }
  }
  cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
  return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 174808kb

input:

6 4 5
1 1 4 5 1 4
3 3 2 4
Q 1 5 1 2
Q 2 5 3 4
U 5 2
Q 1 6 1 2
Q 2 5 3 4

output:

Yes
No
No
Yes

result:

ok 4 tokens

Test #2:

score: 0
Accepted
time: 0ms
memory: 178872kb

input:

1 1 1
0
1
Q 1 1 1 1

output:

Yes

result:

ok "Yes"

Test #3:

score: 0
Accepted
time: 508ms
memory: 179572kb

input:

2000 2000 200000
1 1 2 0 0 2 0 2 0 0 0 0 0 2 2 1 2 0 0 2 2 2 1 0 1 2 1 2 0 0 1 1 1 2 0 0 2 2 2 2 0 2 0 0 2 1 2 0 0 1 2 2 1 0 2 0 0 0 1 2 2 1 2 2 0 0 1 1 1 0 0 2 0 0 1 1 0 2 2 2 1 0 0 1 0 1 2 2 2 1 1 2 2 1 2 1 0 2 2 3 1 3 2 3 1 0 1 2 0 1 1 1 0 2 2 3 2 0 3 2 3 3 1 2 3 1 2 0 1 0 3 1 0 0 2 0 1 2 1 3 2 2...

output:

Yes
Yes
No
Yes
Yes
No
No
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
Yes
Yes
No
Yes
Yes
No
No
No
No
No
Yes
No
No
No
Yes
Yes
No
Yes
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
Yes
No
Yes
Yes
Yes
No
No
Yes
No
Yes
No
No
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
Yes
Yes
No...

result:

ok 100554 tokens

Test #4:

score: 0
Accepted
time: 183ms
memory: 181856kb

input:

1 200000 200000
998244353
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

output:

Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
...

result:

ok 100240 tokens

Test #5:

score: 0
Accepted
time: 180ms
memory: 184484kb

input:

6 131072 200000
0 0 0 0 1000000000 1000000000
4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 ...

output:

Yes
Yes
Yes
No
No
No
Yes
No
No
No
No
No
Yes
Yes
No
Yes
No
Yes
Yes
Yes
No
No
No
No
No
No
No
Yes
No
No
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
No
No
No
Yes
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
Yes
Yes
No
Yes
N...

result:

ok 100021 tokens

Test #6:

score: 0
Accepted
time: 554ms
memory: 273156kb

input:

200000 200000 200000
490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877...

output:

No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
Yes
Yes
Yes
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
Yes
Yes
No
No
No
No
No
No
No
No
N...

result:

ok 187340 tokens

Test #7:

score: 0
Accepted
time: 475ms
memory: 275868kb

input:

200000 200000 200000
360543531 360543531 360543531 360543531 360543531 360543531 360543531 360543531 360543531 360543531 360543531 360543531 360543531 360543531 360543531 360543531 360543531 360543531 360543531 360543531 360543531 360543531 360543531 360543531 360543531 360543531 360543531 360543531...

output:

Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
...

result:

ok 199985 tokens

Test #8:

score: -100
Wrong Answer
time: 433ms
memory: 275552kb

input:

200000 200000 200000
793134805 922104801 158394038 993313213 77527653 992889267 148461787 499165677 132176015 189185554 783374975 332147281 923925325 371040161 393285793 437388761 138662855 212488140 265392646 498903298 578518594 550390771 960084339 408548934 56106823 814997309 456913457 300689692 1...

output:

No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
42166,58785,nm,No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
N...

result:

wrong answer 49th words differ - expected: 'Yes', found: '42166,58785,nm,No'