Submission #963491

#	Time	Username	Problem	Language	Result	Execution time	Memory
963491		simona1230	Game (IOI13_game)	C++17	0 / 100	3 ms	16732 KiB

game

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

int r,c;

void init(int R,int C)
{
    r=R;
    c=C;
}

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

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

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

    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,c-1,i);
        return;
    }

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

    upd2(1,0,c-1,i);
}

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,c-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 update(int X,int Y,long long V)
{
    x=X;
    y=Y;
    v=V;
    upd1(1,0,r-1);
}

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

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