oj.uz

Submission #1091031

# Submission time Handle Problem Language Result Execution time Memory
1091031 2024-09-19T14:29:27 Z vjudge1 Game (IOI13_game) C++17
37 / 100
 13000 ms 15668 KB 
#include <bits/stdc++.h>
#include "game.h"

using namespace std;
struct node{
    node *ll=nullptr;
    node *lr=nullptr;
    node *rl=nullptr;
    node *rr=nullptr;
    node *tatko=nullptr;
    long long value=0;
    int id;
    pair<long long,long long> x;
    pair<long long,long long> y;
};
int p=0;

// trgni voa posle
long long gcd2(long long x,long long y)
{
    if (x==0) return y;
    if (y==0) return x;
    if (x%y==0) return y;
    return gcd2(y,x%y);
}

int stepen(int x)
{
    int a = 1;
    while(a<=x)
    {
        a*=2;
    }
    return a;
}

node koren;
void init(int R,int C)
{
    long long r = stepen(R),c = stepen(C);
    koren.x.first =0;
    koren.y.first =0;
    koren.x.second=r-1;
    koren.y.second=c-1;
    koren.id = p;
    p++;
}

node* create_node(int x1,int x2,int y1,int y2,int v)
{
    node *nov = new node;
    nov->x={x1,x2};
    nov->y={y1,y2};
    nov->value = v;
    nov->id = p;
    p++;

    return nov;
}

void update1(long long r=0,long long c=0,long long v=0,node &n=koren)
{
    //cout<< "ulava u "<<n.x.first<<" "<<n.x.second<< "  "<<n.y.first<<" "<<n.y.second<<endl;
    //system("pause");
    if (n.x.first==n.x.second && n.y.first==n.y.second)
    {
        n.value = v;
        return;
    }

    long long midx = (n.x.second+n.x.first)/2;
    long long midy = (n.y.second+n.y.first)/2;

    if (n.x.first<=r && r<=midx)
    {
        if (n.y.first<=c && c<=midy)
        {
            if (n.ll==nullptr)
                n.ll = create_node(n.x.first,midx,n.y.first,midy,v);

            update1(r,c,v,*n.ll);
        }
        if (n.y.second>=c && c>midy)
        {
            if (n.lr==nullptr)
                n.lr = create_node(n.x.first,midx,midy+1,n.y.second,v);

            update1(r,c,v,*n.lr);
        }
    }

    if (n.x.second>=r && r>midx)
    {
        if (c>=n.y.first && c<=midy)
        {
            if (n.rl==nullptr) n.rl = create_node(midx+1,n.x.second,n.y.first,midy,v);

            update1(r,c,v,*n.rl);
        }
        if (c<=n.y.second && c>midy)
        {
            if (n.rr==nullptr) n.rr = create_node(midx+1,n.x.second,midy+1,n.y.second,v);

            update1(r,c,v,*n.rr);
        }
    }

    long long odg = 0;
    if (n.ll) odg = gcd2(odg,n.ll->value);
    if (n.rl) odg = gcd2(odg,n.rl->value);
    if (n.lr) odg = gcd2(odg,n.lr->value);
    if (n.rr) odg = gcd2(odg,n.rr->value);

    n.value = odg;
}

long long calculate1(long long lx=0,long long ty=0,long long rx=0,long long by=0,node &n=koren)
{
    if (lx>n.x.second || ty>n.y.second || rx<n.x.first || by<n.y.first) return 0;
    if (lx<=n.x.first && n.x.second<=rx && ty<=n.y.first && n.y.second<=by)
    {
        //cout<< n.x.first<<" "<<n.y.first<<" -> "<<n.x.second<<" "<<n.y.second<<" return "<<n.value<<endl;
        return n.value;
    }

    long long odg=0;
    if (n.ll) odg = gcd2(odg,calculate1(lx,ty,rx,by,*n.ll));
    if (n.rl) odg = gcd2(odg,calculate1(lx,ty,rx,by,*n.rl));
    if (n.lr) odg = gcd2(odg,calculate1(lx,ty,rx,by,*n.lr));
    if (n.rr) odg = gcd2(odg,calculate1(lx,ty,rx,by,*n.rr));

    //cout<< n.x.first<<" "<<n.y.first<<" -> "<<n.x.second<<" "<<n.y.second<<" return "<<odg<<endl;
    //system("pause");
    return odg;
}

