Submission #659062

#	Time	Username	Problem	Language	Result	Execution time	Memory
659062		Danilo21	Game (IOI13_game)	C++14	37 / 100	13095 ms	87044 KiB

game

#include <bits/stdc++.h>
#include "game.h"

#define ll long long
#define ld long double
#define pb push_back
#define fi first
#define se second
#define en '\n'
#define sp ' '
#define tb '\t'
#define ri(n) int n; cin >> n
#define rl(n) ll n; cin >> n
#define rs(s) string s; cin >> s
#define rc(c) char c; cin >> c
#define rv(v) for (auto &x : v) cin >> x
#define pven(v) for (auto x : v) cout << x << en
#define pv(v) for (auto x : v) cout << x << sp; cout << en
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define yes cout << "YES" << en
#define no cout << "NO" << en
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
#define ssort(a, b) if (a < b) swap(a, b)
#define bitcnt(a) (__builtin_popcountll(a))
#define bithigh(a) (63-__builtin_clzll(a))
#define lg bithigh
#define highpow(a) (1LL << (ll)lg(a))

using namespace std;

long long gcd2(long long X, long long Y) {
    long long tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}

struct node{

    ll x;
    node(ll v = 0){ update(v); }
    node update(ll v, vector<ll> params = {}){ x = v; return *this; }
    static node op(const node& a, const node& b){ return node(gcd2(a.x, b.x)); }
};

template<class T>
class segtree{

    int n;
    vector<T> tree;

    T update(int s, int l, int r, int pos, vector<ll> params){
        if (pos < l || pos > r) return tree[s];
        if (l == r){
            ll x = params[0];
            params = vector<ll>(params.begin()+1, params.end());
            tree[s].update(x, params);
            return tree[s];
        }
        int m = (l + r)>>1;
        T a = update(2*s, l, m, pos, params);
        T b = update(2*s+1, m+1, r, pos, params);
        return tree[s] = T::op(a, b);
    }

    T query(int s, int l, int r, int ql, int qr) const {
        if (l > qr || r < ql) return T();
        if (l >= ql && r <= qr) return tree[s];
        int m = (l + r)>>1;
        T a = query(2*s, l, m, ql, qr);
        T b = query(2*s+1, m+1, r, ql, qr);
        return T::op(a, b);
    }

public:
    segtree<T>(int n = 0, const T& a = T()){ Assign(n, a); }
    void Assign(int s, const T& a){
        n = highpow(s);
        if (bitcnt(s) > 1) n <<= 1;
        tree.assign(2*n, a);
    }
    static segtree<T> op(const segtree<T>& a, const segtree<T>& b){
        int n = max(a.n, b.n);
        segtree<T> r(n);
        for (int i = 1; i < 2*n; i++)
            r.tree[i] = T::op((a.n ? a.tree[i] : T()), (b.n ? b.tree[i] : T()));
        return r;
    }
    T update(int pos, vector<ll> params){ return update(1, 0, n-1, pos, params); }
    T query(int l, int r) const { return query(1, 0, n-1, l, r); }
};

const ll LINF = 4e18;
const int mxN = 1e3+10, INF = 2e9;
ll n, m, a[mxN];
segtree<segtree<node> > st;

void init(int R, int C){
    st.Assign(C, segtree<node>(R));
}

void update(int P, int Q, long long K) {
    st.update(Q, {P, K});
}

long long calculate(int P, int Q, int U, int V) {
    auto tree = st.query(Q, V);
    return tree.query(P, U).x;
}

• Subtask 1: 10 / 10
• Subtask 2: 27 / 27
• Subtask 3: 0 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20