oj.uz

Submission #1031106

# Submission time Handle Problem Language Result Execution time Memory
1031106 2024-07-22T14:53:04 Z vjudge1 Game (IOI13_game) C++17
0 / 100
 2400 ms 256000 KB 
#include "game.h"

long long gcd2(long long X, long long Y) {
    long long tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}

#include<iostream>
#include<cassert>

struct {
    struct Node{
        long long val=0;
        int ch[4]{0,0,0,0};
    }tree[9000000];
    int nx=1;
    int n,m;
    void init(int N,int M){
        n=N,m=M;
    }
    int P1,P2;
    long long VAL;
    int update(int l1,int r1,int l2,int r2,int node){
        //assert(!(l1<r1||l2<r2));
        //std::cerr<<l1<<" "<<r1<<" "<<l2<<" "<<r2<<"\n";
        if(!node)node=++nx;
        if(l1==r1&&l2==r2){
            tree[node].val=VAL;
            return node;
        }
        int mid1=(l1+r1)>>1,mid2=(l2+r2)>>1;
        if(P1<=mid1){
            if(P2<=mid2){
                tree[node].ch[0]=update(l1,mid1,l2,mid2,tree[node].ch[0]);
            }else{
                tree[node].ch[1]=update(l1,mid1,mid2+1,r2,tree[node].ch[1]);
            }
        }else{
            if(P2<=mid2){
                tree[node].ch[3]=update(mid1+1,r1,l2,mid2,tree[node].ch[3]);
            }else{
                tree[node].ch[4]=update(mid1+1,r1,mid2+1,r2,tree[node].ch[4]);
            }
        }
        tree[node].val=0;
        for(int i=0;i<4;i++)if(tree[node].ch[i])tree[node].val=gcd2(tree[node].val,tree[tree[node].ch[i]].val);
        return node;
    }
    void update(int p1,int p2,long long val){
        P1=p1,P2=p2,VAL=val;
        update(0,n-1,0,m-1,1);
    }
    int L1,R1,L2,R2;
    long long ANS;
    void query(int l1,int r1,int l2,int r2,int node){
        if(!node)return;
        if(L1<=l1&&r1<=R1&&L2<=l2&&r2<=R2){
            ANS=gcd2(ANS,tree[node].val);
            return;
        }
        if(r1<L1||R1<l1||r2<L2||R2<l2)return;
        int mid1=(l1+r1)>>1,mid2=(l2+r2)>>1;
        query(l1,mid1,l2,mid2,tree[node].ch[0]);
        if(mid2+1<=r2)query(l1,mid1,mid2+1,r2,tree[node].ch[1]);
        if(mid1+1<=r1)query(mid1+1,r1,l2,mid2,tree[node].ch[3]);
        if(mid1+1<=r1&&mid2+1<=r2)query(mid1+1,r1,mid2+1,r2,tree[node].ch[4]);
    }
    long long query(int l1,int r1,int l2,int r2){
        L1=l1,R1=r1,L2=l2,R2=r2;
        ANS=0;
        query(0,n-1,0,m-1,1);
        return ANS;
    }
}st;

void init(int R, int C) {
    //std::cerr<<"ok\n";
    st.init(R,C);
    //std::cerr<<"ok1\n";
}

void update(int P, int Q, long long K) {
    //std::cerr<<"up ok\n";
    st.update(P,Q,K);
    //std::cerr<<"up ok1\n";
}

long long calculate(int P, int Q, int U, int V) {
    //std::cerr<<"begun\n";
    long long val=st.query(P,U,Q,V);
    //std::cerr<<"ended\n";
    return val;
}

Compilation message

game.cpp: In function 'int<unnamed struct>::update(int, int, int, int, int)':
game.cpp:47:40: warning: array subscript 4 is above array bounds of 'int [4]' [-Warray-bounds]
   47 |                 tree[node].ch[4]=update(mid1+1,r1,mid2+1,r2,tree[node].ch[4]);
      |                                  ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
game.cpp:19:13: note: while referencing '<unnamed struct>::Node::ch'
   19 |         int ch[4]{0,0,0,0};
      |             ^~
