oj.uz

Submission #1013650

# Submission time Handle Problem Language Result Execution time Memory
1013650 2024-07-03T18:27:26 Z parsadox2 Game (IOI13_game) C++17
80 / 100
 13000 ms 92028 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 600 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 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 436 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 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 1 ms 348 KB Output is correct
3 Correct 0 ms 440 KB Output is correct
4 Correct 3238 ms 11568 KB Output is correct
5 Correct 2526 ms 11332 KB Output is correct
6 Correct 2467 ms 8516 KB Output is correct
7 Correct 5788 ms 8464 KB Output is correct
8 Correct 731 ms 7444 KB Output is correct
9 Correct 4248 ms 8364 KB Output is correct
10 Correct 4937 ms 8092 KB Output is correct
11 Correct 0 ms 348 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 436 KB Output is correct
3 Correct 1 ms 440 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 2033 ms 13832 KB Output is correct
13 Correct 1923 ms 7668 KB Output is correct
14 Correct 179 ms 5712 KB Output is correct
15 Correct 2311 ms 9280 KB Output is correct
16 Correct 1348 ms 11856 KB Output is correct
17 Correct 901 ms 10060 KB Output is correct
18 Correct 2851 ms 13276 KB Output is correct
19 Correct 1906 ms 13632 KB Output is correct
20 Correct 1862 ms 12732 KB Output is correct
21 Correct 0 ms 344 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 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 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 1 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 3079 ms 11424 KB Output is correct
13 Correct 2167 ms 11472 KB Output is correct
14 Correct 2241 ms 8608 KB Output is correct
15 Correct 5525 ms 8432 KB Output is correct
16 Correct 773 ms 7332 KB Output is correct
17 Correct 4425 ms 8232 KB Output is correct
18 Correct 5164 ms 8008 KB Output is correct
19 Correct 2295 ms 13848 KB Output is correct
20 Correct 2000 ms 7804 KB Output is correct
21 Correct 198 ms 5616 KB Output is correct
22 Correct 2354 ms 9300 KB Output is correct
23 Correct 1524 ms 11856 KB Output is correct
24 Correct 913 ms 10252 KB Output is correct
25 Correct 2850 ms 13180 KB Output is correct
26 Correct 2064 ms 13468 KB Output is correct
27 Correct 1963 ms 12920 KB Output is correct
28 Correct 2028 ms 50612 KB Output is correct
29 Correct 3874 ms 52300 KB Output is correct
30 Correct 3574 ms 34320 KB Output is correct
31 Correct 2611 ms 27972 KB Output is correct
32 Correct 291 ms 10152 KB Output is correct
33 Correct 380 ms 10576 KB Output is correct
34 Correct 8061 ms 44712 KB Output is correct
35 Correct 1118 ms 31600 KB Output is correct
36 Correct 4377 ms 49912 KB Output is correct
37 Correct 2682 ms 49312 KB Output is correct
38 Correct 2689 ms 49168 KB Output is correct
39 Correct 1841 ms 44916 KB Output is correct
40 Correct 0 ms 344 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory 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 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 440 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 3257 ms 11380 KB Output is correct
13 Correct 2378 ms 11336 KB Output is correct
14 Correct 2228 ms 8676 KB Output is correct
15 Correct 5305 ms 8324 KB Output is correct
16 Correct 730 ms 7564 KB Output is correct
17 Correct 4284 ms 8120 KB Output is correct
18 Correct 4999 ms 8004 KB Output is correct
19 Correct 2179 ms 13908 KB Output is correct
20 Correct 1923 ms 7776 KB Output is correct
21 Correct 181 ms 5712 KB Output is correct
22 Correct 2387 ms 9160 KB Output is correct
23 Correct 1502 ms 11932 KB Output is correct
24 Correct 953 ms 10188 KB Output is correct
25 Correct 2905 ms 13368 KB Output is correct
26 Correct 2065 ms 13580 KB Output is correct
27 Correct 1816 ms 12936 KB Output is correct
28 Correct 1784 ms 49864 KB Output is correct
29 Correct 3913 ms 52244 KB Output is correct
30 Correct 3484 ms 34336 KB Output is correct
31 Correct 2589 ms 27924 KB Output is correct
32 Correct 277 ms 10064 KB Output is correct
33 Correct 400 ms 10584 KB Output is correct
34 Correct 9019 ms 45872 KB Output is correct
35 Correct 1156 ms 31512 KB Output is correct
36 Correct 4048 ms 49056 KB Output is correct
37 Correct 2521 ms 50392 KB Output is correct
38 Correct 2510 ms 48504 KB Output is correct
39 Correct 4737 ms 90696 KB Output is correct
40 Correct 11389 ms 92028 KB Output is correct
41 Correct 8909 ms 66008 KB Output is correct
42 Correct 6429 ms 49972 KB Output is correct
43 Execution timed out 13021 ms 81396 KB Time limit exceeded
44 Halted 0 ms 0 KB -