oj.uz

Submission #1013656

# Submission time Handle Problem Language Result Execution time Memory
1013656 2024-07-03T18:36:22 Z parsadox2 Game (IOI13_game) C++17
100 / 100
 1745 ms 90848 KB 
#include "game.h"
#include <bits/stdc++.h>
 
using namespace std;
 
int N , M;
 
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;
}
 
struct SEG{
    struct NODE{
        int lc , rc , l , r;
        long long g;
        NODE(){
            lc = 0;  rc = 0;
            g = 0;
        }
    };
    vector <NODE> t;
    NODE emp;
    void Build()
    {
        t.push_back(emp);
        t.push_back(emp);
        t[1].l = 0;
        t[1].r = M;
    }
    void Make_child(int par , int now)
    {
        int mid = (t[par].l + t[par].r) >> 1;
        //cout << "CH " << par << " " << now << " " << t[par].l << " " << t[par].r << " "<< mid << " " << t[now].l << endl;
        if(t[now].l < mid)
        {
            //cout << "L " << endl;
            t[par].lc = now;
        }
        else
        {
            //cout << "R " << endl;
            t[par].rc = now;
        }
    }
    void Set(int id , long long vl , int par = 1 , int node = 1 , int nl = 0 , int nr = M)
    {
        //cout << "NOW " << par << " " << node <<  " " << nl << " " << nr << " " << t[node].l << " " << t[node].r << " " << endl;
        if(par != node && t[node].l == nl && t[node].r == nr)
        {
            Set(id , vl , node , node , nl , nr);
            return;
        }
        if(nr - nl == 1)
        {
            t[node].g = vl;
            return;
        }
        int mid = (nl + nr) >> 1;
        if(par == node)
        {
            if(id < mid)
            {
                if(t[node].lc == 0)
                {
                    int nd = t.size();  t.push_back(emp);
                    t[nd].l = id;  t[nd].r = id + 1;  t[nd].g = vl;
                    t[node].lc = nd;
                    t[node].g = gcd2(t[t[node].rc].g , vl);
                    //cout << "WTF " << t[node].lc << " " << t[t[node].lc].l << " " << t[t[node].lc].r << " " << endl;
                    return;
                }
                Set(id , vl , node , t[node].lc , nl , mid);
            }
            else
            {
                if(t[node].rc == 0)
                {
                    int nd = t.size();  t.push_back(emp);
                    t[nd].l = id;  t[nd].r = id + 1;  t[nd].g = vl;
                    t[node].rc = nd;
                    t[node].g = gcd2(t[t[node].lc].g , vl);
                    //cout << "WTF " << t[node].rc << " " << t[t[node].rc].l << " " << t[t[node].rc].r << " " << endl;
                    return;
                }
                Set(id , vl , node , t[node].rc , mid , nr);
            }
            t[node].g = gcd2(t[t[node].lc].g , t[t[node].rc].g);
            return;
        }
        else
        {
            if(id < mid && t[node].l < mid)
            {
                Set(id , vl , par , node , nl , mid);
                return;
            }
            else if(id >= mid && t[node].l >= mid)
            {
                Set(id , vl , par , node , mid , nr);
                return;
            }
            int nd = t.size();  t.push_back(emp);
            int p = t.size();  t.push_back(emp);
            t[nd].l = id;  t[nd].r = id + 1;  t[nd].g = vl;
            t[p].l = nl;  t[p].r = nr;
            Make_child(p , node);
            Make_child(p , nd);
            Make_child(par , p);
            t[p].g = gcd2(t[t[p].lc].g , t[t[p].rc].g);
            return;
        }
    }
    long long Get(int l , int r , int node = 1 , int nl = 0 , int nr = M)
    {
        if(r <= nl || nr <= l)
            return 0;
        if(l <= nl && nr <= r)
        {
            ////cout << node << " " << nl << " " << nr << " : " << t[node].g << endl;
            return t[node].g;
        }
        long long res = 0;
        if(t[node].lc != 0)
            res = gcd2(res , Get(l , r , t[node].lc , t[t[node].lc].l , t[t[node].lc].r));
        if(t[node].rc != 0)
            res = gcd2(res , Get(l , r , t[node].rc , t[t[node].rc].l , t[t[node].rc].r));
        return res;
    }
    void Debug(int node = 1 , int nl = 0 , int nr = M)
    {
        //cout << "KA KA KAGAN " <<  node << " " << t[node].lc << " " << t[node].rc << " " << t[node].g << " " <<nl << " " << nr << " " << endl;
        if(t[node].lc != 0)
            Debug(t[node].lc , t[t[node].lc].l , t[t[node].lc].r);
        if(t[node].rc != 0)
            Debug(t[node].rc , t[t[node].rc].l , t[t[node].rc].r);
    }
};
 
