oj.uz

Submission #88494

# Submission time Handle Problem Language Result Execution time Memory
88494 2018-12-06T07:19:30 Z gs18115 Game (IOI13_game) C++14
63 / 100
 8183 ms 257024 KB 
#include "game.h"
#include<cassert>
#include<iostream>
using namespace std;
typedef long long LL;
LL gcd2(LL X, LL Y) {
    LL tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}
struct SY
{
    bool flag;
    int Y;
    SY*l,*r;
    LL val;
    SY()
    {
        flag=true;
        val=0;
        l=r=nullptr;
    }
    inline void update(int y,LL p)
    {
        Y=y;
        val=p;
        return;
    }
    void update(int L,int R,int y,LL p)
    {
        if(L==R)
        {
            val=p;
            return;
        }
        int mid=L+R>>1;
        if(flag)
        {
            if(Y==y)
            {
                val=p;
                return;
            }
            if(Y>mid)
            {
                r=new SY();
                r->update(Y,val);
            }
            else
            {
                l=new SY();
                l->update(Y,val);
            }
            flag=false;
            if(y>mid)
            {
                if(!r)
                {
                    r=new SY();
                    r->update(y,p);
                }
                else
                    r->update(mid+1,R,y,p);
            }
            else
            {
                if(!l)
                {
                    l=new SY();
                    l->update(y,p);
                }
                else
                    l->update(L,mid,y,p);
            }
            LL LP,RP;
            if(!l)
                LP=0;
            else
                LP=l->val;
            if(!r)
                RP=0;
            else
                RP=r->val;
            val=gcd2(LP,RP);
            return;
        }
        if(y>mid)
        {
            if(!r)
            {
                r=new SY();
                r->update(y,p);
            }
            else
                r->update(mid+1,R,y,p);
        }
        else
        {
            if(!l)
            {
                l=new SY();
                l->update(y,p);
            }
            else
                l->update(L,mid,y,p);
        }
        LL LP,RP;
        if(!l)
            LP=0;
        else
            LP=l->val;
        if(!r)
            RP=0;
        else
            RP=r->val;
        val=gcd2(LP,RP);
        return;
    }
    void update(SY*P,int L,int R,int y,LL p)
    {
        if(L==R)
        {
            val=P->val;
            Y=P->Y;
            return;
        }
        int mid=L+R>>1;
        if(!flag&&P->flag)
        {
            P->flag=false;
            if(P->Y>mid)
            {
                P->r=new SY();
                P->r->update(P->Y,P->val);
            }
            else
            {
                P->l=new SY();
                P->l->update(P->Y,P->val);
            }
        }
        else if(flag&&!P->flag)
        {
            flag=false;
            if(Y>mid)
            {
                r=new SY();
                r->update(Y,val);
            }
            else
            {
                l=new SY();
                l->update(Y,val);
            }
        }
        val=P->val;
        Y=P->Y;
        if(flag)
            return;
        if(y>mid)
        {
            if(!P->r)
                assert(false);
            else if(!r)
            {
                r=new SY();
                r->update(y,p);
            }
            else
                r->update(P->r,mid+1,R,y,p);
        }
        else
        {
            if(!P->l)
                assert(false);
            else if(!l)
            {
                l=new SY();
                l->update(y,p);
            }
            else
                l->update(P->l,L,mid,y,p);
        }
        return;
    }
    void update(SY*Lp,SY*Rp,int L,int R,int y,LL p)
    {
        if(L==R)
        {
            val=gcd2(Lp->val,Rp->val);
            flag=false;
            return;
        }
        int mid=L+R>>1;
        if(flag)
        {
            flag=false;
            if(Y>mid)
            {
                r=new SY();
                r->update(Y,val);
            }
            else
            {
                l=new SY();
                l->update(Y,val);
            }
        }
        if(Lp->flag)
        {
            Lp->flag=false;
            if(Lp->Y>mid)
            {
                Lp->r=new SY();
                Lp->r->update(Lp->Y,Lp->val);
            }
            else
            {
                Lp->l=new SY();
                Lp->l->update(Lp->Y,Lp->val);
            }
        }
        if(Rp->flag)
        {
            Rp->flag=false;
            if(Rp->Y>mid)
            {
                Rp->r=new SY();
                Rp->r->update(Rp->Y,Rp->val);
            }
            else
            {
                Rp->l=new SY();
                Rp->l->update(Rp->Y,Rp->val);
            }
        }
        val=gcd2(Lp->val,Rp->val);
        if(y>mid)
        {
            if(!Lp->r&&!Rp->r)
                assert(false);
            else if(!r)
            {
                r=new SY();
                r->update(y,p);
            }
            else if(!Lp->r)
                r->update(Rp->r,mid+1,R,y,p);
            else if(!Rp->r)
                r->update(Lp->r,mid+1,R,y,p);
            else
                r->update(Lp->r,Rp->r,mid+1,R,y,p);
        }
        else
        {
            if(!Lp->l&&!Rp->l)
                assert(false);
            else if(!l)
            {
                l=new SY();
                l->update(y,p);
            }
            else if(!Lp->l)
                l->update(Rp->l,L,mid,y,p);
            else if(!Rp->l)
                l->update(Lp->l,L,mid,y,p);
            else
                l->update(Lp->l,Rp->l,L,mid,y,p);
        }
        return;
    }
    LL query(int L,int R,int y1,int y2)
    {
        if(L>y2||R<y1)
            return 0;
        if(L>=y1&&R<=y2)
            return val;
        if(flag)
        {
            if(y1<=Y&&Y<=y2)
                return val;
            else
                return 0;
        }
        int mid=L+R>>1;
        LL LP,RP;
        if(!l)
            LP=0;
        else
            LP=l->query(L,mid,y1,y2);
        if(!r)
            RP=0;
        else
            RP=r->query(mid+1,R,y1,y2);
        return gcd2(LP,RP);
    }
};
int R,C;
struct SX
{
    SX*l,*r;
    SY*val;
    SX()
    {
        val=new SY();
        l=r=nullptr;
    }
    void update(int L,int R,int x,int y,LL p)
    {
        if(L==R)
        {
            val->update(0,C-1,y,p);
            return;
        }
        int mid=L+R>>1;
        if(x>mid)
        {
            if(!r)
                r=new SX();
            r->update(mid+1,R,x,y,p);
        }
        else
        {
            if(!l)
                l=new SX();
            l->update(L,mid,x,y,p);
        }
        if(!r)
            val->update(l->val,0,C-1,y,p);
        else if(!l)
            val->update(r->val,0,C-1,y,p);
        else
            val->update(l->val,r->val,0,C-1,y,p);
        return;
    }
    LL query(int L,int R,int x1,int x2,int y1,int y2)
    {
        if(L>x2||R<x1)
            return 0;
        if(L>=x1&&R<=x2)
            return val->query(0,C-1,y1,y2);
        int mid=L+R>>1;
        LL LP,RP;
        if(!l)
            LP=0;
        else
            LP=l->query(L,mid,x1,x2,y1,y2);
        if(!r)
            RP=0;
        else
            RP=r->query(mid+1,R,x1,x2,y1,y2);
        return gcd2(LP,RP);
    }
}*rt;
void init(int R,int C)
{
    ::R=R;
    ::C=C;
    rt=new SX();
    return;
}
void update(int P,int Q,long long K)
{
    rt->update(0,R-1,P,Q,K);
    return;
}
LL calculate(int P,int Q,int U,int V)
{
    return rt->query(0,R-1,P,U,Q,V);
}

Compilation message

grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  int res;
      ^~~
game.cpp: In member function 'void SY::update(int, int, int, LL)':
game.cpp:40:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid=L+R>>1;
                 ~^~
game.cpp: In member function 'void SY::update(SY*, int, int, int, LL)':
game.cpp:131:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid=L+R>>1;
                 ~^~
game.cpp: In member function 'void SY::update(SY*, SY*, int, int, int, LL)':
game.cpp:198:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid=L+R>>1;
                 ~^~
game.cpp: In member function 'LL SY::query(int, int, int, int)':
game.cpp:289:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid=L+R>>1;
                 ~^~
game.cpp: In member function 'void SX::update(int, int, int, int, LL)':
game.cpp:319:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid=L+R>>1;
                 ~^~
game.cpp: In member function 'LL SX::query(int, int, int, int, int, int)':
game.cpp:346:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid=L+R>>1;
                 ~^~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 612 KB Output is correct
3 Correct 3 ms 672 KB Output is correct
4 Correct 2 ms 672 KB Output is correct
5 Correct 2 ms 672 KB Output is correct
6 Correct 2 ms 672 KB Output is correct
7 Correct 2 ms 672 KB Output is correct
8 Correct 2 ms 720 KB Output is correct
9 Correct 2 ms 724 KB Output is correct
10 Correct 2 ms 728 KB Output is correct
11 Correct 2 ms 900 KB Output is correct
12 Correct 2 ms 900 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 900 KB Output is correct
2 Correct 2 ms 900 KB Output is correct
3 Correct 2 ms 900 KB Output is correct
4 Correct 756 ms 11084 KB Output is correct
5 Correct 491 ms 11372 KB Output is correct
6 Correct 837 ms 11372 KB Output is correct
7 Correct 882 ms 11372 KB Output is correct
8 Correct 567 ms 11372 KB Output is correct
9 Correct 922 ms 11372 KB Output is correct
10 Correct 833 ms 12444 KB Output is correct
11 Correct 2 ms 12444 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12444 KB Output is correct
2 Correct 3 ms 12444 KB Output is correct
3 Correct 3 ms 12444 KB Output is correct
4 Correct 2 ms 12444 KB Output is correct
5 Correct 2 ms 12444 KB Output is correct
6 Correct 2 ms 12444 KB Output is correct
7 Correct 2 ms 12444 KB Output is correct
8 Correct 2 ms 12444 KB Output is correct
9 Correct 3 ms 12444 KB Output is correct
10 Correct 3 ms 12444 KB Output is correct
11 Correct 2 ms 12444 KB Output is correct
12 Correct 1215 ms 25152 KB Output is correct
13 Correct 2749 ms 25152 KB Output is correct
14 Correct 391 ms 25152 KB Output is correct
15 Correct 3245 ms 32832 KB Output is correct
16 Correct 261 ms 42368 KB Output is correct
17 Correct 1550 ms 42368 KB Output is correct
18 Correct 2657 ms 52928 KB Output is correct
19 Correct 2470 ms 58412 KB Output is correct
20 Correct 2224 ms 63252 KB Output is correct
21 Correct 2 ms 63252 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 63252 KB Output is correct
2 Correct 3 ms 63252 KB Output is correct
3 Correct 3 ms 63252 KB Output is correct
4 Correct 2 ms 63252 KB Output is correct
5 Correct 2 ms 63252 KB Output is correct
6 Correct 3 ms 63252 KB Output is correct
7 Correct 2 ms 63252 KB Output is correct
8 Correct 2 ms 63252 KB Output is correct
9 Correct 3 ms 63252 KB Output is correct
10 Correct 2 ms 63252 KB Output is correct
11 Correct 2 ms 63252 KB Output is correct
12 Correct 740 ms 63252 KB Output is correct
13 Correct 462 ms 66836 KB Output is correct
14 Correct 726 ms 68480 KB Output is correct
15 Correct 871 ms 72792 KB Output is correct
16 Correct 560 ms 74504 KB Output is correct
17 Correct 820 ms 81960 KB Output is correct
18 Correct 808 ms 86164 KB Output is correct
19 Correct 1197 ms 98536 KB Output is correct
20 Correct 2753 ms 98536 KB Output is correct
21 Correct 377 ms 98536 KB Output is correct
22 Correct 3334 ms 106356 KB Output is correct
23 Correct 248 ms 115908 KB Output is correct
24 Correct 1354 ms 115908 KB Output is correct
25 Correct 2891 ms 126252 KB Output is correct
26 Correct 2343 ms 131888 KB Output is correct
27 Correct 2249 ms 136480 KB Output is correct
28 Correct 998 ms 199180 KB Output is correct
29 Correct 2216 ms 206140 KB Output is correct
30 Correct 8183 ms 252292 KB Output is correct
31 Correct 7398 ms 252292 KB Output is correct
32 Correct 702 ms 252292 KB Output is correct
33 Correct 1008 ms 252292 KB Output is correct
34 Correct 398 ms 252292 KB Output is correct
35 Correct 1837 ms 252292 KB Output is correct
36 Runtime error 3470 ms 257024 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
37 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 257024 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
2 Halted 0 ms 0 KB -