QOJ.ac

QOJ

The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#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

This is the latest submission verdict.

[2024-04-08 11:27:27]
Judged

Verdict: WA
Time: 82ms
Memory: 486936kb

Show

[2024-04-08 11:27:27]
Submitted

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;
      }
    }
  }
}

源文件, 语言: C++17

詳細信息

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'