답안 #1091013

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1091013 2024-09-19T13:12:55 Z vjudge1 게임 (IOI13_game) C++17
10 / 100
13000 ms 12232 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)
{
    int r = stepen(max(R,C));
    koren.x.first =0;
    koren.y.first =0;
    koren.x.second=r-1;
    koren.y.second=r-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++)
      |
# 결과 실행 시간 메모리 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 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 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 432 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Execution timed out 13092 ms 6864 KB Time limit exceeded
5 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 404 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 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 2887 ms 12232 KB Output is correct
13 Execution timed out 13039 ms 6860 KB Time limit exceeded
14 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 1 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 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 440 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 432 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 1 ms 436 KB Output is correct
12 Execution timed out 13088 ms 6836 KB Time limit exceeded
13 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 432 KB Output is correct
5 Correct 0 ms 344 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 0 ms 344 KB Output is correct
12 Execution timed out 13080 ms 6920 KB Time limit exceeded
13 Halted 0 ms 0 KB -