oj.uz

Submission #963497

# Submission time Handle Problem Language Result Execution time Memory
963497 2024-04-15T07:25:44 Z simona1230 Game (IOI13_game) C++17
36 / 100
 1327 ms 193544 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 3 ms 16728 KB Output is correct
3 Correct 2 ms 10840 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 3 ms 16732 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 2 ms 14684 KB Output is correct
10 Correct 2 ms 4956 KB Output is correct
11 Correct 2 ms 12636 KB Output is correct
12 Correct 1 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 538 ms 8856 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 344 KB Output is correct
2 Correct 2 ms 16732 KB Output is correct
3 Correct 2 ms 10844 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 4 ms 16728 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 2 ms 14684 KB Output is correct
10 Correct 1 ms 4956 KB Output is correct
11 Correct 2 ms 12636 KB Output is correct
12 Correct 824 ms 126052 KB Output is correct
13 Correct 1088 ms 128104 KB Output is correct
14 Correct 544 ms 75368 KB Output is correct
15 Correct 1327 ms 174248 KB Output is correct
16 Correct 225 ms 193544 KB Output is correct
17 Correct 939 ms 116456 KB Output is correct
18 Correct 1176 ms 144440 KB Output is correct
19 Correct 1176 ms 140108 KB Output is correct
20 Correct 1129 ms 139108 KB Output is correct
21 Correct 0 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 4 ms 16728 KB Output is correct
3 Correct 2 ms 10840 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 2 ms 16732 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 2 ms 14684 KB Output is correct
10 Correct 2 ms 4956 KB Output is correct
11 Correct 2 ms 12632 KB Output is correct
12 Incorrect 523 ms 8816 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 3 ms 16732 KB Output is correct
3 Correct 2 ms 10844 KB Output is correct
4 Correct 0 ms 452 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 3 ms 16828 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 2 ms 14680 KB Output is correct
10 Correct 2 ms 4956 KB Output is correct
11 Correct 2 ms 12636 KB Output is correct
12 Incorrect 533 ms 8860 KB Output isn't correct
13 Halted 0 ms 0 KB -