Submission #597804

#	Time	Username	Problem	Language	Result	Execution time	Memory
597804		Bench0310	Game (IOI13_game)	C++17	63 / 100	1762 ms	256000 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_bottom(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_bottom(now->l,l,m,pos,x);
        else update_c_bottom(now->r,m+1,r,pos,x);
        now->pull();
    }
}

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

void update_r(Up *now,int l,int r,int pos_r,int pos_c,ll x)
{
    if(l==r) update_c_bottom(now->root,1,M,pos_c,x);
    else
    {
        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);
        update_c(now->root,now->l->root,now->r->root,1,M,pos_c);
    }
}

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: 10 / 10
• Subtask 2: 27 / 27
• Subtask 3: 26 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20