oj.uz

Submission #503955

# Submission time Handle Problem Language Result Execution time Memory
503955 2022-01-09T09:37:43 Z stefantaga Game (IOI13_game) C++14
100 / 100
 3190 ms 82248 KB 
#include "game.h"
#include <bits/stdc++.h>

using namespace std;
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;
}
typedef long long ll;
int n,m;
struct nodex
{
    int st,dr;
    nodex *fiust,*fiudr;
    long long val;
    nodex(int stanga,int dreapta)
    {
        st=stanga;
        dr=dreapta;
        val=0;
        fiust=fiudr=nullptr;
    }
};
struct nodey
{
    nodey(int stanga,int dreapta) : st(stanga), dr(dreapta), fiust(NULL), fiudr(NULL), fiux(1,m) {}
    int st,dr;
    nodex fiux;
    nodey *fiust,*fiudr;
}*root;
ll query2(nodex *arb, int st,int dr)
{
    if (arb == nullptr || arb->st>dr||st>arb->dr)
    {
        return 0;
    }
    if (st<=arb->st&&arb->dr<=dr)
    {
        return arb->val;
    }
    int mij=(arb->st+arb->dr)/2;
    return gcd2(
        query2(arb->fiust,st,dr),
        query2(arb->fiudr,st,dr)
    );
}
ll query1(nodey *arb ,int st,int dr,int p,int q,int u ,int v)
{
    if (arb == NULL || st > u || dr<p)
    {
        return 0;
    }
    if (p<=st && dr<=u)
    {
        return query2(&arb->fiux,q,v);
    }
    int mij=(st+dr)/2;
    return gcd2(
        query1(arb->fiust,st,mij,p,q,u,v),
        query1(arb->fiudr,mij+1,dr,p,q,u,v)
    );
}
void init(int R, int C) {
    n=R;
    m=C;
    root = new nodey(1,n);
}
void updatey(nodex *arb,int y,ll k)
{
     int st = arb->st, dr = arb->dr, mij=(st+dr)/2;
     if (st==dr)
     {
         arb->val=k;
         return;
     }
     nodex **copil = &(y<=mij ? arb->fiust : arb->fiudr);
     if (*copil == NULL)
     {
         *copil = new nodex (y,y);
         (*copil)->val = k;
     }
     else
     if ((*copil)->st<=y&&y<=(*copil)->dr)
     {
         updatey(*copil,y,k);
     }
     else
     {
         do
         {
             if (y<=mij)
             {
                 dr=mij;
             }
             else
             {
                 st=mij+1;
             }
             mij=(st+dr)/2;
         }while ((y<=mij) == ((*copil)->dr<=mij));
         nodex *nnode = new nodex(st,dr);
         if ((*copil)->dr<=mij)
         {
             nnode->fiust = *copil;
         }
         else
         {
             nnode->fiudr = *copil;
         }
         *copil=nnode;
         updatey(*copil,y,k);
     }
     arb->val = gcd2(
         arb->fiust ? arb->fiust->val : 0 ,
         arb->fiudr ? arb->fiudr->val : 0
     );
}
void updatex(nodey *arb, int st,int dr,int x,int y,long long k)
{
    int mij=(st+dr)/2;
    if (st==dr)
    {
        updatey(&arb->fiux,y,k);
        return;
    }
    if (x<=mij)
    {
        if (arb->fiust==NULL)
        {
            arb->fiust=new nodey(st,mij);
        }
        updatex(arb->fiust,st,mij,x,y,k);
    }
    else
    {
        if (arb->fiudr==NULL)
        {
            arb->fiudr= new nodey(mij+1,dr);
        }
        updatex(arb->fiudr,mij+1,dr,x,y,k);
    }
    ll val = gcd2(
       arb->fiust ? query2(&arb->fiust->fiux,y,y) : 0,
       arb->fiudr ? query2(&arb->fiudr->fiux,y,y) : 0
    );
    updatey(&arb->fiux,y,val);
}
void update(int P, int Q, long long K) {
    P++;
    Q++;
    updatex(root,1,n,P,Q,K);
}
long long calculate(int P, int Q, int U, int V) {
    P++;Q++;U++;V++;
    return query1(root ,1,n,P,Q,U,V);
}
#ifdef HOME
int main()
{
    int n,m,q;
    ifstream cin("date.in");
    ofstream cout("date.out");
    cin>>n>>m>>q;
    init(n,m);
    for (;q--;)
    {
        int tip;
        cin>>tip;
        if (tip==1)
        {
            long long x,y,val;
            cin>>x>>y>>val;
            update(x,y,val);
        }
        else
        {
            long long p,q,u,v;
            cin>>p>>q>>u>>v;
            cout<<calculate(p,q,u,v)<<'\n';
        }
    }
    return 0;
}
#endif // HOME

Compilation message

game.cpp: In constructor 'nodey::nodey(int, int)':
game.cpp:34:19: warning: 'nodey::fiudr' will be initialized after [-Wreorder]
   34 |     nodey *fiust,*fiudr;
      |                   ^~~~~
game.cpp:33:11: warning:   'nodex nodey::fiux' [-Wreorder]
   33 |     nodex fiux;
      |           ^~~~
game.cpp:31:5: warning:   when initialized here [-Wreorder]
   31 |     nodey(int stanga,int dreapta) : st(stanga), dr(dreapta), fiust(NULL), fiudr(NULL), fiux(1,m) {}
      |     ^~~~~
