Submission #1166667

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166667		Hanksburger	Game (IOI13_game)	C++20	100 / 100	2487 ms	82920 KiB

game

#include "game.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll large=1e9;
struct node2
{
    node2 *lc, *rc;
    int l, r;
    ll val;
    node2(ll l, ll r) : lc(0), rc(0), l(l), r(r), val(0) {}
};
struct node1
{
    node1 *lc, *rc;
    node2 *x;
    int l, r;
    node1(ll l, ll r) : lc(0), rc(0), x(0), l(l), r(r) {}
} root(0, large);
void upd2(node2 *i, ll y, ll z)
{
    if (i->l==i->r)
    {
        i->val=z;
        return;
    }
    ll mid=(i->l+i->r)/2;
    if (y<=mid)
    {
        if (!i->lc)
            i->lc=new node2(y, y);
        else if (y<i->lc->l || y>i->lc->r)
        {
            ll l=i->l, r=i->r, m=(l+r)/2;
            while ((y<=m)^(i->lc->l>m))
            {
                if (y<=m)
                    r=m;
                else
                    l=m+1;
                m=(l+r)/2;
            }
            node2 *j=new node2(l, r);
            if (y<=m)
                j->rc=i->lc;
            else
                j->lc=i->lc;
            i->lc=j;
        }
        upd2(i->lc, y, z);
    }
    else
    {
        if (!i->rc)
            i->rc=new node2(y, y);
        else if (y<i->rc->l || y>i->rc->r)
        {
            ll l=i->l, r=i->r, m=(l+r)/2;
            while ((y<=m)^(i->rc->l>m))
            {
                if (y<=m)
                    r=m;
                else
                    l=m+1;
                m=(l+r)/2;
            }
            node2 *j=new node2(l, r);
            if (y<=m)
                j->rc=i->rc;
            else
                j->lc=i->rc;
            i->rc=j;
        }
        upd2(i->rc, y, z);
    }
    i->val=gcd(i->lc?i->lc->val:0, i->rc?i->rc->val:0);
}
ll qry2(node2 *i, ll ql, ll qr)
{
    if (ql<=i->l && i->r<=qr)
        return i->val;
    return gcd((i->lc && i->lc->l<=qr && ql<=i->lc->r)?qry2(i->lc, ql, qr):0,
               (i->rc && i->rc->l<=qr && ql<=i->rc->r)?qry2(i->rc, ql, qr):0);
}
void upd1(node1 *i, ll x, ll y, ll z)
{
    if (i->l==i->r)
    {
        if (!i->x)
            i->x=new node2(0, large);
        upd2(i->x, y, z);
        return;
    }
    ll mid=(i->l+i->r)/2;
    if (x<=mid)
    {
        if (!i->lc)
            i->lc=new node1(i->l, mid);
        upd1(i->lc, x, y, z);
    }
    else
    {
        if (!i->rc)
            i->rc=new node1(mid+1, i->r);
        upd1(i->rc, x, y, z);
    }
    if (!i->x)
        i->x=new node2(0, large);
    upd2(i->x, y, gcd(i->lc?qry2(i->lc->x, y, y):0, i->rc?qry2(i->rc->x, y, y):0));
}
ll qry1(node1 *i, ll ql1, ll qr1, ll ql2, ll qr2)
{
    if (ql1<=i->l && i->r<=qr1)
        return qry2(i->x, ql2, qr2);
    return gcd((i->lc && i->lc->l<=qr1 && ql1<=i->lc->r)?qry1(i->lc, ql1, qr1, ql2, qr2):0,
               (i->rc && i->rc->l<=qr1 && ql1<=i->rc->r)?qry1(i->rc, ql1, qr1, ql2, qr2):0);
}
void init(int R, int C) {}
void update(int P, int Q, ll K) {upd1(&root, P, Q, K);}
ll calculate(int P, int Q, int U, int V) {return qry1(&root, P, U, Q, V);}

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