oj.uz

Submission #587256

# Submission time Handle Problem Language Result Execution time Memory
587256 2022-07-01T14:28:49 Z yutabi Game (IOI13_game) C++14
63 / 100
 2677 ms 256000 KB 
#include "game.h"

#define gcd gcd2


#include <bits/stdc++.h>
using namespace std;


#define pb push_back


typedef long long ll;
typedef pair <int,int> ii;


long long gcd2(long long X, long long Y)
{
    long long tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}

struct nodex;

struct nodey
{
    nodey* L=0;
    nodey* R=0;

    nodey* par=0;

    nodex* parx=0;

    ll val=0;
};

struct nodex
{
    nodex* L=0;
    nodex* R=0;

    nodex* par=0;

    nodey* Y=0;

    ll val=0;
};


int r;
int c;

nodex* segment_tree;

void check()
{
    vector <pair <nodex*,ii> > processx;

    processx.pb(make_pair(segment_tree,ii(0,r-1)));

    while(processx.size())
    {
        nodex* currx=processx.back().first;

        int Lx=processx.back().second.first;
        int Rx=processx.back().second.second;

        processx.pop_back();

        printf("%lld %d %d\n",currx->val,Lx,Rx);

        vector <pair <nodey*,ii> > processy;

        if(currx->Y!=0)
        {
            processy.pb(make_pair(currx->Y,ii(0,c-1)));
        }

        while(processy.size())
        {
            nodey* curry=processy.back().first;

            int Ly=processy.back().second.first;
            int Ry=processy.back().second.second;

            processy.pop_back();

            printf("%lld %d %d\n",curry->val,Ly,Ry);

            if(curry->L!=0)
            {
                processy.pb(make_pair(curry->L,ii(Ly,(Ly+Ry)/2)));
            }

            if(curry->R!=0)
            {
                processy.pb(make_pair(curry->R,ii((Ly+Ry)/2+1,Ry)));
            }
        }

        printf("\n");

        if(currx->L!=0)
        {
            processx.pb(make_pair(currx->L,ii(Lx,(Lx+Rx)/2)));
        }

        if(currx->R!=0)
        {
            processx.pb(make_pair(currx->R,ii((Lx+Rx)/2+1,Rx)));
        }
    }

    printf("\n");
}

void init(int R, int C)
{
    r=R;
    c=C;

    segment_tree=new nodex;
}

void update(int P, int Q, long long K)
{
    nodex* currx=segment_tree;

    int Lx=0;
    int Rx=r-1;

    while(1)
    {
        if(Lx==Rx)
        {
            if(currx->Y==0)
            {
                currx->Y=new nodey;
                 
                currx->Y->parx=currx;
            }

            nodey* curry=currx->Y;

            int Ly=0;
            int Ry=c-1;

            while(1)
            {
                if(Ly==Ry)
                {
                    curry->val=K;

                    break;
                }

                int My=(Ly+Ry)/2;

                if(Q<=My)
                {
                    if(curry->L==0)
                    {
                        curry->L=new nodey;
                        curry->L->par=curry;
                    }

                    curry=curry->L;

                    Ry=My;
                }

                else
                {
                    if(curry->R==0)
                    {
                        curry->R=new nodey;
                        curry->R->par=curry;
                    }

                    curry=curry->R;

                    Ly=My+1;
                }
            }

            while(1)
            {
                if(curry->par==0)
                {
                    break;
                }

                curry=curry->par;

                curry->val=0;

                if(curry->L!=0)
                {
                    curry->val=curry->L->val;
                }

                if(curry->R!=0)
                {
                    curry->val=gcd(curry->val,curry->R->val);
                }
            }

            break;
        }

        int Mx=(Lx+Rx)/2;

        if(P<=Mx)
        {
            if(currx->L==0)
            {
                currx->L=new nodex;
                currx->L->par=currx;
            }

            currx=currx->L;

            Rx=Mx;
        }

        else
        {
            if(currx->R==0)
            {
                currx->R=new nodex;
                currx->R->par=currx;
            }

            currx=currx->R;

            Lx=Mx+1;
        }
    }

    while(currx->par!=0)
    {
        currx=currx->par;

        nodex* lx=currx->L;
        nodex* rx=currx->R;

        nodey* curry;

        nodey* ly=0;
        nodey* ry=0;

        if(currx->Y==0)
        {
            currx->Y=new nodey;
            currx->Y->parx=currx;
        }

        curry=currx->Y;

        if(lx!=0)
        {
            ly=lx->Y;
        }

        if(rx!=0)
        {
            ry=rx->Y;
        }

        int Ly=0;
        int Ry=c-1;

        while(1)
        {
            ll ans=0;

            if(ly!=0)
            {
                ans=ly->val;
            }

            if(ry!=0)
            {
                ans=gcd(ans,ry->val);
            }

            if(curry!=0)
            {
                curry->val=ans;
            }

            if(Ly==Ry)
            {
                break;
            }

            int My=(Ly+Ry)/2;

            if(Q<=My)
            {
                if(curry->L==0)
                {
                    curry->L=new nodey;
                    curry->L->par=curry;
                }

                curry=curry->L;
                
                if(ly!=0)
                {
                    ly=ly->L;
                }
                
                if(ry!=0)
                {
                    ry=ry->L;
                }

                Ry=My;
            }

            else
            {
                if(curry->R==0)
                {
                    curry->R=new nodey;
                    curry->R->par=curry;
                }

                curry=curry->R;
                
                if(ly!=0)
                {
                    ly=ly->R;
                }
                
                if(ry!=0)
                {
                    ry=ry->R;
                }

                Ly=My+1;
            }
        }
    }

    //check();
}

