oj.uz

Submission #963694

# Submission time Handle Problem Language Result Execution time Memory
963694 2024-04-15T13:36:17 Z simona1230 Game (IOI13_game) C++17
36 / 100
 1119 ms 227404 KB 
#include <bits/stdc++.h>
#include "game.h"
using namespace std;

int h,w;
long long x,y;
long long p,q,u,v;

struct segmentTree
{
    long long t[8000];
    segmentTree(){}

    long long query(long long i,long long l,long long r,long long ql,long long qr)
    {
        //cout<<l<<" -- "<<r<<endl;
        if(ql>qr)return 0;
        if(ql<=l&&r<=qr)return t[i];
        long long m=(l+r)/2;

        return __gcd(query(i*2,l,m,ql,min(qr,m)),query(i*2+1,m+1,r,max(ql,m+1),qr));
    }

    void update(long long i,long long l,long long r,long long idx,long long val)
    {
        //cout<<l<<" + "<<r<<endl;
        if(l==r)
        {
            t[i]=val;
            //cout<<l<<" + "<<r<<endl;
            return;
        }

        long long m=(l+r)/2;
        if(idx<=m)update(i*2,l,m,idx,val);
        else update(i*2+1,m+1,r,idx,val);

        t[i]=__gcd(t[i*2],t[i*2+1]);
        //cout<<l<<" + "<<r<<endl;
    }
};

struct twod
{
    segmentTree t[8000];
    twod(){}
    void update(int i,int l,int r,int x,int y,long long v)
    {
        //cout<<l<<" - "<<r<<endl;
        if(l==r)
        {
            t[i].update(1,0,w-1,y,v);
            //cout<<l<<" - "<<r<<endl;
            return;
        }

        int m=(l+r)/2;
        if(x<=m)update(i*2,l,m,x,y,v);
        else update(i*2+1,m+1,r,x,y,v);
        //cout<<l<<" - "<<r<<endl;
        long long val=__gcd(t[i*2].query(1,0,w-1,y,y),t[i*2+1].query(1,0,w-1,y,y));

        t[i].update(1,0,w-1,y,val);
    }

    long long query(int i,int l,int r,int ql,int qr,int ql2,int qr2)
    {
        if(ql>qr)return 0;
        if(ql<=l&&r<=qr)
        {
            //cout<<l<<" "<<r<<endl;
            return t[i].query(1,0,w-1,ql2,qr2);
        }
        int m=(l+r)/2;
        return __gcd(query(i*2,l,m,ql,min(qr,m),ql2,qr2),query(i*2+1,m+1,r,max(ql,m+1),qr,ql2,qr2));
    }
};

twod t;

void init(int R,int C)
{
    h=R;
    w=C;
}

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

long long calculate(int P,int Q,int U,int V)
{
    p=P;
    q=Q;
    u=U;
    v=V;
    return t.query(1,0,h-1,p,u,q,v);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 3 ms 16828 KB Output is correct
3 Correct 2 ms 10844 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 2 ms 16732 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 2 ms 14692 KB Output is correct
10 Correct 1 ms 4956 KB Output is correct
11 Correct 2 ms 12636 KB Output is correct
12 Correct 0 ms 432 KB Output is correct

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 420 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Incorrect 479 ms 8768 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 348 KB Output is correct
2 Correct 4 ms 16732 KB Output is correct
3 Correct 2 ms 10940 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 2 ms 16732 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 14780 KB Output is correct
10 Correct 1 ms 4956 KB Output is correct
11 Correct 2 ms 12728 KB Output is correct
12 Correct 717 ms 124864 KB Output is correct
13 Correct 945 ms 127888 KB Output is correct
14 Correct 473 ms 75520 KB Output is correct
15 Correct 1119 ms 217440 KB Output is correct
16 Correct 181 ms 227404 KB Output is correct
17 Correct 899 ms 116372 KB Output is correct
18 Correct 1084 ms 144216 KB Output is correct
19 Correct 1029 ms 140132 KB Output is correct
20 Correct 1006 ms 139248 KB Output is correct
21 Correct 0 ms 348 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 3 ms 16732 KB Output is correct
3 Correct 2 ms 10940 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 408 KB Output is correct
6 Correct 3 ms 16828 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 14680 KB Output is correct
10 Correct 1 ms 4956 KB Output is correct
11 Correct 2 ms 12636 KB Output is correct
12 Incorrect 505 ms 8820 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 348 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 444 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 2 ms 16828 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 12732 KB Output is correct
12 Incorrect 487 ms 8724 KB Output isn't correct
13 Halted 0 ms 0 KB -