Submission #1013656

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013656		parsadox2	Game (IOI13_game)	C++17	100 / 100	1745 ms	90848 KiB

game

#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 (stderr)

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 / 10
• Subtask 2: 27 / 27
• Subtask 3: 26 / 26
• Subtask 4: 17 / 17
• Subtask 5: 20 / 20