QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#382292	#7782. Ursa Minor	nguyentunglam	WA	78ms	24100kb	C++17	2.2kb	2024-04-08 11:17:55	2024-04-08 11:17:56

Judging History

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

[2024-04-08 11:17:56]
评测

测评结果：WA
用时：78ms
内存：24100kb

查看

[2024-04-08 11:17:55]
提交

answer

#include<bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define endl "\n"
using namespace std;

const int N = 2e5 + 10, base = 100, mod = 1e9 + 7, T1 = 300, T2 = 300;

long long pw[N], f[N], a[N], sum[1010][1010];

int lg[N], rmq[20][N];

int b[N];

int n, m, q;

void update (int p, int v) {
  long long old = f[p];
  a[p] = v;
  f[p] = p > 1 ? a[p] - a[p - 1] : a[p] - a[n];
  for(int c = 1; c <= T1; c++) {
    sum[c][p / T2] += (f[p] - old) * pw[p % c];
  }
}

tuple<int, int, int, int> query[N];

int get_gcd (int l, int r) {
  int k = lg[r - l + 1];
  return __gcd(rmq[k][l], rmq[k][r - (1 << k) + 1]);
}

int32_t main() {
  #define task ""

  cin.tie(0) -> sync_with_stdio(0);

  if (fopen("task.inp", "r")) {
    freopen("task.inp", "r", stdin);
    freopen("task.out", "w", stdout);
  }

  if (fopen(task".inp", "r")) {
    freopen (task".inp", "r", stdin);
    freopen (task".out", "w", stdout);
  }

  cin >> n >> m >> q;

  pw[0] = 1;
  for(int i = 1; i <= n; i++) {
    pw[i] = pw[i - 1] * base % mod;
  }

  for(int i = 1; i <= n; i++) {
    cin >> a[i];
    update(i, a[i]);
  }

  for(int i = 2; i <= m; i++) lg[i] = lg[i / 2] + 1;

  for(int i = 1; i <= m; i++) cin >> rmq[0][i];

  for(int j = 1; j <= lg[m]; j++) for(int i = 1; i + (1 << j) - 1 <= m; i++) {
    rmq[j][i] = __gcd(rmq[j - 1][i], rmq[j - 1][i + (1 << j - 1)]);
  }

  while (q--) {
    char type; cin >> type;
    if (type == 'U') {
      int p, v; cin >> p >> v;
      update(p, v);
    }
    else {
      int x, y, u, v; cin >> x >> y >> u >> v;
      int c = __gcd(y - x + 1, get_gcd(u, v));
      long long hs = 0;
      if (c <= T1) {
        int st = x / T2;
        int ed = y / T2;
        for(int i = st + 1; i < ed; i++) hs += sum[c][i];
        if (st == ed) {
          for(int i = x; i <= y; i++) hs += f[i] * pw[i % c];
        }
        else {
          for(int i = x; i <= st * T2 + T2 - 1; i++) hs += f[i] * pw[i % c];
          for(int i = y; i >= ed * T2; i--) hs += f[i] * pw[i % c];
        }
        hs -= f[x] * pw[x % c];
        hs += (a[x] - a[y]) * pw[x % c];
        cout << (hs == 0 ? "Yes\n" : "No\n");
      }
      else {

      }
    }
  }
}

Source code, Language: C++17

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 2ms

memory: 15944kb

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: 11864kb

input:

output:

Yes

result:

ok "Yes"

Test #3:

score: -100

Wrong Answer

time: 78ms

memory: 24100kb

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
No
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
No
Yes
No
No
Yes
No
No
No
No
No
Yes
Yes
Yes
Yes
Yes
No
No
No
Yes
No
Yes
Yes
Yes
No
Yes
Y...

result:

wrong answer 25th words differ - expected: 'Yes', found: 'No'