QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#618657#9250. Max GCDucup-team1766WA 2481ms719384kbC++202.3kb2024-10-07 02:28:002024-10-07 02:28:01

Judging History

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

  • [2024-10-07 02:28:01]
  • 评测
  • 测评结果:WA
  • 用时:2481ms
  • 内存:719384kb
  • [2024-10-07 02:28:00]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 150005;
const int MAXV = 1000005;
vector<int> divisors[MAXV];
vector<pair<int, int>> intervals[MAXN];
vector<int> inds[MAXV];

struct Tree {
    typedef int T;
    static constexpr T unit = 0;
    T f(T a, T b) { return max(a, b); } // (any associative fn)
    vector<T> s; int n;
    Tree(int n = 0, T def = unit) : s(2*n, def), n(n) {}
    void update(int pos, T val) {
        pos += n;
        for (s[pos] = f(s[pos], val); pos /= 2;)
            s[pos] = f(s[pos * 2], s[pos * 2 + 1]);
    }
    T query(int b, int e) { // query [b, e)
        T ra = unit, rb = unit;
        for (b += n, e += n; b < e; b /= 2, e /= 2) {
            if (b % 2) ra = f(ra, s[b++]);
            if (e % 2) rb = f(s[--e], rb);
        }
        return f(ra, rb);
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    for (int i = 1; i < MAXV; i++) {
        for (int j = i; j < MAXV; j += i) {
            divisors[j].push_back(i);
        }
    }

    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        for (int divisor : divisors[a[i]]) {
            inds[divisor].push_back(i);
        }
    }

    for (int i = 1; i < MAXV; i++) {
        int d_prev = -1;
        for (auto it = inds[i].begin(); it != inds[i].end(); it++) {
            if (d_prev != -1) {
                auto next_ind = lower_bound(it, inds[i].end(), *it + (*it - d_prev));
                if (next_ind != inds[i].end()) {
                    intervals[*next_ind].emplace_back(d_prev, i);
                }
            }
            d_prev = *it;
        }
    }

    vector<tuple<int, int, int>> queries(q);
    for (int i = 0; i < q; i++) {
        int l, r;
        cin >> l >> r;
        queries[i] = {r - 1, l - 1, i};
    }
    sort(queries.begin(), queries.end());

    Tree st(n);
    vector<int> res(n);
    int p = 0;
    for (int i = 0; i < n; i++) {
        for (auto [l, div] : intervals[i]) {
            st.update(l, div);
        }
        while (p < n && get<0>(queries[p]) == i) {
            res[get<2>(queries[p])] = st.query(get<1>(queries[p]), i + 1);
            p++;
        }
    }
    for (int i = 0; i < n; i++) {
        cout << res[i] << "\n";
    }
}

詳細信息

Test #1:

score: 100
Accepted
time: 495ms
memory: 117768kb

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
Wrong Answer
time: 2481ms
memory: 719384kb

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...

output:

997920
997920
997920
997920
997920
997920
997920
997920
997920
997920
997920
997920
997920
997920
997920
997920
997920
997920
997920
997920
997920
997920
997920
997920
997920
997920
997920
997920
997920
997920
997920
997920
997920
997920
997920
997920
997920
997920
997920
997920
997920
997920
997920...

result:

wrong answer Participant output contains extra tokens