QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#553500 | #9250. Max GCD | PetroTarnavskyi | TL | 1ms | 3536kb | C++23 | 2.0kb | 2024-09-08 14:15:26 | 2024-09-08 14:15:26 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second
typedef long long LL;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef double db;
const int N = 1e6 + 47;
const int N2 = 2e7 + 47;
struct Query
{
int l, r, val;
bool operator<(const Query& q)
{
if (l != q.l)
return l > q.l;
return val > q.val;
}
};
VI idx[N];
Query qe[N2];
int qh = 0;
struct Fenwick
{
int n;
VI t;
Fenwick(int _n = 0): n(_n), t(n, 1) {}
void upd(int i, int x)
{
for (; i < n; i |= i + 1)
t[i] = max(t[i], x);
}
int query(int i)
{
int ans = 1;
for (; i >= 0; i = (i & (i + 1)) - 1)
ans = max(ans, t[i]);
return ans;
}
};
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n, q;
cin >> n >> q;
VI a(n);
FOR (i, 0, n)
{
cin >> a[i];
idx[a[i]].PB(i);
}
int mx = *max_element(ALL(a));
FOR (d, 2, mx + 1)
{
VI poses;
for (int j = d; j <= mx; j += d)
poses.insert(poses.end(), ALL(idx[j]));
sort(ALL(poses));
FOR (i, 1, SZ(poses))
{
int dis = poses[i] - poses[i - 1];
int j = lower_bound(ALL(poses), poses[i] + dis) - poses.begin();
if (j != SZ(poses))
{
if (gcd(a[poses[i - 1]], gcd(a[poses[i]], a[poses[j]])) == d)
qe[qh++] = {poses[i - 1], poses[j], d};
}
}
}
FOR (i, 0, q)
{
int l, r;
cin >> l >> r;
l--, r--;
if (r - l > 1)
qe[qh++] = {l, r, -i - 1};
}
sort(qe, qe + qh);
Fenwick fn(n);
VI ans(q);
FOR (i, 0, qh)
{
int r = qe[i].r;
int val = qe[i].val;
//cerr << i << ' ' << r << ' ' << val << '\n';
if (val > 0)
fn.upd(r, val);
else
ans[-val - 1] = fn.query(r);
}
FOR (i, 0, q)
{
cout << ans[i] << '\n';
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3536kb
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:
4 2 3 1 3 4 2 3
result:
ok 8 tokens
Test #2:
score: -100
Time Limit Exceeded
input:
150000 100000 982800 554400 665280 982800 997920 720720 786240 831600 997920 982800 786240 982800 942480 831600 887040 665280 831600 960960 786240 982800 786240 942480 665280 831600 942480 665280 982800 960960 960960 997920 720720 960960 960960 665280 982800 665280 982800 942480 786240 997920 554400...