QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#280823#7782. Ursa Minorucup-team1198#WA 1267ms27640kbC++147.3kb2023-12-09 17:59:232023-12-09 17:59:23

Judging History

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

  • [2023-12-09 17:59:23]
  • 评测
  • 测评结果:WA
  • 用时:1267ms
  • 内存:27640kb
  • [2023-12-09 17:59:23]
  • 提交

answer

#pragma GCC optimize("Ofast,unroll-loops")

#include <map>
#include <set>
#include <array>
#include <cmath>
#include <deque>
#include <bitset>
#include <random>
#include <string>
#include <vector>
#include <cassert>
#include <complex>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>

using namespace std;

const int K = 179;
const int MAXN = 400400;

int n;

long long fenw[MAXN];

void add_fenw(int i, long long x) {
  for (; i < 2 * n; i = (i | (i + 1)))
    fenw[i] += x;
}

long long get(int i) {
  long long ans = 0;
  for (; i >= 0; i = (i & (i + 1)) - 1)
    ans += fenw[i];
  return ans;
}

long long get(int l, int r) {
  return get(r - 1) - get(l - 1);
}


int gcd(int a, int b) {
  while (b) {
    a %= b;
    swap(a, b);
  }
  return a;
}

int tree_gcd[(1 << 19) + 228];

void build(int v, int left, int right, vector<int>& A) {
  if (left + 1 == right) {
    tree_gcd[v] = A[left];
    return;
  }
  int mid = (left + right) / 2;
  build(2 * v + 1, left, mid, A);
  build(2 * v + 2, mid, right, A);
  tree_gcd[v] = gcd(tree_gcd[2 * v + 1], tree_gcd[2 * v + 2]);
}

int get_gcd(int v, int left, int right, int x, int y) {
  if (y <= left || right <= x)
    return 0;
  if (x <= left && right <= y)
    return tree_gcd[v];
  int mid = (left + right) / 2;
  return gcd(get_gcd(2 * v + 1, left, mid, x, y), get_gcd(2 * v + 2, mid, right, x, y));
}


const int MOD1 = 1e9 + 9;

int add1(int a, int b) {
  return a + b >= MOD1 ? a + b - MOD1 : a + b;
}

int sub1(int a, int b) {
  return a >= b ? a - b : a + MOD1 - b;
}

int mul1(int a, int b) {
  return (1ll * a * b) % MOD1;
}


const int MOD2 = 1e9 + 447;

int add2(int a, int b) {
  return a + b >= MOD2 ? a + b - MOD2 : a + b;
}

int sub2(int a, int b) {
  return a >= b ? a - b : a + MOD2 - b;
}

int mul2(int a, int b) {
  return (1ll * a * b) % MOD2;
}

const int BASE = 379;
int BASEPOW1[MAXN];
int BASEPOW2[MAXN];

pair<int, int> combine(pair<int, int> A, pair<int, int> B, int r_len) {
  return make_pair(add1(mul1(A.first, BASEPOW1[r_len]), B.first),
    add2(mul2(A.second, BASEPOW2[r_len]), B.second));
}

const pair<int, int> NONE(0, 0);

pair<int, int> cur_vals[MAXN];
pair<int, int> suff_hashes[MAXN];
pair<int, int> pref_hashes[MAXN];

pair<int, int> get_segm_hash(int left, int right) {
  int l = left / K + 1;
  int r = right / K;
  pair<int, int> ans = suff_hashes[left];
  for (int i = l; i < r; ++i)
    ans = combine(ans, suff_hashes[i * K], K);
  ans = combine(ans, pref_hashes[right], right - r * K + 1);
  return ans;
}

void recalc_block(int id) {
  id /= K;
  pair<int, int> cur_pref = NONE;
  for (int i = id * K; i < id * K + K; ++i) {
    cur_pref = combine(cur_pref, cur_vals[i], 1);
    pref_hashes[i] = cur_pref;
  }
  pair<int, int> cur_suff = NONE;
  for (int i = id * K + K - 1; i >= id * K; --i) {
    cur_suff = combine(cur_vals[i], cur_suff, id * K + K - i - 1);
    suff_hashes[i] = cur_suff;
  }
}

