Submission #1091117

#	Time	Username	Problem	Language	Result	Execution time	Memory
1091117		AtinaR	Game (IOI13_game)	C++14	0 / 100	1 ms	356 KiB

game

#include <bits/stdc++.h>
#include "game.h"
using namespace std;
const int MAX=2010;
int gcd(int a, int b)
{
    if(b==0)return a;
    return gcd(b,a%b);
}
int n,m;
int mat[MAX][MAX];
int tree[4*MAX][4*MAX];
void buildy(int nodex, int Lx, int Rx, int nodey, int Ly, int Ry)
{
    if(Ly==Ry)
    {
        if(Lx==Rx)
        {
            tree[nodex][nodey]=mat[Lx][Ly];
        }
        else
        {
            tree[nodex][nodey]=gcd(tree[2*nodex][nodey],tree[2*nodex+1][nodey]);
        }
    }
    else
    {
        int mid=(Ly+Ry)/2;
        buildy(nodex,Lx,Rx,2*nodey,Ly,mid);
        buildy(nodex,Lx,Rx,2*nodey+1,mid+1,Ry);
        tree[nodex][nodey]=gcd(tree[nodex][2*nodey],tree[nodex][2*nodey+1]);
    }
}

void buildx(int node, int L, int R)
{
    if(L!=R)
    {
        int mid=(L+R)/2;
        buildx(2*node,L,mid);
        buildx(2*node+1,mid+1,R);
    }
    buildy(node,L,R,1,0,m-1);
}
int sumy(int nodex, int nodey, int L, int R, int _left, int _right)
{
    if(L>=_left && R<=_right)return tree[nodex][nodey];
    else if(L>_right || R<_left)return 0;
    int mid=(L+R)/2;
    int l=sumy(nodex,2*nodey,L,mid,_left,_right);
    int r=sumy(nodex,2*nodey+1,mid+1,R,_left,_right);
    return gcd(l,r);
}
int sumx(int node, int L, int R, int _leftx, int _rightx, int _lefty, int _righty)
{
    if(L>=_leftx && R<=_rightx)
    {
        return sumy(node,1,0,m-1,_lefty,_righty);
    }
    else if(L>_rightx || R<_leftx)return 0;
    int mid=(L+R)/2;
    int l=sumx(2*node,L,mid,_leftx,_rightx,_lefty,_righty);
    int r=sumx(2*node+1,mid+1,R,_leftx,_rightx,_lefty,_righty);
    return gcd(l,r);
}
void updatey(int nodex, int Lx, int Rx, int nodey, int Ly, int Ry, int row, int col, int 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
    {
        int 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(int node, int L, int R, int row, int col, int val)
{
    if(L!=R)
    {
        int 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;
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<m; j++)
        {
            cin>>mat[i][j];
        }
    }
    buildx(1,0,n-1);
    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;
}

4 4
1 1 2 1 - 5 - 12
0 4 2 1 - 7         - 26
3 2 1 2 - 8 - 14
2 1 1 2 - 6

4 4
1 1 2 1
0 4 2 1
3 2 1 2
2 1 1 2
*/

• Subtask 1: 0 / 10
• Subtask 2: 0 / 27
• Subtask 3: 0 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20