oj.uz

Submission #963775

# Submission time Handle Problem Language Result Execution time Memory
963775 2024-04-15T16:15:53 Z simona1230 Game (IOI13_game) C++17
0 / 100
 1 ms 432 KB 
#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;
    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.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 432 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -