oj.uz

Submission #1091130

# Submission time Handle Problem Language Result Execution time Memory
1091130 2024-09-19T22:19:30 Z vjudge1 Game (IOI13_game) C++14
63 / 100
 1020 ms 133692 KB 
#include <bits/stdc++.h>
#include "game.h"
using namespace std;
const int MAX=2010;
const int MXX=1e5+10;
const int MEX=10;
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*MEX][4*MXX];
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 348 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 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 1 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
27.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 348 KB Output is correct
4 Correct 446 ms 39140 KB Output is correct
5 Correct 329 ms 41692 KB Output is correct
6 Correct 385 ms 42368 KB Output is correct
7 Correct 384 ms 42100 KB Output is correct
8 Correct 312 ms 40236 KB Output is correct
9 Correct 376 ms 42064 KB Output is correct
10 Correct 322 ms 41768 KB Output is correct
11 Correct 0 ms 348 KB Output is correct

Subtask #3
26.0 / 26.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 1 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 627 ms 43348 KB Output is correct
13 Correct 801 ms 35412 KB Output is correct
14 Correct 454 ms 3664 KB Output is correct
15 Correct 1018 ms 84020 KB Output is correct
16 Correct 153 ms 128080 KB Output is correct
17 Correct 767 ms 109136 KB Output is correct
18 Correct 928 ms 128148 KB Output is correct
19 Correct 912 ms 128380 KB Output is correct
20 Correct 870 ms 127604 KB Output is correct
21 Correct 0 ms 348 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 1116 KB Output is correct
3 Correct 1 ms 1116 KB Output is correct
4 Correct 1 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 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 1 ms 604 KB Output is correct
12 Correct 449 ms 39132 KB Output is correct
13 Correct 327 ms 41600 KB Output is correct
14 Correct 368 ms 42396 KB Output is correct
15 Correct 368 ms 42068 KB Output is correct
16 Correct 314 ms 40272 KB Output is correct
17 Correct 372 ms 42040 KB Output is correct
18 Correct 323 ms 41560 KB Output is correct
19 Correct 632 ms 45648 KB Output is correct
20 Correct 794 ms 37728 KB Output is correct
21 Correct 439 ms 8408 KB Output is correct
22 Correct 932 ms 88364 KB Output is correct
23 Correct 157 ms 132436 KB Output is correct
24 Correct 776 ms 113984 KB Output is correct
25 Correct 1006 ms 133460 KB Output is correct
26 Correct 889 ms 133692 KB Output is correct
27 Correct 874 ms 132832 KB Output is correct
28 Runtime error 12 ms 344 KB Execution killed with signal 11
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 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 1160 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 1 ms 604 KB Output is correct
12 Correct 432 ms 39088 KB Output is correct
13 Correct 317 ms 41608 KB Output is correct
14 Correct 370 ms 42548 KB Output is correct
15 Correct 363 ms 42144 KB Output is correct
16 Correct 303 ms 40184 KB Output is correct
17 Correct 367 ms 41984 KB Output is correct
18 Correct 340 ms 41728 KB Output is correct
19 Correct 641 ms 45732 KB Output is correct
20 Correct 814 ms 37692 KB Output is correct
21 Correct 467 ms 8272 KB Output is correct
22 Correct 954 ms 88400 KB Output is correct
23 Correct 158 ms 132428 KB Output is correct
24 Correct 793 ms 114144 KB Output is correct
25 Correct 1020 ms 133456 KB Output is correct
26 Correct 901 ms 133684 KB Output is correct
27 Correct 850 ms 132952 KB Output is correct
28 Runtime error 8 ms 348 KB Execution killed with signal 11
29 Halted 0 ms 0 KB -