QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#560405#9250. Max GCDduckindogWA 33ms5696kbC++232.3kb2024-09-12 15:35:172024-09-12 15:35:23

Judging History

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

  • [2024-09-12 15:35:23]
  • 评测
  • 测评结果:WA
  • 用时:33ms
  • 内存:5696kb
  • [2024-09-12 15:35:17]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

const int N = 150'000 + 10,
          MAX = 1'000'000,
          S = 500;
int n, q;
int a[N];
struct Query { 
  int l, r, idx;
  friend istream& operator >> (istream& is, auto& rhs) { 
    return is >> rhs.l >> rhs.r;
  }
} query[N];
int answer[N];

vector<int> pos[MAX + 10];
vector<pair<int, int>> save[N];

int block[S + 10];
int ma[N];

int32_t main() { 
  cin.tie(0)->sync_with_stdio(0);

  cin >> n >> q;
  for (int i = 1; i <= n; ++i) cin >> a[i];
  for (int i = 1; i <= q; ++i) cin >> query[i], query[i].idx = i;

  for (int i = 1; i <= n; ++i) pos[a[i]].push_back(i); 

  { //init
    for (int value = MAX; value >= 1; --value) { 
      vector<int> totalPos;
      for (int multiple = value; multiple <= MAX; multiple += value) { 
        for (const auto& x : pos[multiple]) totalPos.push_back(x);
      }
      if (totalPos.size() <= 2) continue;

      sort(totalPos.begin(), totalPos.end());

      vector<pair<int, int>> all;
      for (auto it = totalPos.begin(); it != totalPos.end(); ++it) {
        if (*it == totalPos[0] || *it == totalPos.end()[-1]) continue;
        int l = *(it - 1);
        if (2 * *it - l <= totalPos.back()) all.push_back({l, 2 * *it - l});
      }

      sort(all.begin(), all.end(), [&](const auto& a, const auto& b) { 
        return a.second > b.second;
      });

      int it = totalPos.size() - 1;
      for (const auto& [l, r] : all) { 
        while (it && totalPos[it - 1] >= r) it -= 1;
        save[l].push_back({totalPos[it], value});
      }
    }
  }

  sort(query + 1, query + q + 1, [&](const auto& a, const auto& b) { return a.l < b.l; });

  auto upd = [&](int p, int value) { 
    int bl = (p - 1) / S + 1;
    block[bl] = max(block[bl], value);
  };
  auto que = [&](int x) { 
    int ret = 0;
    
    int bl = (x - 1) / S + 1;
    for (int i = 1; i < bl; ++i) ret = max(ret, block[i]);
    for (int i = bl * S - S + 1; i <= x; ++i) ret = max(ret, ma[i]);

    return ret;
  };

  int it = n;
  for (int i = q; i >= 1; --i) { 
    const auto& [l, r, idx] = query[i];

    while (it >= l) 
      for (const auto& [r, value] : save[it--]) upd(r, value);

    answer[idx] = que(r);
  }
  
  for (int i = 1; i <= q; ++i) cout << answer[i] << "\n";
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 33ms
memory: 5696kb

input:

8 8
8 24 4 6 6 7 3 3
1 5
2 6
3 7
5 8
4 8
1 3
2 5
3 8

output:

0
0
0
0
0
0
0
0

result:

wrong answer 1st words differ - expected: '4', found: '0'