QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#560405 | #9250. Max GCD | duckindog | WA | 33ms | 5696kb | C++23 | 2.3kb | 2024-09-12 15:35:17 | 2024-09-12 15:35:23 |
Judging History
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'