Submission #1091124

#	Time	Username	Problem	Language	Result	Execution time	Memory
1091124		AtinaR	Game (IOI13_game)	C++14	36 / 100	955 ms	132432 KiB

game

#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 / 10
• Subtask 2: 0 / 27
• Subtask 3: 26 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20