game.cpp: In function 'll query2(nodex*, int, int)':
game.cpp:46:9: warning: unused variable 'mij' [-Wunused-variable]
   46 |     int mij=(arb->st+arb->dr)/2;
      |         ^~~

Subtask #1
10.0 / 10.0

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 296 KB Output is correct
3 Correct 1 ms 292 KB Output is correct
4 Correct 408 ms 12692 KB Output is correct
5 Correct 303 ms 12476 KB Output is correct
6 Correct 398 ms 10044 KB Output is correct
7 Correct 515 ms 9772 KB Output is correct
8 Correct 275 ms 8064 KB Output is correct
9 Correct 394 ms 9860 KB Output is correct
10 Correct 412 ms 9448 KB Output is correct
11 Correct 1 ms 204 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 288 KB Output is correct
5 Correct 1 ms 296 KB Output is correct
6 Correct 1 ms 292 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 723 ms 15548 KB Output is correct
13 Correct 1304 ms 8840 KB Output is correct
14 Correct 223 ms 5620 KB Output is correct
15 Correct 1459 ms 10440 KB Output is correct
16 Correct 176 ms 13988 KB Output is correct
17 Correct 568 ms 11064 KB Output is correct
18 Correct 1110 ms 15964 KB Output is correct
19 Correct 889 ms 15760 KB Output is correct
20 Correct 820 ms 15120 KB Output is correct
21 Correct 0 ms 288 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 324 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 ms 292 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 256 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 444 ms 12708 KB Output is correct
13 Correct 303 ms 12464 KB Output is correct
14 Correct 367 ms 10028 KB Output is correct
15 Correct 424 ms 9664 KB Output is correct
16 Correct 274 ms 7992 KB Output is correct
17 Correct 394 ms 9780 KB Output is correct
18 Correct 369 ms 9472 KB Output is correct
19 Correct 694 ms 15648 KB Output is correct
20 Correct 1325 ms 8844 KB Output is correct
21 Correct 230 ms 5748 KB Output is correct
22 Correct 1464 ms 10532 KB Output is correct
23 Correct 197 ms 14060 KB Output is correct
24 Correct 581 ms 11016 KB Output is correct
25 Correct 1039 ms 15696 KB Output is correct
26 Correct 935 ms 15648 KB Output is correct
27 Correct 817 ms 15056 KB Output is correct
28 Correct 374 ms 43224 KB Output is correct
29 Correct 1056 ms 45448 KB Output is correct
30 Correct 2075 ms 35228 KB Output is correct
31 Correct 1841 ms 28564 KB Output is correct
32 Correct 354 ms 10152 KB Output is correct
33 Correct 416 ms 10760 KB Output is correct
34 Correct 251 ms 39140 KB Output is correct
35 Correct 741 ms 26880 KB Output is correct
36 Correct 1666 ms 43260 KB Output is correct
37 Correct 1236 ms 43464 KB Output is correct
38 Correct 1264 ms 42868 KB Output is correct
39 Correct 1070 ms 35708 KB Output is correct
40 Correct 1 ms 272 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 292 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 288 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 421 ms 12740 KB Output is correct
13 Correct 302 ms 12716 KB Output is correct
14 Correct 400 ms 10088 KB Output is correct
15 Correct 415 ms 9780 KB Output is correct
16 Correct 275 ms 8060 KB Output is correct
17 Correct 408 ms 9856 KB Output is correct
18 Correct 400 ms 9504 KB Output is correct
19 Correct 695 ms 15548 KB Output is correct
20 Correct 1362 ms 8948 KB Output is correct
21 Correct 230 ms 5544 KB Output is correct
22 Correct 1680 ms 10512 KB Output is correct
23 Correct 209 ms 14084 KB Output is correct
24 Correct 711 ms 10984 KB Output is correct
25 Correct 1392 ms 15496 KB Output is correct
26 Correct 1045 ms 15664 KB Output is correct
27 Correct 935 ms 15084 KB Output is correct
28 Correct 445 ms 43124 KB Output is correct
29 Correct 1227 ms 45320 KB Output is correct
30 Correct 2173 ms 35164 KB Output is correct
31 Correct 1943 ms 28444 KB Output is correct
32 Correct 322 ms 10200 KB Output is correct
33 Correct 433 ms 10636 KB Output is correct
34 Correct 256 ms 39084 KB Output is correct
35 Correct 847 ms 26876 KB Output is correct
36 Correct 1778 ms 43164 KB Output is correct
37 Correct 1550 ms 43420 KB Output is correct
38 Correct 1345 ms 42768 KB Output is correct
39 Correct 527 ms 81100 KB Output is correct
40 Correct 1853 ms 82248 KB Output is correct
41 Correct 3190 ms 67116 KB Output is correct
42 Correct 2681 ms 52504 KB Output is correct
43 Correct 481 ms 76792 KB Output is correct
44 Correct 387 ms 10724 KB Output is correct
45 Correct 1098 ms 35812 KB Output is correct
46 Correct 2383 ms 81288 KB Output is correct
47 Correct 2359 ms 80832 KB Output is correct
48 Correct 2264 ms 80464 KB Output is correct
49 Correct 1 ms 204 KB Output is correct