Submission #1165692

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165692		Hanksburger	Game (IOI13_game)	C++20	0 / 100	2 ms	1404 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=1e9;
ll gcd2(ll X, ll Y)
{
    ll tmp;
    while (X!=Y && Y!=0)
    {
        tmp=X;
        X=Y;
        Y=tmp%Y;
    }
    return X;
}
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 << "update (" << l1 << ' ' << r1 << ") (" << l2 << ' ' << r2 << ")\n";
    if (l2==r2)
    {
        segtree[i]=z;
        return;
    }
    if (!leftchild2[i])
        leftchild2[i]=createNode();
    if (!rightchild2[i])
        rightchild2[i]=createNode();
    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]=gcd2(segtree[leftchild2[i]], segtree[rightchild2[i]]);
}
void update1(ll i, ll l1, ll r1, ll x, ll y, ll z)
{
    //cout << "update (" << l1 << ' ' << r1 << ")\n";
    update2(i, l1, r1, 0, large, x, y, z);
    if (l1==r1)
        return;
    ll mid=(l1+r1)/2;
    if (x<=mid)
    {
        if (!leftchild1[i])
            leftchild1[i]=createNode();
        update1(leftchild1[i], l1, mid, x, y, z);
    }
    else
    {
        if (!rightchild1[i])
            rightchild1[i]=createNode();
        update1(rightchild1[i], mid+1, r1, 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));
    //cout << "query2 (" << l1 << ' ' << r1 << ") (" << l2 << ' ' << r2 << ") " << res << '\n';
    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));
    //cout << "query1 (" << l1 << ' ' << r1 << ") " << res << '\n';
    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