struct SEG2{
    struct NODE{
        int lc , rc;
        SEG s;
    };
    NODE emp;
    vector <NODE> t;
    void Build()
    {
        emp.s.Build();
        emp.lc = 0;
        emp.rc = 0;
        t.push_back(emp);
        t.push_back(emp);
    }
    void Set(int id , int a , long long b , int node = 1 , int nl = 0 , int nr = N)
    {
        int nd = node;
        if(nr - nl == 1)
        {
            t[nd].s.Set(a , b);
            t[nd].s.Debug();
            return;
        }
        int mid = (nl + nr) >> 1;
        if(id < mid)
        {
            if(t[nd].lc == 0)
            {
                t[nd].lc = t.size();
                t.push_back(emp);
            }
            Set(id , a , b , t[nd].lc , nl , mid);
        }
        else
        {
            if(t[nd].rc == 0)
            {
                t[nd].rc = t.size();
                t.push_back(emp);
            }
            Set(id , a ,  b , t[nd].rc , mid , nr);
        }
        t[nd].s.Set(a , gcd2(t[t[nd].lc].s.Get(a , a + 1) , t[t[nd].rc].s.Get(a , a + 1)));
    }
    long long Get(int l , int r , int s , int e , int node = 1 , int nl = 0 , int nr = N)
    {
        if(r <= nl || nr <= l)
            return 0;
        if(l <= nl && nr <= r)
        {
            //t[node].s.Debug(); 
            long long x = t[node].s.Get(s , e);
            return x;
        }
        int mid = (nl + nr) >> 1;
        return gcd2(Get(l , r , s , e , t[node].lc , nl , mid) , Get(l , r , s , e , t[node].rc , mid , nr));
    }
} seg;
 
void init(int R, int C) {
    M = C;
    N = R;
    seg.Build();
}
 
void update(int P, int Q, long long K) {
    seg.Set(P , Q , K);
}
 
long long calculate(int P, int Q, int U, int V) {
    int l = min(P , U) , r = max(P , U);
    int s = min(Q , V) , e = max(Q , V);
    return seg.Get(l , r + 1 , s , e + 1);
    long long res = 0;
    /*for(int i = l ; i <= r ; i++)  for(int j = s ; j <= e ; j++)
    {
        res = gcd2(res , ar[i][j]);
    }
    if(res != seg.Get(l , r + 1 , s , e + 1))
    {
        cout << "CORRECT : " << res << " WRONG : " << seg.Get(l , r + 1 , s , e + 1) << endl;
    }
    return res;*/
}
 
/*signed main()
{
    int R, C, N;
    int P, Q, U, V;
    long long K;
    int i, type;
 
    assert(scanf("%d", &R) == 1);
    assert(scanf("%d", &C) == 1);
    assert(scanf("%d", &N) == 1);
 
    init(R, C);
    std::vector<long long> answers;
 
    for (i = 0; i < N; i++) {
        assert(scanf("%d", &type) == 1);
        if (type == 1) {
            assert(scanf("%d%d%lld", &P, &Q, &K) == 3);
            update(P, Q, K);
        } else if (type == 2) {
            assert(scanf("%d%d%d%d", &P, &Q, &U, &V) == 4);
            answers.push_back(calculate(P, Q, U, V));
        } 
    }
    for (auto answer: answers) {
      printf("%lld\n", answer);
    }
 
    return 0;
}*/
/*
2 3 4
1 0 0 20
1 0 2 15
1 1 1 12
2 0 0 1 1

100 100 5
1 0 0 30
1 0 40 42
1 99 0 70
1 99 99 105
2 0 0 99 99

1 5 4
1 0 2 11467
1 0 1 30498
1 0 0 9024
2 0 1 0 2
*/

Compilation message

game.cpp: In function 'long long int calculate(int, int, int, int)':
game.cpp:219:15: warning: unused variable 'res' [-Wunused-variable]
  219 |     long long res = 0;
      |               ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 504 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 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct

Subtask #2
27.0 / 27.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 0 ms 348 KB Output is correct
4 Correct 309 ms 7120 KB Output is correct
5 Correct 190 ms 7312 KB Output is correct
6 Correct 254 ms 3972 KB Output is correct
7 Correct 344 ms 3740 KB Output is correct
8 Correct 172 ms 3224 KB Output is correct
9 Correct 302 ms 3712 KB Output is correct
10 Correct 265 ms 3424 KB Output is correct
11 Correct 1 ms 348 KB Output is correct

