oj.uz

Submission #1091123

# Submission time Handle Problem Language Result Execution time Memory
1091123 2024-09-19T21:58:55 Z vjudge1 Game (IOI13_game) C++14
36 / 100
 944 ms 134996 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 sumy(long long nodex, long long nodey, long long L, long long R, long long _left, long long _right)
{
    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);
}
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(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]);
    }
}
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);
}
void init(int R, int C)
{
    n=R,m=C;
}
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);
}/*
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n>>m;
    cout<<tree[1][1]<<endl;
    int q;
    cin>>q;
    for(int i=0; i<q; i++)
    {
        int type;
        cin>>type;
        if(type==1)
        {
            int r,c,val;
            cin>>r>>c>>val;
            updatex(1,0,n-1,r,c,val);
        }
        else
        {
            int gorelevox,gorelevoy,doludesnox,doludesnoy;
            cin>>gorelevox>>gorelevoy>>doludesnox>>doludesnoy;
            cout<<sumx(1,0,n-1,gorelevox,doludesnox,gorelevoy,doludesnoy)<<endl;
        }

    }
    return 0;
}

2 3
20 6 15
0 14 0
*/

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 3172 KB Output is correct
3 Correct 1 ms 3164 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 3164 KB Output is correct
7 Correct 0 ms 352 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 3168 KB Output is correct
10 Correct 1 ms 2908 KB Output is correct
11 Correct 1 ms 2652 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 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Incorrect 374 ms 8864 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 352 KB Output is correct
2 Correct 1 ms 3240 KB Output is correct
3 Correct 1 ms 3164 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 352 KB Output is correct
6 Correct 1 ms 3164 KB Output is correct
7 Correct 1 ms 352 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 3172 KB Output is correct
10 Correct 1 ms 2916 KB Output is correct
11 Correct 1 ms 2656 KB Output is correct
12 Correct 584 ms 48848 KB Output is correct
13 Correct 717 ms 41072 KB Output is correct
14 Correct 416 ms 10424 KB Output is correct
15 Correct 944 ms 89684 KB Output is correct
16 Correct 170 ms 133460 KB Output is correct
17 Correct 790 ms 115352 KB Output is correct
18 Correct 922 ms 134580 KB Output is correct
19 Correct 907 ms 134996 KB Output is correct
20 Correct 837 ms 134048 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 3164 KB Output is correct
3 Correct 1 ms 3164 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 3164 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 3164 KB Output is correct
10 Correct 1 ms 3260 KB Output is correct
11 Correct 1 ms 2652 KB Output is correct
12 Incorrect 381 ms 8788 KB Output isn't correct
13 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 3164 KB Output is correct
3 Correct 1 ms 3164 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Correct 1 ms 3164 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 440 KB Output is correct
9 Correct 1 ms 3164 KB Output is correct
10 Correct 1 ms 2908 KB Output is correct
11 Correct 1 ms 2652 KB Output is correct
12 Incorrect 368 ms 8784 KB Output isn't correct
13 Halted 0 ms 0 KB -