Submission #1013160

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013160		parsadox2	Game (IOI13_game)	C++17	0 / 100	11 ms	24420 KiB

game

#include "game.h"
#include <bits/stdc++.h>

using namespace std;

const int N = 1e9 + 2;

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;
        long long g;
    };
    vector <NODE> t;
    NODE emp;
    int root;
    void Build()
    {
        root = 0;
        emp.lc = 0;
        emp.rc = 0;
        emp.g = 0;
        t.push_back(emp);
    }
    int Set(int id , long long vl , int node , int nl = 0 , int nr = N)
    {
        int nd = t.size();
        t.push_back(t[node]);
        if(nr - nl == 1)
        {
            t[nd].g = vl;
            t[nd].lc = nd;
            t[nd].rc = nd;
            //cout << "col " << nl << " " << nr << " " << nd << " " << t[nd].lc << " " << t[nd].rc << " " << t[t[nd].lc].g << " " << t[t[nd].rc].g << endl;
            //cout << t[nd].g << endl;
            return nd;
        }
        int mid = (nl + nr) >> 1;
        if(id < mid)
        {
            int x = Set(id , vl , t[nd].lc , nl , mid);
            //cout << "WTF " << nd << " " << x << endl;
            t[nd].lc = x;
        }
        else
        {
            int x = Set(id , vl , t[nd].rc , mid , nr);
            t[nd].rc = x;
        }
        t[nd].g = gcd2(t[t[nd].lc].g , t[t[nd].rc].g);
        //cout << "col " << nl << " " << nr << " " << nd << " " << t[nd].lc << " " << t[nd].rc << " " << t[t[nd].lc].g << " " << t[t[nd].rc].g << endl;
        //cout << t[nd].g << endl;
        return nd;
    }
    long long Get(int l , int r , int node , int nl = 0 , int nr = N)
    {
        if(r <= nl || nr <= l)
            return 0;
        if(l <= nl && nr <= r)
            return t[node].g;
        int mid = (nl + nr) >> 1;
        return gcd2(Get(l , r , t[node].lc , nl , mid) , Get(l , r , t[node].rc , mid , nr));
    }
};

struct SEG2{
    struct NODE{
        int lc , rc;
        SEG s;
    };
    NODE emp;
    vector <NODE> t;
    int root;
    void Build()
    {
        emp.s.Build();
        root = 0;
        emp.lc = 0;
        emp.rc = 0;
        t.push_back(emp);
    }
    int Set(int id , int a , long long b , int node , int nl = 0 , int nr = N)
    {
       // //cout << id << " " << a << " " << b << endl;
        int nd = t.size();  t.push_back(t[node]);
        if(nr - nl == 1)
        {
            //cout << "ROW " << nl << " " << nr << endl;
            int x = t[nd].s.Set(a , b , t[nd].s.root);
            t[nd].s.root = x;
            return nd;
        }
        int mid = (nl + nr) >> 1;
        if(id < mid)
        {
            int x = Set(id , a , b , t[nd].lc , nl , mid);
            t[nd].lc = x;
        }
        else
        {
            int x = Set(id , a ,  b , t[nd].rc , mid , nr);
            t[nd].rc = x;
        }
        //cout << "ROW " << nl << " " << nr << endl;
        t[nd].s.root = t[nd].s.Set(a , gcd2(t[t[nd].lc].s.Get(a , a + 1 , t[t[nd].lc].s.root) , t[t[nd].rc].s.Get(a , a + 1 , t[t[nd].rc].s.root)) , t[nd].s.root);
        return nd;
    }
    long long Get(int l , int r , int s , int e , int node , int nl = 0 , int nr = N)
    {
        if(r <= nl || nr <= l)
            return 0;
        if(l <= nl && nr <= r)
        {
            int x = t[node].s.Get(s , e , t[node].s.root);
            ////cout << "RANGOOL " << l << " " << r << " " << s << " " << e << " " << x << endl;
            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) {
    seg.Build();
}

void update(int P, int Q, long long K) {
    seg.root = seg.Set(P , Q , K , seg.root);
}

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 , seg.root);
}

/*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
*/

• Subtask 1: 0 / 10
• Subtask 2: 0 / 27
• Subtask 3: 0 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20