Submission #1166229

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166229		Hanksburger	Game (IOI13_game)	C++20	80 / 100	3900 ms	244984 KiB

game

#include "game.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int leftchild1[10400000], rightchild1[10400000], leftchild2[10400000], rightchild2[10400000];
ll segtree[10400000], large=1e9, cnt;
ll createNode()
{
    return (cnt++);
}
void update2(ll i, ll l1, ll r1, ll l2, ll r2, ll x, ll y, ll z)
{
    if (l2==r2)
    {
        if (l1==r1)
            segtree[i]=z;
        else
            segtree[i]=gcd(segtree[leftchild1[i]], segtree[rightchild1[i]]);
        return;
    }
    ll mid=(l2+r2)/2;
    if (y<=mid)
    {
        if (!leftchild2[i])
            leftchild2[i]=createNode();
        leftchild1[leftchild2[i]]=leftchild2[leftchild1[i]];
        rightchild1[leftchild2[i]]=leftchild2[rightchild1[i]];
        update2(leftchild2[i], l1, r1, l2, mid, x, y, z);
    }
    else
    {
        if (!rightchild2[i])
            rightchild2[i]=createNode();
        leftchild1[rightchild2[i]]=rightchild2[leftchild1[i]];
        rightchild1[rightchild2[i]]=rightchild2[rightchild1[i]];
        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;
    }
    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);
    }
    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();
    createNode();
}
void update(int P, int Q, ll K)
{
    update1(1, 0, large, P, Q, K);
}
ll calculate(int P, int Q, int U, int V)
{
    return query1(1, 0, large, P, U, Q, V);
}

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