Submission #1165681

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

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;
const int large=1e9;
vector<int> leftchild1, rightchild1, leftchild2, rightchild2;
vector<long long> segtree;
int 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(int i, int l1, int r1, int l2, int r2, int x, int y, long long 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();
    int 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]]);
}
void update1(int i, int l1, int r1, int x, int y, long long z)
{
    //cout << "update (" << l1 << ' ' << r1 << ")\n";
    update2(i, l1, r1, 0, large, x, y, z);
    if (l1==r1)
        return;
    int 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);
    }
}
long long query2(int i, int l1, int r1, int l2, int r2, int ql1, int qr1, int ql2, int qr2)
{
    if (ql2<=l2 && r2<=qr2)
        return segtree[i];
    int mid=(l2+r2)/2;
    long long 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;
}
long long query1(int i, int l1, int r1, int ql1, int qr1, int ql2, int qr2)
{
    if (ql1<=l1 && r1<=qr1)
        return query2(i, l1, r1, 0, large, ql1, qr1, ql2, qr2);
    int mid=(l1+r1)/2;
    long long 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, long long K)
{
    update1(0, 0, large, P, Q, K);
}
long long 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