Subtask #3
26.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 1 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 0 ms 344 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 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 404 ms 9660 KB Output is correct
13 Correct 670 ms 3888 KB Output is correct
14 Correct 129 ms 852 KB Output is correct
15 Correct 829 ms 4688 KB Output is correct
16 Correct 114 ms 7760 KB Output is correct
17 Correct 424 ms 5380 KB Output is correct
18 Correct 624 ms 8016 KB Output is correct
19 Correct 535 ms 8192 KB Output is correct
20 Correct 492 ms 7416 KB Output is correct
21 Correct 0 ms 348 KB Output is correct

Subtask #4
17.0 / 17.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 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 344 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 289 ms 7228 KB Output is correct
13 Correct 195 ms 7392 KB Output is correct
14 Correct 271 ms 3968 KB Output is correct
15 Correct 290 ms 3652 KB Output is correct
16 Correct 185 ms 3212 KB Output is correct
17 Correct 297 ms 3700 KB Output is correct
18 Correct 261 ms 3392 KB Output is correct
19 Correct 403 ms 9924 KB Output is correct
20 Correct 695 ms 3808 KB Output is correct
21 Correct 143 ms 852 KB Output is correct
22 Correct 826 ms 4724 KB Output is correct
23 Correct 119 ms 7764 KB Output is correct
24 Correct 410 ms 5436 KB Output is correct
25 Correct 609 ms 8056 KB Output is correct
26 Correct 559 ms 8272 KB Output is correct
27 Correct 559 ms 7508 KB Output is correct
28 Correct 354 ms 39440 KB Output is correct
29 Correct 689 ms 41900 KB Output is correct
30 Correct 1050 ms 28556 KB Output is correct
31 Correct 995 ms 22656 KB Output is correct
32 Correct 225 ms 1108 KB Output is correct
33 Correct 269 ms 1640 KB Output is correct
34 Correct 148 ms 37896 KB Output is correct
35 Correct 530 ms 20500 KB Output is correct
36 Correct 870 ms 38928 KB Output is correct
37 Correct 783 ms 39800 KB Output is correct
38 Correct 823 ms 39380 KB Output is correct
39 Correct 737 ms 35096 KB Output is correct
40 Correct 0 ms 348 KB Output is correct

Subtask #5
20.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 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 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 388 ms 7088 KB Output is correct
13 Correct 214 ms 7492 KB Output is correct
14 Correct 312 ms 4200 KB Output is correct
15 Correct 319 ms 3772 KB Output is correct
16 Correct 201 ms 3216 KB Output is correct
17 Correct 343 ms 3512 KB Output is correct
18 Correct 312 ms 3452 KB Output is correct
19 Correct 481 ms 9744 KB Output is correct
20 Correct 815 ms 4036 KB Output is correct
21 Correct 159 ms 852 KB Output is correct
22 Correct 821 ms 4744 KB Output is correct
23 Correct 119 ms 7764 KB Output is correct
24 Correct 446 ms 5200 KB Output is correct
25 Correct 652 ms 8092 KB Output is correct
26 Correct 627 ms 8272 KB Output is correct
27 Correct 542 ms 7504 KB Output is correct
28 Correct 396 ms 39088 KB Output is correct
29 Correct 805 ms 41604 KB Output is correct
30 Correct 1149 ms 28436 KB Output is correct
31 Correct 1066 ms 22300 KB Output is correct
32 Correct 303 ms 5768 KB Output is correct
33 Correct 302 ms 6308 KB Output is correct
34 Correct 190 ms 42624 KB Output is correct
35 Correct 587 ms 25872 KB Output is correct
36 Correct 996 ms 44300 KB Output is correct
37 Correct 886 ms 45260 KB Output is correct
38 Correct 905 ms 43728 KB Output is correct
39 Correct 471 ms 85676 KB Output is correct
40 Correct 1287 ms 86892 KB Output is correct
41 Correct 1745 ms 60428 KB Output is correct
42 Correct 1729 ms 45092 KB Output is correct
43 Correct 366 ms 85028 KB Output is correct
44 Correct 334 ms 10600 KB Output is correct
45 Correct 793 ms 45076 KB Output is correct
46 Correct 1527 ms 90848 KB Output is correct
47 Correct 1351 ms 90652 KB Output is correct
48 Correct 1358 ms 90428 KB Output is correct
49 Correct 1 ms 348 KB Output is correct