void update(int P, int Q,long long K)
{
    update1(P,Q,K);
}
long long calculate(int P, int Q, int U, int V)
{
    return calculate1(P,Q,U,V);
}

/*
int main()
{
/*
    init(2,3);
    update(0,0,20);
    update(0,2,15);
    update(1,1,12);
    cout<<calculate(0,0,0,2)<<endl;
    cout<<calculate(0,0,1,1)<<endl;
    update(0,1,6);
    update(1,1,14);
    cout<<calculate(0,0,0,2)<<endl;
    cout<<calculate(0,0,1,1)<<endl;

    init(4,4);
    update(0,0,10);
    update(0,1,12);
    update(0,2,14);
    update(0,3,16);
    update(1,0,20);
    update(1,1,18);
    update(1,3,100);
    update(2,0,15);
    update(2,2,0);
    update(3,0,13);
    update(3,1,13);

    /*for (int x1=0;x1<4;x1++)
        for (int x2=x1;x2<4;x2++)
            for (int y1=0;y1<4;y1++)
                for (int y2=y1;y2<4;y2++){
                    cout<< "od ("<<x1<<","<<y1<<") do ("<<x2<<","<<y2<<") = ";
                    cout<<calculate(x1,y1,x2,y2)<<endl;
                }
    cout<<"0,0 -> 1,1 = "<<calculate(0,0,1,1)<<endl;
    cout<<"0,2 -> 1,3 = "<<calculate(0,2,1,3)<<endl;
    cout<<"0,0 -> 2,0 = "<<calculate(0,0,2,0)<<endl;
    cout<<"2,2 -> 3,3 = "<<calculate(2,2,3,3)<<endl;
    cout<<"3,0 -> 3,1 = "<<calculate(3,0,3,1)<<endl;
    cout<<"2,0 -> 2,0 = "<<calculate(2,0,2,0)<<endl;
    cout<<"1,1 -> 2,2 = "<<calculate(1,1,2,2)<<endl;


    return 0;
}
*/

Compilation message

game.cpp:149:1: warning: "/*" within comment [-Wcomment]
  149 | /*
      |  
game.cpp:174:5: warning: "/*" within comment [-Wcomment]
  174 |     /*for (int x1=0;x1<4;x1++)
      |

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 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 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 600 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 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 600 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 557 ms 15644 KB Output is correct
5 Correct 341 ms 15444 KB Output is correct
6 Correct 462 ms 13212 KB Output is correct
7 Correct 538 ms 12888 KB Output is correct
8 Correct 347 ms 10180 KB Output is correct
9 Correct 491 ms 13140 KB Output is correct
10 Correct 495 ms 12624 KB Output is correct
11 Correct 0 ms 600 KB Output is correct

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 432 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 0 ms 440 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 2780 ms 12472 KB Output is correct
13 Execution timed out 13043 ms 6916 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 0 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 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 567 ms 15608 KB Output is correct
13 Correct 424 ms 15668 KB Output is correct
14 Correct 470 ms 13368 KB Output is correct
15 Correct 644 ms 13068 KB Output is correct
16 Correct 373 ms 10204 KB Output is correct
17 Correct 531 ms 13068 KB Output is correct
18 Correct 571 ms 12628 KB Output is correct
19 Correct 2822 ms 12344 KB Output is correct
20 Execution timed out 13039 ms 6548 KB Time limit exceeded
21 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 0 ms 348 KB Output is correct
3 Correct 1 ms 432 KB Output is correct
4 Correct 0 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 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 0 ms 344 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 558 ms 15656 KB Output is correct
13 Correct 328 ms 15640 KB Output is correct
14 Correct 472 ms 13260 KB Output is correct
15 Correct 527 ms 13060 KB Output is correct
16 Correct 388 ms 10064 KB Output is correct
17 Correct 477 ms 13140 KB Output is correct
18 Correct 452 ms 12716 KB Output is correct
19 Correct 2741 ms 12328 KB Output is correct
20 Execution timed out 13073 ms 6704 KB Time limit exceeded
21 Halted 0 ms 0 KB -