QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#648129#7470. WBLTguosoun60 523ms18608kbC++172.5kb2024-10-17 17:10:572024-10-17 17:10:58

Judging History

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

  • [2024-10-17 17:10:58]
  • 评测
  • 测评结果:60
  • 用时:523ms
  • 内存:18608kb
  • [2024-10-17 17:10:57]
  • 提交

answer

#include <bits/stdc++.h>
template <class T>
void chkmax(T &x, const T &y) {
  if (x < y) x = y;
}
using ull = unsigned long long;
const int N = 100100;

template <int N>
struct bitset {
  static const int B = 64;
  std::array<ull, (N - 1) / B + 2> a;
  bitset() : a() {}
  void set(int i) { a[i >> 6] |= 1ull << (i & 63); }
  void reset(int i) { a[i >> 6] &= ~(1ull << (i & 63)); }
  ull gets(int i) {
    if (i >= N) return 0;
    return a[i >> 6] >> (i & 63) |
           ((i & 63) ? a[(i >> 6) + 1] << (B - (i & 63)) : 0);
  }
  int calc(int k) {
    int ret = 0;
    for (int i = 0; i < k; i += B) {
      ull cur = -1;
      if (k - i < B) cur &= (1ull << (k - i)) - 1;
      for (int j = i, c = 1; cur &= gets(j); j += k, c++) chkmax(ret, c);
    }
    return ret;
  }
};

int main() {
  const int B = 30;
  std::cin.tie(0)->sync_with_stdio(0);
  int n, m;
  std::cin >> n;
  std::vector<int> a(n);
  for (auto &x : a) std::cin >> x;
  std::cin >> m;
  std::vector<int> ans(m);
  std::vector<std::tuple<int, int, int, int *>> q(m);
  for (int i = 0; auto &[l, r, b, it] : q) {
    std::cin >> l >> r >> b, l--, r--;
    it = &ans[i++];
  }
  std::sort(q.begin(), q.end(), [](auto x, auto y) -> bool {
    auto [l1, r1, b1, it1] = x;
    auto [l2, r2, b2, it2] = y;
    if (l1 / 400 == l2 / 400) return (r1 < r2) ^ ((l1 / 400) & 1);
    return l1 < l2;
  });
  for (int b = 1; b < B; b++) {
    std::vector<std::array<int, N>> cnt(b);
    std::vector<std::bitset<N>> vis(b);
    for (auto &t : vis) t.set();
    auto add = [&](int i) {
      if (!cnt[a[i] % b][a[i] / b]++) vis[a[i] % b][a[i] / b] = 0;
    };
    auto remove = [&](int i) {
      if (!--cnt[a[i] % b][a[i] / b]) vis[a[i] % b][a[i] / b] = 1;
    };
    int l = 1, r = 0;
    for (auto [ql, qr, qb, it] : q) {
      if (qb != b) continue;
      while (r < qr) add(++r);
      while (l > ql) add(--l);
      while (r > qr) remove(r--);
      while (l < ql) remove(l++);
      for (int i = 0; i < b; i++) {
        chkmax<int>(*it, vis[i]._Find_first());
      }
    }
  }
  std::array<int, N> cnt{};
  bitset<N> vis;
  auto add = [&](int i) {
    if (!cnt[a[i]]++) vis.set(a[i]);
  };
  auto remove = [&](int i) {
    if (!--cnt[a[i]]) vis.reset(a[i]);
  };
  int l = 1, r = 0;
  for (auto [ql, qr, qb, it] : q) {
    if (qb < B) continue;
    while (r < qr) add(++r);
    while (l > ql) add(--l);
    while (r > qr) remove(r--);
    while (l < ql) remove(l++);
    *it = vis.calc(qb);
  }
  for (int i : ans) std::cout << i << '\n';
}

詳細信息

Subtask #1:

score: 30
Accepted

Test #1:

score: 30
Accepted
time: 14ms
memory: 15348kb

input:

1000
233 991 831 426 140 881 289 287 957 886 561 109 305 469 961 577 683 593 277 601 181 255 100 997 161 619 632 413 987 811 357 635 99 809 888 511 945 881 261 434 851 311 21 641 508 701 661 158 696 560 577 501 951 786 909 238 546 573 617 236 270 705 786 353 651 296 353 720 261 429 855 176 977 57 50...

output:

3
3
2
4
4
0
3
2
2
2
2
2
1
4
2
2
3
3
2
2
5
3
1
2
2
2
2
1
3
3
2
3
1
3
5
2
0
4
2
1
5
2
2
2
2
2
2
2
2
2
2
6
1
3
2
1
2
2
1
0
0
2
2
2
3
2
1
3
2
2
2
3
2
4
0
2
2
2
3
3
2
2
0
2
3
2
2
2
4
1
2
2
4
3
2
2
5
3
2
2
1
1
2
2
2
6
3
2
1
2
3
1
1
0
3
3
2
2
2
1
2
2
2
3
3
3
2
4
3
2
1
5
2
4
2
1
1
2
2
3
2
2
2
3
3
2
2
1
2
2
...

