제출 #591378

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
591378		SlavicG	Game (IOI13_game)	C++17	100 / 100	6182 ms	67484 KiB

game

#include "game.h"
#include "bits/stdc++.h"
using namespace std;

using ll = long long;


mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll rand(ll a, ll b) {return a + rng() % (b - a + 1);}

int n, m;
struct node {
    node *left, *right;
    ll val;
};
ll gcd(ll a, ll b, ll c)  {
    return __gcd(__gcd(a, b), c);
}
struct Treap {
    struct node {
        node *l, *r;
        ll x, y;
        ll gc, val;
        node(ll X) {
            l = r = NULL;
            x = X, y = rand(1, (ll)1e9);
        }
    };
    node *root = 0;
    ll get(node *a) {
        if(a == NULL) return 0;
        return a->gc;
    }
    void split(node *t, node *&l, node *&r, int k) {
        if(!t) {
            l = r = NULL;
        } else if(t->x <= k) {
            split(t->r, t->r, r, k), l = t;
        } else {
            split(t->l, l, t->l, k), r = t;
        }
        if(t != NULL)
            t->gc = gcd(get(t->l), get(t->r), t->val);
    }
    void merge(node *&t, node *l, node *r) {
        if(!l) {
            t = r;
        } else if(!r) {
            t = l;
        } else if(l->y > r->y) {
            merge(l->r, l->r, r), t = l;
        } else {
            merge(r->l, l, r->l), t = r;
        }
        if(t != NULL)
            t->gc = gcd(get(t->l), get(t->r), t->val);
    }
    bool find(node* t, ll k) {
        if(t == NULL) return false;
        if(t->x == k) return true;
        if(t->x > k) return find(t->l, k);
        else return find(t->r, k);
    }
    ll query(int l, int r) {
        if(root == NULL) return 0;
        node *A, *B, *C;
        split(root, A, B, l - 1);
        split(B, B, C, r);
        ll ans = (B == NULL ? 0 : B->gc);
        merge(root, A, B);
        merge(root, root, C);
        return ans;
    }
    void modif(int j, ll val) {
        node *A, *B, *C;
        if(find(root, j)) {
            split(root, A, B, j - 1);
            split(B, B, C, j);
            B->val = val;
            merge(root, A, B);
            merge(root, root, C);
        } else {
            split(root, A, B, j - 1);
            C = new node(j);
            C->val = val;
            merge(root, A, C);
            merge(root, root, B);
        }
    }
};

struct purice {
    purice *left, *right;
    Treap paiu;
};

void modifi(purice *&i, int l, int r, int posi, int posj, ll val) {
    if(l > posi || r < posi) return;
    if(!i) i = new purice();
    if(l == posi && r == posi) {
        i->paiu.modif(posj, val);
        return;
    }
    int mid = (l + r) >> 1;

    modifi(i->left, l, mid, posi, posj, val);
    modifi(i->right, mid + 1, r, posi, posj, val);
    ll leftval = 0, rightval = 0;
    if(i->left) leftval = i->left->paiu.query(posj, posj);
    if(i->right) rightval = i->right->paiu.query(posj, posj);
    ll new_val = __gcd(leftval, rightval);

    i->paiu.modif(posj, new_val);
}

ll queryi(purice* i, int l, int r, int tli, int tri, int tlj, int trj) {
    if(l > tri || r < tli) return 0;
    if(!i || l > tri || r < tli) return 0;
    if(l >= tli && r <= tri) return i->paiu.query(tlj, trj);
    int mid = (l + r) >> 1;
    return __gcd(queryi(i->left, l, mid, tli, tri, tlj, trj), queryi(i->right, mid + 1, r, tli, tri, tlj, trj));
}

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;
}


purice *amogus;
void init(int R, int C) {
    n = R, m = C;
}


void update(int P, int Q, long long K) {
    modifi(amogus, 0, n - 1, P, Q, K);
}

long long calculate(int P, int Q, int U, int V) {
    return queryi(amogus, 0, n - 1, P, U, Q, V);
}

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