QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#382297	#7782. Ursa Minor	nguyentunglam	WA	82ms	486936kb	C++17	2.3kb	2024-04-08 11:27:27	2024-04-08 11:27:27

Judging History

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

[2024-04-08 11:27:27]
评测

测评结果：WA
用时：82ms
内存：486936kb

查看

[2024-04-08 11:27:27]
提交

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 = 1;

long long pw[N], f[N], a[N], sum[T1 + 10][N / T2 + 10];

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 << endl;
        cout << (hs == 0 ? "Yes\n" : "No\n");
      }
      else {
        cout << 1 << endl;
      }
    }
  }
}

Source code, Language: C++17

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 0ms

memory: 482840kb

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

input:

output:

Yes

result:

ok "Yes"

Test #3:

score: -100

Wrong Answer

time: 82ms

memory: 486936kb

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'