result:

ok 1000 numbers

Subtask #2:

score: 30
Accepted

Test #2:

score: 30
Accepted
time: 197ms
memory: 18376kb

input:

100000
241 721 861 909 540 928 171 159 637 60 145 227 110 975 766 220 311 761 191 980 887 793 773 957 625 61 994 606 465 625 598 667 181 197 15 826 136 499 199 331 621 327 945 726 197 997 681 641 465 805 211 531 333 505 483 345 612 241 376 700 5 338 661 777 241 412 118 585 121 1 398 658 855 598 300 ...

output:

2
6
17
3
2
2
2
2
2
3
2
2
11
2
7
2
4
2
2
3
9
5
2
2
4
2
2
4
2
2
2
2
7
8
2
2
9
2
3
4
4
2
3
2
2
3
2
2
1
2
2
2
13
167
11
2
3
0
2
2
2
2
2
2
3
3
4
7
2
3
2
4
2
5
2
23
2
3
2
0
2
2
2
4
2
4
2
2
4
2
2
5
2
91
5
2
2
2
3
3
2
2
3
2
0
2
3
2
2
2
3
2
5
2
2
5
2
77
21
2
7
3
2
3
2
2
2
2
13
2
4
4
2
2
9
2
2
2
3
13
3
5
2
4
...

result:

ok 100000 numbers

Test #3:

score: 30
Accepted
time: 523ms
memory: 18608kb

input:

100000
6 8 75 85 89 8 88 56 1 64 37 6 28 16 87 74 57 51 5 72 39 85 100 54 1 97 77 40 97 95 65 56 37 13 44 23 68 49 85 79 27 57 75 81 1 26 61 45 97 31 85 61 51 37 30 53 1 51 11 57 49 22 40 67 49 85 53 89 1 97 88 57 79 6 61 61 36 75 71 53 81 91 91 1 91 1 29 67 47 81 81 37 71 14 17 26 65 59 36 7 97 77 ...

output:

5
2
4
2
4
4
4
0
6
2
2
7
8
2
3
2
4
8
2
2
2
8
2
2
2
0
4
1
3
2
2
4
10
2
3
0
2
13
2
2
3
2
2
2
5
2
3
2
0
3
6
2
0
2
3
2
3
34
2
2
7
2
2
8
2
2
10
2
0
0
2
2
2
3
2
2
2
3
2
5
2
2
2
2
2
2
5
10
34
2
2
3
3
2
3
2
2
2
2
20
4
13
4
4
2
50
5
3
2
2
10
2
3
2
3
4
2
12
3
7
12
5
2
5
3
4
2
2
3
2
2
2
2
2
2
2
4
2
2
2
2
2
0
13...

result:

ok 100000 numbers

Test #4:

score: 30
Accepted
time: 279ms
memory: 18520kb

input:

100000
6 7 6 6 1 1 9 1 7 6 3 4 6 6 5 1 8 6 6 3 2 7 1 3 6 3 9 2 1 7 6 10 7 5 7 7 3 1 1 6 1 3 3 2 5 1 9 2 1 10 3 7 1 1 7 3 4 6 5 5 10 8 7 3 9 5 4 9 5 1 2 1 10 1 7 1 9 2 9 5 1 1 9 9 1 10 7 1 6 5 3 9 3 6 10 7 6 9 7 3 9 1 1 7 6 9 5 3 4 1 9 7 9 3 8 10 1 6 7 9 4 1 5 1 1 5 1 1 6 5 7 3 9 7 7 5 6 3 4 7 6 5 5 ...

output:

2
4
2
2
2
0
0
2
0
5
2
0
2
2
2
0
3
2
0
2
2
0
2
1
3
2
4
0
0
1
2
4
2
2
0
2
0
0
2
0
2
0
4
2
2
2
2
0
2
2
3
2
2
5
4
3
0
2
2
2
3
3
2
1
2
0
1
2
2
2
4
2
2
2
0
2
4
0
2
2
3
4
2
0
3
2
2
4
2
2
0
0
4
4
1
2
2
2
3
2
2
2
0
2
2
5
0
2
4
1
2
2
2
2
2
2
0
2
2
2
2
0
4
2
2
5
0
2
4
2
2
5
2
0
2
4
2
0
4
2
2
2
2
2
0
2
5
2
4
2
...

result:

ok 100000 numbers

Subtask #3:

score: 0
Time Limit Exceeded

Test #5:

score: 0
Time Limit Exceeded

input:

99917
24947 3268 49683 43610 87927 86331 16017 19557 72137 16689 28231 87819 9481 2403 18661 8145 86091 90410 54635 10896 53999 43367 95987 23733 17359 94625 81763 44331 63663 6075 20784 94229 61578 3890 95047 32681 39491 33139 51629 34573 859 31797 22897 7647 52199 17817 6311 46787 20619 81037 5374...

output:


result: