Submission #973101

#	Time	Username	Problem	Language	Result	Execution time	Memory
973101		simona1230	Game (IOI13_game)	C++17	0 / 100	1 ms	348 KiB

game

#include <bits/stdc++.h>
#include "game.h"
using namespace std;
 
int h,w;
long long x,y;
long long p,q,u,v;
 
struct node1
{
    int lf,rt,val;
    node1(){}
    node1(int l,int r,int v)
    {
        lf=l;
        rt=r;
        val=v;
    }
};
 
struct segmentTree
{
    vector<node1> t;
    segmentTree()
    {
        t.push_back({0,0,0});
    }
 
    void make_left(int i)
    {
        int idx=t.size();
        t[i].lf=idx;
        t.push_back({0,0,0});
    }
 
    void make_right(int i)
    {
        int idx=t.size();
        t[i].rt=idx;
        t.push_back({0,0,0});
 
    }
 
    long long query(long long i,long long l,long long r,long long ql,long long qr)
    {
        //cout<<l<<" -- "<<r<<endl;
        if(ql>qr)return 0;
        if(ql<=l&&r<=qr)return t[i].val;
 
        long long m=(l+r)/2;
        if(t[i].lf==0)make_left(i);
        if(t[i].rt==0)make_right(i);
 
        return __gcd(query(t[i].lf,l,m,ql,min(qr,m)),query(t[i].rt,m+1,r,max(ql,m+1),qr));
    }
 
    void update(long long i,long long l,long long r,long long idx,long long val)
    {
        //cout<<l<<" + "<<r<<endl;
        if(l==r)
        {
            t[i].val=val;
            //cout<<l<<" + "<<r<<endl;
            return;
        }
 
        long long m=(l+r)/2;
        if(t[i].lf==0)make_left(i);
        if(t[i].rt==0)make_right(i);
        int lf=t[i].lf;
        int rt=t[i].rt;
 
        if(idx<=m)update(t[i].lf,l,m,idx,val);
        else update(t[i].rt,m+1,r,idx,val);
 
        t[i].val=__gcd(t[lf].val,t[rt].val);
        //cout<<l<<" + "<<r<<endl;
    }
};
segmentTree f;
struct node2
{
    int lf,rt;
    segmentTree s;
    node2(){}
    node2(int l,int r,segmentTree _s)
    {
        lf=l;
        rt=r;
        s=_s;
    }
};
 
 
struct twod
{
    vector<node2> t={{0,0,f}};
    twod(){}
    void make_left(int i)
    {
        int idx=t.size();
        t[i].lf=idx;
        t.push_back({0,0,{}});
    }
 
    void make_right(int i)
    {
        int idx=t.size();
        t[i].rt=idx;
        t.push_back({0,0,{}});
    }
    void update(int i,int l,int r,int x,int y,long long v)
    {
        //cout<<l<<" - "<<r<<endl;
        if(l==r)
        {
            t[i].s.update(1,0,w-1,y,v);
            //cout<<l<<" - "<<r<<endl;
            return;
        }
 
        int m=(l+r)/2;
        if(t[i].lf==0)make_left(i);
        if(t[i].rt==0)make_right(i);
        int lf=t[i].lf;
        int rt=t[i].rt;
 
        if(x<=m)update(lf,l,m,x,y,v);
        else update(rt,m+1,r,x,y,v);
        //cout<<l<<" - "<<r<<endl;
        long long val=__gcd(t[lf].s.query(0,0,w-1,y,y),t[rt].s.query(0,0,w-1,y,y));
 
        t[i].s.update(0,0,w-1,y,val);
    }
 
    long long query(int i,int l,int r,int ql,int qr,int ql2,int qr2)
    {
        if(ql>qr)return 0;
        if(ql<=l&&r<=qr)
        {
            return t[i].s.query(1,0,w-1,ql2,qr2);
        }
        int m=(l+r)/2;
        if(t[i].lf==0)make_left(i);
        if(t[i].rt==0)make_right(i);
        int lf=t[i].lf;
        int rt=t[i].rt;
        return __gcd(query(lf,l,m,ql,min(qr,m),ql2,qr2),query(rt,m+1,r,max(ql,m+1),qr,ql2,qr2));
    }
};
 
twod t;
 
void init(int R,int C)
{
    h=R;
    w=C;
    t.t.push_back({0,0,f});
}
 
void update(int X,int Y,long long V)
{
    x=X;
    y=Y;
    v=V;
    t.update(0,0,h-1,x,y,v);
}
 
long long calculate(int P,int Q,int U,int V)
{
    p=P;
    q=Q;
    u=U;
    v=V;
    return t.query(0,0,h-1,p,u,q,v);
}

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