fork download
copy 
// https://c...content-available-to-author-only...s.com/gym/522055/problem/D

#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

template<class T> bool maximize(T &res, const T &val) {
    if (res < val) {
        res = val;
        return true;
    }
    return false;
}

template<class T> bool minimize(T &res, const T &val) {
    if (res > val) {
        res = val;
        return true;
    }
    return false;
}

template<class Integer>
Integer gcd(Integer a, Integer b)
{
    while (a) swap(b %= a, a);
    return b;
}

struct Node
{
    long long value;
    Node(long long v = 0) : value(v) {}
    
    friend Node operator + (const Node &LHS, const Node &RHS) {
        return Node(gcd(LHS.value, RHS.value));
    }
    
    friend ostream& operator << (ostream &os, const Node &S) {
        os << S.value;
        return os;
    }
};

struct Segtree
{
    int n;
    vector<Node> tree;
    
    // Khởi tạo segment tree chứa tối thiểu n phần tử (các phần tử thừa khỏi tạo là 0)
    void init(int lim)
    {
        for (n = 1; n < lim; n <<= 1);
        tree.assign(n << 1, Node());
    }
    
    // Để sử dụng Segtree S(n); thay vì Segtree S; S.init(n);
    Segtree(int lim = 0)
    {
        init(lim);
    }
    
    /// Sửa giá trị tại a[p] thành v, cần tìm nút lá tree[ct] tương ứng a[p]
    /// với chỉ số node hiện tại là ct, và quản lí đoạn a[lt..rt)
    void modify(int p, const Node& v, int ct, int lt, int rt)
    {
        // đã tìm được nút lá tree[ct] = a[p]
        if (rt - lt == 1) {
            // thay thế nó bằng giá trị v (lưu ý nhớ cập nhật lại các cha)
            tree[ct] = v;
            return ;
        }
        
        // tìm trung điểm của đoạn (vì mỗi đoạn độ dài 2^k)
        int mt = (lt + rt) / 2;
        if (mt > p) { 
            // nhánh trái::con trái = cha * 2 + 1, quản lí đoạn a[lt..mt)
            modify(p, v, ct * 2 + 1, lt, mt);
        }
        else { 
            // nhánh phải::con phải = cha * 2 + 2, quản lí đoạn a[mt..rt)
            modify(p, v, ct * 2 + 2, mt, rt);
        }
        
        // lưu ý: phải cập nhật lại các cha bị thay đổi, khi a[p] := v
        tree[ct] = tree[ct * 2 + 1] + tree[ct * 2 + 2];
    }
    
    /// Truy vấn gán a[p] := v, thì sửa lại cây để phù hợp với a[] mới
    /// với gốc cây là ct = 0, quản lí đoạn a[0..n)
    void modify(int p, const Node& v)
    {
        return modify(p, v, 0, 0, n);        
    }
    
    /// Tính kết quả tổng a[l..r), cần tìm các đoạn tree[lt..rt] chứa các đoạn a[li..ri] 
    Node query(int l, int r, int ct, int lt, int rt)
    {
        // Vùng [lt..rt] hiện tại không chứa a[l..r)
        if (lt >= r || l >= rt) {
            return Node();
        }
        // Vùng [lt..rt] hiện tại cũng chính là đoạn con a[li..ri] thuộc a[l..r)
        if (lt >= l && r >= rt) {
            return tree[ct];
        }
        
        // tìm trung điểm của đoạn (vì mỗi đoạn độ dài 2^k)
        int mt = (lt + rt) / 2;
        // lấy kết quả các đoạn bên trái, con trái = cha * 2 + 1, quản lí đoạn a[lt..mt)
        Node res_lt = query(l, r, ct * 2 + 1, lt, mt);
        // lấy kết quả các đoạn bên phải, con phải = cha * 2 + 2, quản lí đoạn a[mt..rt)
        Node res_rt = query(l, r, ct * 2 + 2, mt, rt);
        
        // tính tổng kết quả hai bên
        return res_lt + res_rt;
    }
    
    /// Truy vấn lấy tổng của a[l..r)
    /// với gốc cây là ct = 0, quản lí đoạn a[0..n)
    Node query(int l, int r)
    {
        return query(l, r, 0, 0, n);
    }
};

int main()
{
    if (fopen("GCD.INP", "r")) {
        freopen("GCD.INP", "r", stdin);
        freopen("GCD.OUT", "w", stdout);    
    }
    
    ios::sync_with_stdio(NULL);
    cin.tie(NULL);
    
    int n, k;
    cin >> n >> k;
    
    vector<long long> a(n);
    for (long long &x : a) {
        cin >> x;
    }
    Segtree S(n);
    for (int i = 0; i < n; ++i) {
        S.modify(i, Node(a[i]));
    }
    
    /* Debug
    for (int l = 0; l < n; ++l) {
        long long ans = 0;
        cerr << "a[" << l << ".." << n << "] = { ";
        for (int r = l; r < n; ++r) cerr << a[r] << " ";
        cerr << "}" << endl;
        for (int r = l; r < n; ++r) {
            ans = gcd(ans, a[r]);
            cerr << "a[" << l << ".." << r << "] = " << S.query(l, r + 1) << " vs " << ans << endl;
        }   
    }
    cerr << string(32, '-') << endl;
    */
    long long res = 0;
    for (int l = 0, r = k; r <= n; ++l, ++r) { /// [l..r), size = k
        maximize(res, S.query(l, r).value);
    }
    cout << res;
    return 0;
}
Success #stdin #stdout 0s 5300KB
comments (?)
stdin
copy 
10 3
2 6 4 3 18 12 24 8 7 5
stdout
copy 
6
https://ideone.com/y3MVsM
language:
C++14 (gcc 8.3)
created:
14 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!