oj.uz

Submission #962913

# Submission time Handle Problem Language Result Execution time Memory
962913 2024-04-14T09:40:03 Z simona1230 Game (IOI13_game) C++17
37 / 100
 787 ms 32200 KB 
#include <bits/stdc++.h>
#include "game.h"
using namespace std;
int r,c;
long long a[128][128];
bool subt1,subt2;
void init(int R,int C)
{
    r=R;
    c=C;
    if(max(r,c)<=100)subt1=1;
    else subt2=1;
}
long long x,y,v;
long long t[10][400000];


void upd(int i,int l,int r)
{
    if(l==r)
    {
        t[x][i]=v;
        return;
    }
    int m=(l+r)/2;
    if(y<=m)upd(i*2,l,m);
    else upd(i*2+1,m+1,r);

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

int idx;
long long query(int i,int l,int r,int ql,int qr)
{
    if(ql>qr)return 0;
    if(ql<=l&&r<=qr)return t[idx][i];

    int m=(l+r)/2;
    long long lf=query(i*2,l,m,ql,min(qr,m));
    long long rt=query(i*2+1,m+1,r,max(ql,m+1),qr);

    if(lf==0)return rt;
    if(rt==0)return lf;
    return __gcd(rt,lf);
}

void update(int X,int Y,long long V)
{
    x=X;
    y=Y;
    v=V;
    if(subt1)
    {
        a[x][y]=v;
        return;
    }

    upd(1,0,c-1);
}

long long calculate(int p,int q,int u,int v)
{
    if(subt1)
    {
        long long ans=0;
        for(int i=p; i<=u; i++)
        {
            for(int j=q; j<=v; j++)
            {
                if(a[i][j]!=0)
                {
                    if(ans==0)ans=a[i][j];
                    else ans=__gcd(ans,a[i][j]);
                }
            }
        }
        //cout<<ans<<endl;

        return ans;
    }

    long long ans=0;
    for(int i=p;i<=u;i++)
    {
        //cout<<i<<"/"<<endl;
        idx=i;
        long long qr=query(1,0,c-1,q,v);
        if(qr==0)continue;
        if(ans==0)ans=qr;
        else ans=__gcd(ans,qr);
    }

    return ans;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 356 KB Output is correct
12 Correct 1 ms 348 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 775 ms 26552 KB Output is correct
5 Correct 512 ms 26836 KB Output is correct
6 Correct 656 ms 21248 KB Output is correct
7 Correct 639 ms 32140 KB Output is correct
8 Correct 506 ms 19828 KB Output is correct
9 Correct 635 ms 21068 KB Output is correct
10 Correct 594 ms 20788 KB Output is correct
11 Correct 0 ms 348 KB Output is correct

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Runtime error 1 ms 348 KB Execution killed with signal 11
13 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 500 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 600 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 787 ms 26464 KB Output is correct
13 Correct 538 ms 26836 KB Output is correct
14 Correct 617 ms 21328 KB Output is correct
15 Correct 625 ms 32200 KB Output is correct
16 Correct 498 ms 19616 KB Output is correct
17 Correct 678 ms 21128 KB Output is correct
18 Correct 556 ms 20684 KB Output is correct
19 Runtime error 1 ms 348 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 741 ms 26688 KB Output is correct
13 Correct 532 ms 26728 KB Output is correct
14 Correct 632 ms 21276 KB Output is correct
15 Correct 648 ms 32016 KB Output is correct
16 Correct 520 ms 19820 KB Output is correct
17 Correct 666 ms 21176 KB Output is correct
18 Correct 586 ms 20704 KB Output is correct
19 Runtime error 1 ms 348 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -