Submission #591297

#	Time	Username	Problem	Language	Result	Execution time	Memory
591297		SlavicG	Game (IOI13_game)	C++17	0 / 100	1 ms	412 KiB

game

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

using ll = long long;

int n, m;
struct node {
    node *left, *right;
    ll val;
};

struct Treap {
    struct node {
        node *l, *r;
        int x, y;
        ll gc, val;
        bool rev;
    };
    node *root;
    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, t->l, l, k);
            r = t;
        }
        t->gc = __gcd(__gcd(get(t->l), get(t->r)), get(t));
    }
    void merge(node *&t, node *l, node *r) {
        if(!l || !r) {
            t = (l ? l : r);
        } else if(l->y > r->y) {
            merge(l->r, l->r, r);
            t = l;
        } else {
            merge(r->l, l, r->l);
            t = r;
        }
        t->gc = __gcd(__gcd(get(t->l), get(t->r)), get(t));
    }
    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) {
        node *A, *B, *C, *D;
        split(root, A, B, l - 1);
        split(B, C, D, r);
        ll ans = (C == NULL ? 0 : C->val);
        merge(root, A, C);
        merge(root, root, D);
        return ans;
    }
    void modif(int j, ll val) {
        node *A, *B, *C, *D;
        if(find(root, j)) {
            split(root, A, B, j - 1);
            split(B, C, D, j);
            C->val = C->gc = val;
            merge(root, A, C);
            merge(root, root, D);
        } else {
            split(root, A, B, j - 1);
            C = new node();
            C->val = C->gc = val;
            merge(root, root, A);
            merge(root, root, 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;
    leftval = i->left->paiu.query(posj, posj);
    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: 0 / 10
• Subtask 2: 0 / 27
• Subtask 3: 0 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20