Submission #1166191

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166191		Hanksburger	Game (IOI13_game)	C++20	0 / 100	0 ms	328 KiB

game

#include "game.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
vector<ll> leftchild1, rightchild1, leftchild2, rightchild2;
vector<ll> segtree;
ll large=5;
ll createNode()
{
    segtree.push_back(0);
    leftchild1.push_back(0);
    rightchild1.push_back(0);
    leftchild2.push_back(0);
    rightchild2.push_back(0);
    return segtree.size()-1;
}
void update2(ll i, ll l1, ll r1, ll l2, ll r2, ll x, ll y, ll z)
{
    //cout << "update2 " << l1 << ' ' << r1 << ' ' << l2 << ' ' << r2 << '\n';
    if (l2==r2)
    {
        if (l1==r1)
            segtree[i]=z;
        else
            segtree[i]=gcd(segtree[leftchild1[i]], segtree[rightchild1[i]]);
        //cout << "segtree " << l1 << ' ' << r1 << ' ' << l2 << ' ' << r2 << " = " << segtree[i] << '\n';
        return;
    }
    if (!leftchild2[i])
    {
        leftchild2[i]=createNode();
        if (l1<r1)
        {
            if (!leftchild2[leftchild1[i]])
                leftchild2[leftchild1[i]]=createNode();
            leftchild1[leftchild2[i]]=leftchild2[leftchild1[i]];
            if (!leftchild2[rightchild1[i]])
                leftchild2[rightchild1[i]]=createNode();
            rightchild1[leftchild2[i]]=leftchild2[rightchild1[i]];
        }
    }
    if (!rightchild2[i])
    {
        rightchild2[i]=createNode();
        if (l1<r1)
        {
            if (!rightchild2[leftchild1[i]])
                rightchild2[leftchild1[i]]=createNode();
            leftchild1[rightchild2[i]]=rightchild2[leftchild1[i]];
            if (!rightchild2[rightchild1[i]])
                rightchild2[rightchild1[i]]=createNode();
            rightchild1[rightchild2[i]]=rightchild2[rightchild1[i]];
        }
    }
    ll mid=(l2+r2)/2;
    if (y<=mid)
        update2(leftchild2[i], l1, r1, l2, mid, x, y, z);
    else
        update2(rightchild2[i], l1, r1, mid+1, r2, x, y, z);
    segtree[i]=gcd(segtree[leftchild2[i]], segtree[rightchild2[i]]);
    //cout << "segtree " << l1 << ' ' << r1 << ' ' << l2 << ' ' << r2 << " = " << segtree[i] << '\n';
}
void update1(ll i, ll l1, ll r1, ll x, ll y, ll z)
{
    //cout << "update1 " << l1 << ' ' << r1 << '\n';
    if (l1==r1)
    {
        update2(i, l1, r1, 0, large, x, y, z);
        return;
    }
    if (!leftchild1[i])
        leftchild1[i]=createNode();
    if (!rightchild1[i])
        rightchild1[i]=createNode();
    ll mid=(l1+r1)/2;
    if (x<=mid)
        update1(leftchild1[i], l1, mid, x, y, z);
    else
        update1(rightchild1[i], mid+1, r1, x, y, z);
    update2(i, l1, r1, 0, large, x, y, z);
}
ll query2(ll i, ll l1, ll r1, ll l2, ll r2, ll ql1, ll qr1, ll ql2, ll qr2)
{
    if (ql2<=l2 && r2<=qr2)
        return segtree[i];
    ll mid=(l2+r2)/2, res=0;
    if (l2<=qr2 && ql2<=mid && leftchild2[i])
        res=gcd(res, query2(leftchild2[i], l1, r1, l2, mid, ql1, qr1, ql2, qr2));
    if (mid<qr2 && ql2<=r2 && rightchild2[i])
        res=gcd(res, query2(rightchild2[i], l1, r1, mid+1, r2, ql1, qr1, ql2, qr2));
    return res;
}
ll query1(ll i, ll l1, ll r1, ll ql1, ll qr1, ll ql2, ll qr2)
{
    if (ql1<=l1 && r1<=qr1)
        return query2(i, l1, r1, 0, large, ql1, qr1, ql2, qr2);
    ll mid=(l1+r1)/2, res=0;
    if (l1<=qr1 && ql1<=mid && leftchild1[i])
        res=gcd(res, query1(leftchild1[i], l1, mid, ql1, qr1, ql2, qr2));
    if (mid<qr1 && ql1<=r1 && rightchild1[i])
        res=gcd(res, query1(rightchild1[i], mid+1, r1, ql1, qr1, ql2, qr2));
    return res;
}
void init(int R, int C)
{
    createNode();
}
void update(int P, int Q, ll K)
{
    update1(0, 0, large, P, Q, K);
}
ll calculate(int P, int Q, int U, int V)
{
    return query1(0, 0, large, P, U, Q, V);
}

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