int main() {
#ifdef DEBUG
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
#else
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
#endif

  BASEPOW1[0] = 1;
  for (int i = 1; i < MAXN; ++i)
    BASEPOW1[i] = mul1(BASEPOW1[i - 1], BASE);

  BASEPOW2[0] = 1;
  for (int i = 1; i < MAXN; ++i)
    BASEPOW2[i] = mul1(BASEPOW2[i - 1], BASE);

  int m, q;
  cin >> n >> m >> q;
  vector<long long> A(n);
  for (int i = 0; i < n; ++i)
    cin >> A[i];
  vector<int> B(m);
  for (int i = 0; i < m; ++i)
    cin >> B[i];
  build(0, 0, m, B);
  vector<pair<pair<int, int>, int>> queries(q);
  vector<int> interesting;
  for (int i = 0; i < q; ++i) {
    char c;
    cin >> c;
    if (c == 'U') {
      int p, v;
      cin >> p >> v;
      --p;
      queries[i] = make_pair(make_pair(p, v), -1);
    } else {
      int l, r, s, t;
      cin >> l >> r >> s >> t;
      --l;
      --r;
      --s;
      --t;
      int k = gcd(r - l + 1, get_gcd(0, 0, m, s, t + 1));
      if (k <= K)
        interesting.emplace_back(k);
      queries[i] = make_pair(make_pair(l, r), k);
    }
  }
  vector<bool> ans(q);
  sort(interesting.begin(), interesting.end());
  interesting.resize(unique(interesting.begin(), interesting.end()) - interesting.begin());
  vector<long long> cur_a;
  for (int k : interesting) {
    cur_a = A;
    fill(fenw, fenw + 2 * n, 0);
    auto get_real_id = [k](int i) {
      return (i % k) * (n / k + 1) + i / k;
    };
    for (int i = 0; i < n; ++i) {
      add_fenw(get_real_id(i), cur_a[i] - (i == 0 ? 0 : cur_a[i - 1]));
    }
    for (int j = 0; j < q; ++j) {
      if (queries[j].second == -1) {
        // upd
        int i = queries[j].first.first;
        int x = queries[j].first.second;
        add_fenw(get_real_id(i), x - cur_a[i]);
        if (i + 1 < n)
          add_fenw(get_real_id(i + 1), cur_a[i] - x);
        cur_a[i] = x;
      } else if (queries[j].second == k) {
        // query
        int l = queries[j].first.first;
        int r = queries[j].first.second;
        ans[j] = true;
        for (int i = 1; i < k; ++i) {
          // l + i
          long long cur_sum = get(get_real_id(l + i), get_real_id(r + 1 - k + i) + 1);
          if (cur_sum != 0)
            ans[j] = false;
        }
        long long cur_sum = get(get_real_id(l), get_real_id(r + 1 - k) + 1) + (l == 0 ? 0 : cur_a[l - 1]) - cur_a[r];
        if (cur_sum != 0)
          ans[j] = false;
      }
    }
  }
  for (int i = 0; i < n; ++i) {
    cur_vals[i].first = (A[i] - (i == 0 ? 0 : A[i - 1]) + MOD1) % MOD1;
    cur_vals[i].second = (A[i] - (i == 0 ? 0 : A[i - 1]) + MOD2) % MOD2;
  }
  for (int i = 0; i < n; i += K)
    recalc_block(i);
  cur_a = A;
  for (int j = 0; j < q; ++j) {
    if (queries[j].second == -1) {
      // upd
      int i = queries[j].first.first;
      int x = queries[j].first.second;
      cur_vals[i].first = add1(cur_vals[i].first, (x - cur_a[i] + MOD1) % MOD1);
      cur_vals[i].second = add2(cur_vals[i].second, (x - cur_a[i] + MOD2) % MOD2);
      if (i + 1 < n) {
        cur_vals[i + 1].first = add1(cur_vals[i + 1].first, (cur_a[i] - x + MOD2) % MOD2);
        cur_vals[i + 1].second = add2(cur_vals[i + 1].second, (cur_a[i] - x + MOD2) % MOD2);
      }
      cur_a[i] = x;
      recalc_block(i);
      if ((i + 1) / K != i / K)
        recalc_block(i + 1);
    } else if (queries[j].second > K) {
      // query
      int l = queries[j].first.first;
      int r = queries[j].first.second;
      int k = queries[j].second;
      pair<int, int> total_hash = NONE;
      for (int i = l; i < r; i += k) {
        auto tmp = get_segm_hash(i, i + k - 1);
        total_hash.first = add1(total_hash.first, tmp.first);
        total_hash.second = add2(total_hash.second, tmp.second);
      }
      int delta = (l == 0 ? 0 : cur_a[l - 1]) - cur_a[r];
      total_hash.first = add1(total_hash.first, mul1((delta + MOD1) % MOD1, BASEPOW1[k - 1]));
      total_hash.second = add2(total_hash.second, mul2((delta + MOD2) % MOD2, BASEPOW2[k - 1]));
      ans[j] = total_hash == NONE;
    }
  }

  for (int i = 0; i < q; ++i) {
    if (queries[i].second != -1) {
      if (ans[i])
        cout << "Yes\n";
      else
        cout << "No\n";
    }
  }
  return 0;
}

详细

Test #1:

score: 100
Accepted
time: 3ms
memory: 13896kb

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: 3ms
memory: 15940kb

input:

1 1 1
0
1
Q 1 1 1 1

output:

Yes

result:

ok "Yes"

Test #3:

score: 0
Accepted
time: 262ms
memory: 16240kb

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: 231ms
memory: 19244kb

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: 200ms
memory: 19028kb

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: -100
Wrong Answer
time: 1267ms
memory: 27640kb

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:

wrong answer 128593rd words differ - expected: 'Yes', found: 'No'