Submission #597218

#	Time	Username	Problem	Language	Result	Execution time	Memory
597218		Bench0310	Game (IOI13_game)	C++17	0 / 100	1 ms	468 KiB

game

#include <bits/stdc++.h>
#include "game.h"

using namespace std;
typedef long long ll;

int N,M;

struct Node
{
    ll g;
    Node *l,*r;
    Node(ll _g=0){g=_g;l=r=nullptr;}
    void extend(){if(l==nullptr){l=new Node(); r=new Node();}}
    void pull(){g=gcd(l->g,r->g);}
};

struct Up
{
    Node *root;
    Up *l,*r;
    Up(){root=new Node();l=r=nullptr;}
    void extend(){if(l==nullptr){l=new Up(); r=new Up();}}
};

Up *st;

void update_c(Node *now,int l,int r,int pos,ll x)
{
    if(l==r) now->g=x;
    else
    {
        now->extend();
        int m=(l+r)/2;
        if(pos<=m) update_c(now->l,l,m,pos,x);
        else update_c(now->r,m+1,r,pos,x);
        now->pull();
    }
}

void update_r(Up *now,int l,int r,int pos_r,int pos_c,ll x)
{
    update_c(now->root,1,M,pos_c,x);
    if(l<r)
    {
        now->extend();
        int m=(l+r)/2;
        if(pos_r<=m) update_r(now->l,l,m,pos_r,pos_c,x);
        else update_r(now->r,m+1,r,pos_r,pos_c,x);
    }
}

ll query_c(Node *now,int l,int r,int ql,int qr)
{
    if(ql>qr||!now) return 0;
    if(l==ql&&r==qr) return now->g;
    int m=(l+r)/2;
    return gcd(query_c(now->l,l,m,ql,min(qr,m)),query_c(now->r,m+1,r,max(ql,m+1),qr));
}

ll query_r(Up *now,int l,int r,int ql,int qr,int cl,int cr)
{
    if(ql>qr||!now) return 0;
    if(l==ql&&r==qr) return query_c(now->root,1,M,cl,cr);
    int m=(l+r)/2;
    return gcd(query_r(now->l,l,m,ql,min(qr,m),cl,cr),query_r(now->r,m+1,r,max(ql,m+1),qr,cl,cr));
}

void init(int n,int m)
{
    N=n;
    M=m;
    st=new Up();
}

void update(int r,int c,ll k)
{
    r++; c++;
    update_r(st,1,N,r,c,k);
}

ll calculate(int p,int q,int u,int v)
{
    p++; q++; u++; v++;
    return query_r(st,1,N,p,u,q,v);
}

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