QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#382293	#7782. Ursa Minor	nguyentunglam	WA	93ms	24132kb	C++17	2.2kb	2024-04-08 11:18:54	2024-04-08 11:18:55

Judging History

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

[2024-04-08 11:18:55]
评测

测评结果：WA
用时：93ms
内存：24132kb

查看

[2024-04-08 11:18:54]
提交

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[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 {
        cout << 14091 << 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: 15996kb

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: 2ms

memory: 13872kb

input:

output:

Yes

result:

ok "Yes"

Test #3:

score: -100

Wrong Answer

time: 93ms

memory: 24132kb

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:

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

result:

wrong answer 1st words differ - expected: 'Yes', found: 'No'