제출 #1286017

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1286017		HoriaHaivas	Game (IOI13_game)	C++20	0 / 100	3 ms	584 KiB

game

#include<bits/stdc++.h>
#include "game.h"
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast")
#define int long long

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int range_rng(int l, int r)
{
    return uniform_int_distribution<int>(l,r)(rng);
}

const int lim=1e9+5;

struct Node
{
    int lson;
    int rson;
    int gcd;
};

Node emptyNode={0,0,0};

class AINT
{
public:
    int sz;
    vector<Node> aint;

    void init()///de preferat apeleaza asta
    {
        int sz=0;
        aint.clear();
        aint.push_back(emptyNode);
    }

    void update(int l, int r, int val, int poz, int x)
    {
        if (l==r)
        {
            aint[val].gcd=x;
            return;
        }
        int mid;
        mid=(l+r)/2;
        if (poz<=mid)
        {
            if (aint[val].lson==0)
            {
                sz++;
                aint[val].lson=sz;
                aint.push_back(emptyNode); //aint[sz]=emptyNode;
            }
            update(l,mid,aint[val].lson,poz,x);
        }
        else
        {
            if (aint[val].rson==0)
            {
                sz++;
                aint[val].rson=sz;
                aint.push_back(emptyNode); //aint[sz]=emptyNode;
            }
            update(mid+1,r,aint[val].rson,poz,x);
        }
        aint[val].gcd=0;
        if (aint[val].lson!=0)
            aint[val].gcd=__gcd(aint[val].gcd,aint[aint[val].lson].gcd);
        if (aint[val].rson!=0)
            aint[val].gcd=__gcd(aint[val].gcd,aint[aint[val].rson].gcd);
    }

    int query(int l, int r, int val, int qa, int qb)
    {
        if (qa<=l && r<=qb)
        {
            return aint[val].gcd;
        }
        int mid,ans;
        mid=(l+r)/2;
        ans=0;
        if (qa<=mid)
        {
            if (aint[val].lson!=0)
                ans=__gcd(ans,query(l,mid,aint[val].lson,qa,qb));
        }
        if (qb>mid)
        {
            if (aint[val].rson!=0)
                ans=__gcd(ans,query(mid+1,r,aint[val].rson,qa,qb));
        }
        return ans;
    }

};

struct Node_baban
{
    AINT a;
    int lson;
    int rson;
};

Node_baban emptyNode_baban={{0,{emptyNode}},0,0};

class AINT_baban
{
public:
    int sz;
    vector<Node_baban> aint;

    void init()
    {
        sz=0;
        aint.clear();
        aint.push_back(emptyNode_baban);
        aint.back().a.init();
    }

    void update(int l, int r, int val, int x, int y, int k)
    {
         if (l==r)
         {
             aint[val].a.update(0,lim,0,y,k);
             return;
         }
         int mid;
         mid=(l+r)/2;
         aint[val].a.update(0,lim,0,y,k);
         if (x<=mid)
         {
             if (aint[val].lson==0)
             {
                 sz++;
                 aint[val].lson=sz;
                 aint.push_back(emptyNode_baban);
                 aint.back().a.init();
             }
             update(l,mid,aint[val].lson,x,y,k);
         }
         else
         {
             if (aint[val].rson==0)
             {
                 sz++;
                 aint[val].rson=sz;
                 aint.push_back(emptyNode_baban);
                 aint.back().a.init();
             }
             update(mid+1,r,aint[val].rson,x,y,k);
         }
    }

    int query(int l, int r, int val, int x1, int x2, int y1, int y2)
    {
        if (x1<=l && r<=x2)
        {
            return aint[val].a.query(0,lim,0,y1,y2);
        }
        int mid,ans;
        mid=(l+r)/2;
        ans=0;
        if (x1<=mid)
        {
            if (aint[val].lson!=0)
                ans=__gcd(ans,query(l,mid,aint[val].lson,x1,x2,y1,y2));
        }
        if (x2>mid)
        {
            if (aint[val].rson!=0)
                ans=__gcd(ans,query(mid+1,r,aint[val].rson,x1,x2,y1,y2));
        }
        return ans;
    }
} hurkacz;

void init(signed R, signed C)
{
    hurkacz.init();
}

void update(signed P, signed Q, long long K)
{
    hurkacz.update(0,lim,0,P,Q,K);
}

long long calculate(signed P, signed Q, signed U, signed V)
{
    return hurkacz.query(0,lim,0,P,U,Q,V);
}

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