Submission #1293472

#	Time	Username	Problem	Language	Result	Execution time	Memory
1293472		Lakshya108	Pairs (IOI07_pairs)	C++20	0 / 100	29 ms	2368 KiB

pairs

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

using ll = long long;

ll mygcd(ll a, ll b) {
    if (a == 0) return b;
    if (b == 0) return a;
    while (b) {
        ll t = a % b;
        a = b;
        b = t;
    }
    return a;
}

struct Treap {
    struct Node {
        int key;
        ll val, g;
        unsigned pri;
        Node *l, *r;
        Node(int k, ll v, unsigned p) : key(k), val(v), g(v), pri(p), l(nullptr), r(nullptr) {}
    };
    Node* root = nullptr;
    mt19937 rng;

    Treap() {
        rng.seed(chrono::steady_clock::now().time_since_epoch().count());
    }

    ll getg(Node* t) {
        return t ? t->g : 0;
    }

    void pull(Node* t) {
        if (!t) return;
        t->g = t->val;
        t->g = mygcd(t->g, getg(t->l));
        t->g = mygcd(t->g, getg(t->r));
    }

    void rotateRight(Node* &t) {
        Node* x = t->l;
        t->l = x->r;
        x->r = t;
        pull(t);
        pull(x);
        t = x;
    }

    void rotateLeft(Node* &t) {
        Node* x = t->r;
        t->r = x->l;
        x->l = t;
        pull(t);
        pull(x);
        t = x;
    }

    void insert(Node* &t, int key, ll val) {
        if (!t) {
            t = new Node(key, val, rng());
            return;
        }
        if (key == t->key) {
            t->val = val;
        } else if (key < t->key) {
            insert(t->l, key, val);
            if (t->l->pri > t->pri) rotateRight(t);
        } else {
            insert(t->r, key, val);
            if (t->r->pri > t->pri) rotateLeft(t);
        }
        pull(t);
    }

    ll query(Node* t, int L, int R) {
        if (!t) return 0;
        if (t->key < L) return query(t->r, L, R);
        if (t->key > R) return query(t->l, L, R);
        ll res = t->val;
        res = mygcd(res, query(t->l, L, R));
        res = mygcd(res, query(t->r, L, R));
        return res;
    }

    void update(int key, ll val) {
        insert(root, key, val);
    }

    ll rangeGcd(int L, int R) {
        if (L > R) return 0;
        return query(root, L, R);
    }
};

struct SegTree {
    struct Node {
        int l, r;
        Node *left, *right;
        Treap t;
        Node(int _l, int _r) : l(_l), r(_r), left(nullptr), right(nullptr), t() {}
    };

    Node* root;
    int Rmax;

    SegTree(int R) {
        Rmax = R;
        root = new Node(0, Rmax);
    }

    void upd(Node* cur, int row, int col, ll val) {
        cur->t.update(col, val);
        if (cur->l + 1 == cur->r) return;
        int m = (cur->l + cur->r) >> 1;
        if (row < m) {
            if (!cur->left) cur->left = new Node(cur->l, m);
            upd(cur->left, row, col, val);
        } else {
            if (!cur->right) cur->right = new Node(m, cur->r);
            upd(cur->right, row, col, val);
        }
    }

    ll query(Node* cur, int ql, int qr, int cl, int cr) {
        if (!cur || qr <= cur->l || cur->r <= ql) return 0;
        if (ql <= cur->l && cur->r <= qr) {
            return cur->t.rangeGcd(cl, cr);
        }
        ll a = query(cur->left, ql, qr, cl, cr);
        ll b = query(cur->right, ql, qr, cl, cr);
        return mygcd(a, b);
    }

    void update(int row, int col, ll val) {
        upd(root, row, col, val);
    }

    ll rectGcd(int rl, int rr, int cl, int cr) {
        return query(root, rl, rr + 1, cl, cr);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int R, C, N;
    if (!(cin >> R >> C >> N)) return 0;
    SegTree st(R);

    while (N--) {
        int type;
        cin >> type;
        if (type == 1) {
            int P, Q;
            ll K;
            cin >> P >> Q >> K;
            st.update(P, Q, K);
        } else {
            int P, Q, U, V;
            cin >> P >> Q >> U >> V;
            if (P > U) swap(P, U);
            if (Q > V) swap(Q, V);
            ll ans = st.rectGcd(P, U, Q, V);
            cout << ans << '\n';
        }
    }
    return 0;
}

• Subtask 1: 0 / 6
• Subtask 2: 0 / 6
• Subtask 3: 0 / 6
• Subtask 4: 0 / 6
• Subtask 5: 0 / 6
• Subtask 6: 0 / 7
• Subtask 7: 0 / 7
• Subtask 8: 0 / 8
• Subtask 9: 0 / 8
• Subtask 10: 0 / 10
• Subtask 11: 0 / 10
• Subtask 12: 0 / 10
• Subtask 13: 0 / 10