long long calculate(int P, int Q, int U, int V)
{
    ll ans=0;

    vector <pair <nodex*,ii> > processx;
    vector <pair <nodey*,ii> > processy;

    processx.pb(make_pair(segment_tree,ii(0,r-1)));

    while(processx.size())
    {
        nodex* currx=processx.back().first;

        int Lx=processx.back().second.first;
        int Rx=processx.back().second.second;

        processx.pop_back();

        int Mx=(Lx+Rx)/2;

        if(P<=Lx && Rx<=U)
        {
            if(currx->Y!=0)
            {
                processy.pb(make_pair(currx->Y,ii(0,c-1)));
            }

            continue;
        }

        if(P<=Mx)
        {
            if(currx->L!=0)
            {
                processx.pb(make_pair(currx->L,ii(Lx,Mx)));
            }
        }

        if(Mx+1<=U)
        {
            if(currx->R!=0)
            {
                processx.pb(make_pair(currx->R,ii(Mx+1,Rx)));
            }
        }
    }

    while(processy.size())
    {
        nodey* curry=processy.back().first;

        int Ly=processy.back().second.first;
        int Ry=processy.back().second.second;

        processy.pop_back();

        int My=(Ly+Ry)/2;

        if(Q<=Ly && Ry<=V)
        {
            ans=gcd(ans,curry->val);
            continue;
        }

        if(Q<=My)
        {
            if(curry->L!=0)
            {
                processy.pb(make_pair(curry->L,ii(Ly,My)));
            }
        }

        if(My+1<=V)
        {
            if(curry->R!=0)
            {
                processy.pb(make_pair(curry->R,ii(My+1,Ry)));
            }
        }
    }

    return ans;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 428 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 304 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 0 ms 212 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 733 ms 21224 KB Output is correct
5 Correct 566 ms 21032 KB Output is correct
6 Correct 474 ms 18668 KB Output is correct
7 Correct 528 ms 18504 KB Output is correct
8 Correct 350 ms 13260 KB Output is correct
9 Correct 503 ms 18528 KB Output is correct
10 Correct 515 ms 18068 KB Output is correct
11 Correct 0 ms 212 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 300 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 296 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1410 ms 25636 KB Output is correct
13 Correct 2133 ms 12724 KB Output is correct
14 Correct 306 ms 5620 KB Output is correct
15 Correct 2484 ms 17044 KB Output is correct
16 Correct 200 ms 30960 KB Output is correct
17 Correct 795 ms 21284 KB Output is correct
18 Correct 1364 ms 32632 KB Output is correct
19 Correct 1167 ms 32588 KB Output is correct
20 Correct 1139 ms 32088 KB Output is correct
21 Correct 0 ms 212 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 428 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 737 ms 21264 KB Output is correct
13 Correct 562 ms 21120 KB Output is correct
14 Correct 458 ms 18664 KB Output is correct
15 Correct 534 ms 18364 KB Output is correct
16 Correct 348 ms 13260 KB Output is correct
17 Correct 512 ms 18636 KB Output is correct
18 Correct 488 ms 18344 KB Output is correct
19 Correct 1430 ms 25544 KB Output is correct
20 Correct 2161 ms 12608 KB Output is correct
21 Correct 348 ms 5648 KB Output is correct
22 Correct 2677 ms 16904 KB Output is correct
23 Correct 208 ms 31072 KB Output is correct
24 Correct 919 ms 21244 KB Output is correct
25 Correct 1561 ms 32408 KB Output is correct
26 Correct 1325 ms 32552 KB Output is correct
27 Correct 1262 ms 31904 KB Output is correct
28 Runtime error 563 ms 256000 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 1 ms 424 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 872 ms 21252 KB Output is correct
13 Correct 675 ms 20972 KB Output is correct
14 Correct 652 ms 18692 KB Output is correct
15 Correct 611 ms 18392 KB Output is correct
16 Correct 401 ms 13240 KB Output is correct
17 Correct 633 ms 18532 KB Output is correct
18 Correct 619 ms 18168 KB Output is correct
19 Correct 1681 ms 25536 KB Output is correct
20 Correct 2397 ms 12548 KB Output is correct
21 Correct 373 ms 5652 KB Output is correct
22 Correct 2613 ms 16880 KB Output is correct
23 Correct 199 ms 31016 KB Output is correct
24 Correct 840 ms 21292 KB Output is correct
25 Correct 1444 ms 32528 KB Output is correct
26 Correct 1306 ms 32532 KB Output is correct
27 Correct 1256 ms 31972 KB Output is correct
28 Runtime error 561 ms 256000 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -