Submission #963497

#	Time	Username	Problem	Language	Result	Execution time	Memory
963497		simona1230	Game (IOI13_game)	C++17	36 / 100	1327 ms	193544 KiB

game

#include <bits/stdc++.h>
#include "game.h"
using namespace std;

int rr,cc;

void init(int R,int C)
{
    rr=R;
    cc=C;
}

long long x,y;
long long p,q,u,v;
long long t[8000][8000];

long long query2(int i,int l,int r,int ql,int qr,int j)
{
    if(ql>qr)return 0;
    if(ql<=l&&r<=qr)return t[j][i];
    int m=(l+r)/2;
    long long lf=query2(i*2,l,m,ql,min(qr,m),j);
    long long rt=query2(i*2+1,m+1,r,max(ql,m+1),qr,j);
    if(lf==0)return rt;
    if(rt==0)return lf;
    return __gcd(rt,lf);
}

long long query1(int i,int l,int r,int ql,int qr)
{
    if(ql>qr)return 0;
    if(ql<=l&&r<=qr)return query2(1,0,cc-1,q,v,i);
    int m=(l+r)/2;
    long long lf=query1(i*2,l,m,ql,min(qr,m));
    long long rt=query1(i*2+1,m+1,r,max(ql,m+1),qr);
    if(lf==0)return rt;
    if(rt==0)return lf;
    return __gcd(lf,rt);
}


void upd2(int i,int l,int r,int j,long long val)
{
    if(l==r)
    {
        t[j][i]=val;
        return;
    }

    int m=(l+r)/2;
    if(y<=m)upd2(i*2,l,m,j,val);
    else upd2(i*2+1,m+1,r,j,val);

    long long lf=t[j][i*2];
    long long rt=t[j][i*2+1];
    if(lf==0)t[j][i]=rt;
    else if(rt==0)t[j][i]=lf;
    else t[j][i]=__gcd(lf,rt);
}

void upd1(int i,int l,int r)
{
    if(l==r)
    {
        upd2(1,0,cc-1,i,v);
        return;
    }

    int m=(l+r)/2;
    if(x<=m)upd1(i*2,l,m);
    else upd1(i*2+1,m+1,r);

    long long val1=query2(1,0,cc-1,y,y,i*2);
    long long val2=query2(1,0,cc-1,y,y,i*2+1);
    long long val;
    if(val1==0)val=val2;
    else if(val2==0)val=val1;
    else val=__gcd(val1,val2);

    upd2(1,0,cc-1,i,val);
}


void update(int X,int Y,long long V)
{
    x=X;
    y=Y;
    v=V;
    upd1(1,0,rr-1);
}

long long calculate(int P,int Q,int U,int V)
{
    p=P;
    q=Q;
    u=U;
    v=V;
    return query1(1,0,rr-1,p,u);
}

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