game.cpp:47:32: warning: array subscript 4 is above array bounds of 'int [4]' [-Warray-bounds]
   47 |                 tree[node].ch[4]=update(mid1+1,r1,mid2+1,r2,tree[node].ch[4]);
      |                 ~~~~~~~~~~~~~~~^
game.cpp:19:13: note: while referencing '<unnamed struct>::Node::ch'
   19 |         int ch[4]{0,0,0,0};
      |             ^~
game.cpp: In function 'void<unnamed struct>::query(int, int, int, int, int)':
game.cpp:71:40: warning: array subscript 4 is above array bounds of 'int [4]' [-Warray-bounds]
   71 |         if(mid1+1<=r1&&mid2+1<=r2)query(mid1+1,r1,mid2+1,r2,tree[node].ch[4]);
      |                                   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
game.cpp:19:13: note: while referencing '<unnamed struct>::Node::ch'
   19 |         int ch[4]{0,0,0,0};
      |             ^~
game.cpp:71:40: warning: array subscript 4 is above array bounds of 'int [4]' [-Warray-bounds]
   71 |         if(mid1+1<=r1&&mid2+1<=r2)query(mid1+1,r1,mid2+1,r2,tree[node].ch[4]);
      |                                   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
game.cpp:19:13: note: while referencing '<unnamed struct>::Node::ch'
   19 |         int ch[4]{0,0,0,0};
      |             ^~
game.cpp:71:40: warning: array subscript 4 is above array bounds of 'int [4]' [-Warray-bounds]
   71 |         if(mid1+1<=r1&&mid2+1<=r2)query(mid1+1,r1,mid2+1,r2,tree[node].ch[4]);
      |                                   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
game.cpp:19:13: note: while referencing '<unnamed struct>::Node::ch'
   19 |         int ch[4]{0,0,0,0};
      |             ^~
game.cpp:71:40: warning: array subscript 4 is above array bounds of 'int [4]' [-Warray-bounds]
   71 |         if(mid1+1<=r1&&mid2+1<=r2)query(mid1+1,r1,mid2+1,r2,tree[node].ch[4]);
      |                                   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
game.cpp:19:13: note: while referencing '<unnamed struct>::Node::ch'
   19 |         int ch[4]{0,0,0,0};
      |             ^~
game.cpp:71:40: warning: array subscript 4 is above array bounds of 'int [4]' [-Warray-bounds]
   71 |         if(mid1+1<=r1&&mid2+1<=r2)query(mid1+1,r1,mid2+1,r2,tree[node].ch[4]);
      |                                   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
game.cpp:19:13: note: while referencing '<unnamed struct>::Node::ch'
   19 |         int ch[4]{0,0,0,0};
      |             ^~
game.cpp:71:40: warning: array subscript 4 is above array bounds of 'int [4]' [-Warray-bounds]
   71 |         if(mid1+1<=r1&&mid2+1<=r2)query(mid1+1,r1,mid2+1,r2,tree[node].ch[4]);
      |                                   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
game.cpp:19:13: note: while referencing '<unnamed struct>::Node::ch'
   19 |         int ch[4]{0,0,0,0};
      |             ^~
game.cpp: In function 'long long int calculate(int, int, int, int)':
game.cpp:71:40: warning: array subscript 4 is above array bounds of 'int [4]' [-Warray-bounds]
   71 |         if(mid1+1<=r1&&mid2+1<=r2)query(mid1+1,r1,mid2+1,r2,tree[node].ch[4]);
      |                                   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
game.cpp:19:13: note: while referencing '<unnamed struct>::Node::ch'
   19 |         int ch[4]{0,0,0,0};
      |             ^~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 211600 KB Output is correct
2 Runtime error 2398 ms 256000 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 211568 KB Output is correct
2 Correct 94 ms 211540 KB Output is correct
3 Runtime error 2315 ms 256000 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 211544 KB Output is correct
2 Runtime error 2366 ms 256000 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 211772 KB Output is correct
2 Runtime error 2393 ms 256000 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 211536 KB Output is correct
2 Runtime error 2400 ms 256000 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -