oj.uz

Submission #1091129

# Submission time Handle Problem Language Result Execution time Memory
1091129 2024-09-19T22:18:32 Z AtinaR Game (IOI13_game) C++14
36 / 100
 992 ms 131408 KB 
#include <bits/stdc++.h>
#include "game.h"
using namespace std;
const int MAX=2010;
long long gcd(long long a, long long b)
{
    if(b==0)return a;
    return gcd(b,a%b);
}
long long n,m;
long long tree[4*MAX][4*MAX];
long long tree2[4*MAX][4*MAX];
void init(int R, int C)
{
    n=R,m=C;
}
long long sumy(long long nodex, long long nodey, long long L, long long R, long long _left, long long _right)
{
    if(m<=2000)
    {
        if(L>=_left && R<=_right)return tree[nodex][nodey];
        else if(L>_right || R<_left)return 0;
        long long mid=(L+R)/2;
        long long l=sumy(nodex,2*nodey,L,mid,_left,_right);
        long long r=sumy(nodex,2*nodey+1,mid+1,R,_left,_right);
        return gcd(l,r);
    }
    else
    {
        if(L>=_left && R<=_right)return tree2[nodex][nodey];
        else if(L>_right || R<_left)return 0;
        long long mid=(L+R)/2;
        long long l=sumy(nodex,2*nodey,L,mid,_left,_right);
        long long r=sumy(nodex,2*nodey+1,mid+1,R,_left,_right);
        return gcd(l,r);
    }

}
long long sumx(long long node, long long L, long long R, long long _leftx, long long _rightx, long long _lefty, long long _righty)
{
        if(L>=_leftx && R<=_rightx)
        {
            return sumy(node,1,0,m-1,_lefty,_righty);
        }
        else if(L>_rightx || R<_leftx)return 0;
        long long mid=(L+R)/2;
        long long l=sumx(2*node,L,mid,_leftx,_rightx,_lefty,_righty);
        long long r=sumx(2*node+1,mid+1,R,_leftx,_rightx,_lefty,_righty);
        return gcd(l,r);

}
void updatey(long long nodex, long long Lx, long long Rx, long long nodey, long long Ly, long long Ry, long long row, long long col, long long val)
{
    if(m<=2000)
    {
        if(Ly==Ry)
        {
            if(Lx==Rx)
            {
                tree[nodex][nodey]=val;
            }
            else
            {
                tree[nodex][nodey]=gcd(tree[2*nodex][nodey],tree[2*nodex+1][nodey]);
            }
        }
        else
        {
            long long mid=(Ly+Ry)/2;
            if(col>mid)updatey(nodex,Lx,Rx,2*nodey+1,mid+1,Ry,row,col,val);
            else updatey(nodex,Lx,Rx,2*nodey,Ly,mid,row,col,val);
            tree[nodex][nodey]=gcd(tree[nodex][2*nodey],tree[nodex][2*nodey+1]);
        }
    }
    else
    {
        if(Ly==Ry)
        {
            if(Lx==Rx)
            {
                tree2[nodex][nodey]=val;
            }
            else
            {
                tree2[nodex][nodey]=gcd(tree2[2*nodex][nodey],tree2[2*nodex+1][nodey]);
            }
        }
        else
        {
            long long mid=(Ly+Ry)/2;
            if(col>mid)updatey(nodex,Lx,Rx,2*nodey+1,mid+1,Ry,row,col,val);
            else updatey(nodex,Lx,Rx,2*nodey,Ly,mid,row,col,val);
            tree2[nodex][nodey]=gcd(tree2[nodex][2*nodey],tree2[nodex][2*nodey+1]);
        }
    }

}
void updatex(long long node, long long L, long long R, long long row, long long col, long long val)
{
    if(L!=R)
    {
        long long mid=(L+R)/2;
        if(row>mid)updatex(2*node+1,mid+1,R,row,col,val);
        else updatex(2*node,L,mid,row,col,val);
    }
    updatey(node,L,R,1,0,m-1,row,col,val);
}

long long calculate(int P, int Q, int U, int V)
{
    return sumx(1,0,n-1,P,U,Q,V);
}
void update(int P, int Q, long long K)
{
    updatex(1,0,n-1,P,Q,K);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 1372 KB Output is correct
3 Correct 1 ms 1372 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 1116 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 1116 KB Output is correct
10 Correct 1 ms 860 KB Output is correct
11 Correct 0 ms 604 KB Output is correct
12 Correct 0 ms 348 KB Output is correct

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 440 KB Output is correct
4 Incorrect 449 ms 7252 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 1116 KB Output is correct
3 Correct 1 ms 1204 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 1372 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 1116 KB Output is correct
10 Correct 1 ms 860 KB Output is correct
11 Correct 0 ms 608 KB Output is correct
12 Correct 632 ms 46104 KB Output is correct
13 Correct 801 ms 37944 KB Output is correct
14 Correct 465 ms 6480 KB Output is correct
15 Correct 956 ms 86724 KB Output is correct
16 Correct 155 ms 130644 KB Output is correct
17 Correct 764 ms 111948 KB Output is correct
18 Correct 992 ms 131408 KB Output is correct
19 Correct 948 ms 131304 KB Output is correct
20 Correct 910 ms 130548 KB Output is correct
21 Correct 1 ms 344 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 1116 KB Output is correct
3 Correct 1 ms 1372 KB Output is correct
4 Correct 0 ms 440 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 1372 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 1116 KB Output is correct
10 Correct 1 ms 860 KB Output is correct
11 Correct 0 ms 604 KB Output is correct
12 Incorrect 417 ms 7316 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 1116 KB Output is correct
3 Correct 1 ms 1116 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 1372 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 1116 KB Output is correct
10 Correct 1 ms 860 KB Output is correct
11 Correct 0 ms 604 KB Output is correct
12 Incorrect 429 ms 7268 KB Output isn't correct
13 Halted 0 ms 0 KB -