제출 #489111

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
489111		CYMario	게임 (IOI13_game)	C++17	100 / 100	6851 ms	73220 KiB

game

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
typedef long long ll;
const int N = 300010;
//interaction header
#include "game.h"

ll rd()
{
    ll k = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9')
    {
        k = (k << 1) + (k << 3) + (c ^ 48);
        c = getchar();
    }
    return f > 0 ? k : -k;
}
void wr(ll x)
{
    if (x < 0)
        putchar('-'), x = -x;
    if (x > 9)
        wr(x / 10);
    putchar(x % 10 + '0');
}
 
ll gcd(ll a, ll b)
{
    if (a < 0)
        a = -a;
    if (b < 0)
        b = -a;
    if (a == 0)
        return b;
    if (b == 0)
        return a;
    int r = 0;
    while (!((a & 1) || (b & 1)))
        a >>= 1, b >>= 1, r++;
 
    ll ret = 0;
    while (1)
    {
        while (!(a & 1))
            a >>= 1;
        while (!(b & 1))
            b >>= 1;
        if (a > b)
            a = a - b;
        else
            b = b - a;
        if (0 == a)
        {
            ret = b << r;
            break;
        }
        if (0 == b)
        {
            ret = a << r;
            break;
        }
    }
    return ret;
}
 
struct node
{
    node *l, *r;
    int pos, key, mn, mx;
    ll val, g;
    node(int position, ll value)
    {
        l = r = nullptr;
        mn = mx = pos = position;
        key = rand();
        val = g = value;
    }
    void pull()
    {
        g = val;
        if (l)
            g = gcd(g, l->g);
        if (r)
            g = gcd(g, r->g);
        mn = (l ? l->mn : pos);
        mx = (r ? r->mx : pos);
    }
};
// memory O(n)
struct treap
{
    node *root;
    treap()
    {
        root = nullptr;
    }
    void split(node *t, int pos, node *&l, node *&r)
    {
        if (t == nullptr)
        {
            l = r = nullptr;
            return;
        }
        if (t->pos < pos)
        {
            split(t->r, pos, l, r);
            t->r = l;
            l = t;
        }
        else
        {
            split(t->l, pos, l, r);
            t->l = r;
            r = t;
        }
        t->pull();
    }
    node *merge(node *l, node *r)
    {
        if (!l || !r)
            return l ? l : r;
        if (l->key < r->key)
        {
            l->r = merge(l->r, r);
            l->pull();
            return l;
        }
        r->l = merge(l, r->l);
        r->pull();
        return r;
    }
    bool find(int pos)
    {
        node *t = root;
        while (t)
        {
            if (t->pos == pos)
                return true;
            if (t->pos > pos)
                t = t->l;
            else
                t = t->r;
        }
        return false;
    }
    void upd(node *t, int pos, ll val)
    {
        if (t->pos == pos)
        {
            t->val = val;
            t->pull();
            return;
        }
        if (t->pos > pos)
            upd(t->l, pos, val);
        else
            upd(t->r, pos, val);
        t->pull();
    }
    void insert(int pos, ll val)
    { // set a_pos = val
        if (find(pos))
            upd(root, pos, val);
        else
        {
            node *l, *r;
            split(root, pos, l, r);
            root = merge(merge(l, new node(pos, val)), r);
        }
    }
    ll query(node *t, int st, int en)
    {
        if (t->mx < st || en < t->mn)
            return 0;
        if (st <= t->mn && t->mx <= en)
            return t->g;
        ll ans = (st <= t->pos && t->pos <= en ? t->val : 0);
        if (t->l)
            ans = gcd(ans, query(t->l, st, en));
        if (t->r)
            ans = gcd(ans, query(t->r, st, en));
        return ans;
    }
    ll query(int l, int r)
    { // gcd of a_i such that l <= i <= r
        if (!root)
            return 0;
        return query(root, l, r);
    }
    void print(node *t)
    {
        if (!t)
            return;
        print(t->l);
        wr(t->val), putchar('\n');
        print(t->r);
    }
};
// Dynamic 2D Query Tree From Shahjalal Shohag
// total memory along with treap = nlogn
struct ST
{
    ST *l, *r;
    treap t;
    int b, e;
    ST()
    {
        l = r = nullptr;
    }
    ST(int st, int en)
    {
        l = r = nullptr;
        b = st, e = en;
    }
    void fix(int pos)
    {
        ll val = 0;
        if (l)
            val = gcd(val, l->t.query(pos, pos));
        if (r)
            val = gcd(val, r->t.query(pos, pos));
        t.insert(pos, val);
    }
    void upd(int x, int y, ll val)
    { // set a[x][y] = val
        if (e < x || x < b)
            return;
        if (b == e)
        {
            t.insert(y, val);
            return;
        }
        if (b != e)
        {
            if (x <= (b + e) / 2)
            {
                if (!l)
                    l = new ST(b, (b + e) / 2);
                l->upd(x, y, val);
            }
            else
            {
                if (!r)
                    r = new ST((b + e) / 2 + 1, e);
                r->upd(x, y, val);
            }
        }
        fix(y);
    }
    // gcd of a[x][y] such that i <= x <= j && st <= y <= en
    ll query(int i, int j, int st, int en)
    { 
        if (e < i || j < b)
            return 0;
        if (i <= b && e <= j)
            return t.query(st, en);
        ll ans = 0;
        if (l)
            ans = gcd(ans, l->query(i, j, st, en));
        if (r)
            ans = gcd(ans, r->query(i, j, st, en));
        return ans;
    }
};
ST t;
 
void init(int R, int C)
{
    srand(time(NULL));
    t = ST(0, R - 1);
}
 
void update(int P, int Q, long long K)
{
    t.upd(P, Q, K);
}
 
long long calculate(int P, int Q, int U, int V)
{
    return t.query(P, U, Q, V);
}
 
void test_interaction()
{
    int n = rd(), m = rd();
    init(n, m);
    int q = rd();
    while(q--)
    {
        int op = rd();
        //op 1 : update single point
        if (op == 1)
        {
            int x = rd(), y = rd(); ll w = rd();
            update(x, y, w);
        }
        //op 2 : 2D gcd query
        else 
        {
            int xl = rd(), yl = rd(), xr = rd(), yr = rd();
            wr(calculate(xl, xr, yl, yr)), putchar('\n');
        }
    }
}

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