제출 #1166448

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1166448		Hanksburger	게임 (IOI13_game)	C++20	0 / 100	13094 ms	328 KiB

game

#include "game.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
struct node
{
    node *lc1=0, *rc1=0, *lc2=0, *rc2=0;
    int l1=0, r1=1e9, l2=0, r2=1e9;
    ll val=0;
} root;
void upd2(node *i, ll x, ll y, ll z)
{
    //cout << "upd2 " << i->l1 << ' ' << i->r1 << ' ' << i->l2 << ' ' << i->r2 << '\n';
    //if (i->lc1)
    //    cout << "left child exists\n";
    //if (i->rc1)
    //    cout << "right child exists\n";
    if (i->l2==i->r2)
    {
        if (i->l1==i->r1)
            i->val=z;
        else
            i->val=gcd(i->lc1?i->lc1->val:0, i->rc1?i->rc1->val:0);
        //cout << "SEGGGGGGG " << i->l1 << ' ' << i->r1 << ' ' << i->l2 << ' ' << i->r2 << ' ' << i->val << '\n';
        return;
    }
    ll mid=(i->l2+i->r2)/2;
    if (y<=mid)
    {
        if (!i->lc2)
        {
            i->lc2=new node;
            i->lc2->l1=i->l1;
            i->lc2->r1=i->r1;
            i->lc2->l2=i->l2;
            i->lc2->r2=mid;
        }
        if (i->lc1)
            i->lc2->lc1=i->lc1->lc2;
        if (i->rc1)
            i->lc2->rc1=i->rc1->lc2;
        upd2(i->lc2, x, y, z);
    }
    else
    {
        if (!i->rc2)
        {
            i->rc2=new node;
            i->rc2->l1=i->l1;
            i->rc2->r1=i->r1;
            i->rc2->l2=mid+1;
            i->rc2->r2=i->r2;
        }
        if (i->lc1)
            i->rc2->lc1=i->lc1->rc2;
        if (i->rc1)
            i->rc2->rc1=i->rc1->rc2;
        upd2(i->rc2, x, y, z);
    }
    if (i->l1==i->r1)
        i->val=gcd(i->lc2?i->lc2->val:0, i->rc2?i->rc2->val:0);
    else
        i->val=gcd(i->lc1?i->lc1->val:0, i->rc1?i->rc1->val:0);
    //cout << "SEGGGGGGG " << i->l1 << ' ' << i->r1 << ' ' << i->l2 << ' ' << i->r2 << ' ' << i->val << '\n';
}
//int cnt=0;
void upd1(node *i, ll x, ll y, ll z)
{
    //if (cnt<=10)
    //    cout << "upd1 " << i->l1 << ' ' << i->r1 << '\n';
    //cnt++;
    if (i->l1==i->r1)
    {
        upd2(i, x, y, z);
        return;
    }
    ll mid=(i->l1+i->r1)/2;
    if (x<=mid)
    {
        if (!i->lc1)
        {
            i->lc1=new node;
            i->lc1->l1=x;
            i->lc1->r1=x;
        }
        else if (x<i->lc1->l1 || x>i->lc1->r1)
        {
            ll l=i->l1, r=i->r1;
            while (1)
            {
                ll m=(l+r)/2;
                if ((x<=m)^(i->lc1->r1<=m))
                    break;
                if (x<=m)
                    r=m;
                else
                    l=m+1;
            }
            node *j=new node;
            j->l1=l;
            j->r1=r;
            if (x<=(l+r)/2)
                j->rc1=i->lc1;
            else
                j->lc1=i->lc1;
            i->lc1=j;
        }
        upd1(i->lc1, x, y, z);
    }
    else
    {
        //if (cnt<=10)
        //    cout << "here\n";
        if (!i->rc1)
        {
            //if (cnt<=10)
            //    cout << "here\n";
            i->rc1=new node;
            i->rc1->l1=x;
            i->rc1->r1=x;
        }
        else if (x<i->rc1->l1 || x>i->rc1->r1)
        {
            ll l=i->l1, r=i->r1;
            while (1)
            {
                ll m=(l+r)/2;
                if ((x<=m)^(i->rc1->r1<=m))
                    r=m;
                else
                    l=m+1;
            }
            node *j=new node;
            j->l1=l;
            j->r1=r;
            if (x<=(l+r)/2)
                j->rc1=i->rc1;
            else
                j->lc1=i->rc1;
            i->rc1=j;
        }
        upd1(i->rc1, x, y, z);
    }
    upd2(i, x, y, z);
}
ll qry2(node *i, ll ql1, ll qr1, ll ql2, ll qr2)
{
    //cout << "qry2 " << i->l1 << ' ' << i->r1 << ' ' << i->l2 << ' ' << i->r2 << ' ' << i->val << '\n';
    if (ql2<=i->l2 && i->r2<=qr2)
        return i->val;
    ll mid=(i->l2+i->r2)/2, res=0;
    if (i->l2<=qr2 && ql2<=mid)
    {
        if (!i->lc2)
        {
            i->lc2=new node;
            i->lc2->l1=i->l1;
            i->lc2->r1=i->r1;
            i->lc2->l2=i->l2;
            i->lc2->r2=mid;
        }
        if (i->lc1)
            i->lc2->lc1=i->lc1->lc2;
        if (i->rc1)
            i->lc2->rc1=i->rc1->lc2;
        if (i->lc2->l1==i->lc2->r1)
        {
            if (i->lc2->l2<i->lc2->r2)
                i->lc2->val=gcd(i->lc2->lc2?i->lc2->lc2->val:0, i->lc2->rc2?i->lc2->rc2->val:0);
        }
        else
            i->lc2->val=gcd(i->lc2->lc1?i->lc2->lc1->val:0, i->lc2->rc1?i->lc2->rc1->val:0);
        res=gcd(res, qry2(i->lc2, ql1, qr1, ql2, qr2));
    }
    if (mid<qr2 && ql2<=i->r2)
    {
        if (!i->rc2)
        {
            i->rc2=new node;
            i->rc2->l1=i->l1;
            i->rc2->r1=i->r1;
            i->rc2->l2=mid+1;
            i->rc2->r2=i->r2;
        }
        if (i->lc1)
            i->rc2->lc1=i->lc1->rc2;
        if (i->rc1)
            i->rc2->rc1=i->rc1->rc2;
        if (i->rc2->l1==i->rc2->r1)
        {
            if (i->rc2->l2<i->rc2->r2)
                i->rc2->val=gcd(i->rc2->lc2?i->rc2->lc2->val:0, i->rc2->rc2?i->rc2->rc2->val:0);
        }
        else
            i->rc2->val=gcd(i->rc2->lc1?i->rc2->lc1->val:0, i->rc2->rc1?i->rc2->rc1->val:0);
        res=gcd(res, qry2(i->rc2, ql1, qr1, ql2, qr2));
    }
    return res;
}
ll qry1(node *i, ll ql1, ll qr1, ll ql2, ll qr2)
{
    //cout << "qry1 " << i->l1 << ' ' << i->r1 << ' ' << i->l2 << ' ' << i->r2 << ' ' << i->val << '\n';
    if (ql1<=i->l1 && i->r1<=qr1)
        return qry2(i, ql1, qr1, ql2, qr2);
    ll mid=(i->l1+i->r1)/2, res=0;
    if (i->l1<=qr1 && ql1<=mid && i->lc1)
        res=gcd(res, qry1(i->lc1, ql1, qr1, ql2, qr2));
    if (mid<qr1 && ql1<=i->r1 && i->rc1)
        res=gcd(res, qry1(i->rc1, ql1, qr1, ql2, qr2));
    return res;
}
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: 0 / 10
• Subtask 2: 0 / 27
• Subtask 3: 0 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20