Submission #962808

#	Time	Username	Problem	Language	Result	Execution time	Memory
962808		Ice_man	Game (IOI13_game)	C++14	0 / 100	1105 ms	159084 KiB

game

/**
 ____    ____    ____    __________________    ____    ____    ____
||I ||  ||c ||  ||e ||  ||                ||  ||M ||  ||a ||  ||n ||
||__||  ||__||  ||__||  ||________________||  ||__||  ||__||  ||__||
|/__\|  |/__\|  |/__\|  |/________________\|  |/__\|  |/__\|  |/__\|

*/

#include "game.h"
#include <map>
#include <iostream>
#include <chrono>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <random>

#define maxn 22001
#define maxr 20000005
#define maxn2 205
#define maxlog 20
#define INF 1000000010
#define LINF 1000000000000000005
#define endl '\n'
#define pb(x) push_back(x)
#define X first
#define Y second
#define control cerr<<"passed"<<endl;

#pragma GCC optimize("O3" , "Ofast" , "unroll-loops" , "fast-math")
#pragma GCC target("avx2")

using namespace std;

/**std::chrono::high_resolution_clock::time_point startT, currT;
constexpr double TIME_MULT = 1;

double timePassed()
{
    using namespace std::chrono;
    currT = high_resolution_clock::now();
    double time = duration_cast<duration<double>>(currT - startT).count();
    return time * TIME_MULT;
}*/

typedef long long ll;

mt19937 mt(time(nullptr));

int rands[maxr];
int lastr;


struct Node
{
    int p , key;
    int left , right;
    Node *l , *r;
    ll a;
    ll gcd;

    Node()
    {
        l = nullptr;
        r = nullptr;
    }


    Node(int _pos , ll _a)
    {
        l = nullptr;
        r = nullptr;

        left = _pos;
        right = _pos;
        p = _pos;

        a = _a;
        gcd = _a;

        key = rand();
    }


    void pull()
    {
        gcd = a;
        left = p;
        right = p;

        if(l != nullptr)
            gcd = __gcd(gcd , l -> gcd);

        if(r != nullptr)
            gcd = __gcd(gcd , r -> gcd);

        if(l != nullptr)
            left = l -> left;

        if(r != nullptr)
            right = r -> right;
    }

};




struct treap
{
    Node *root;

    void split(Node *node , int qp , Node* &left , Node* &right)
    {
        if(node == nullptr)
        {
            left = nullptr;
            right = nullptr;

            return;
        }

        if(node -> p < qp)
        {
            split(node -> r , qp , left , right);
            node -> r = left;
            left = node;
        }
        else
        {
            split(node -> l , qp , left , right);
            node -> l = right;
            right = node;

        }

        node -> pull();
    }


    Node* _merge(Node *left , Node *right)
    {
        if(left == nullptr)
            return right;

        if(right == nullptr)
            return left;

        if(left -> key < right -> key)
        {
            left -> r = _merge(left -> r , right);
            left -> pull();

            return left;
        }
        else
        {
            right -> l = _merge(left , right -> l);
            right -> pull();

            return right;
        }
    }


    void update(Node *node , int qp , ll qval)
    {
        if(node -> p == qp)
        {
            node -> a = qval;
            node -> pull();

            return;
        }

        if(node -> p > qp)
            update(node -> l , qp , qval);
        else
            update(node -> r , qp , qval);

        node -> pull();
    }

    bool _find(int qp)
    {
        Node *pom = root;

        while(pom != nullptr)
        {
            if(pom -> p == qp)
                return true;

            if(pom -> p > qp)
                pom = pom -> l;
            else
                pom = pom -> r;
        }

        return false;
    }


    ll fake_query(Node *node , int ql , int qr)
    {
        if(node -> right < ql || qr < node -> left)
            return 0;

        if(ql <= node -> left && node -> right <= qr)
            return node -> gcd;


        ll q = 0;
        if(ql <= node -> p && node -> p <= qr)
            q = node -> a;

        if(node -> l != nullptr)
            q = __gcd(q , fake_query(node -> l , ql , qr));

        if(node -> r != nullptr)
            q = __gcd(q , fake_query(node -> r , ql , qr));

        return q;
    }

    void add(int qp , ll qval)
    {
        if(_find(qp) == true)
            update(root , qp , qval);
        else
        {
            Node *poml , *pomr;
            split(root , qp , poml , pomr);

            root = _merge(_merge(poml , new Node(qp , qval)) , pomr);
        }
    }

    ll query(int ql , int qr)
    {
        if(root == nullptr)
            return 0;
        return fake_query(root , ql , qr);
    }


    treap()
    {
        srand(rand());
        root = nullptr;
    }

};





struct tr
{
    tr *l , *r;
    treap node;
    int li , ri;


    tr(int ql , int qr)
    {
        l = nullptr;
        r = nullptr;

        li = ql;
        ri = qr;
    }


    void makel()
    {
        if(l == nullptr)
            l = new tr(li , (li + ri) / 2);
    }

    void maker()
    {
        if(r == nullptr)
            r = new tr((li + ri) / 2 + 1 , ri);
    }


    ll query(int xl , int xr , int ql , int qr)
    {
        if(ri < xl || xr < li)
            return 0;

        if(xl <= li && ri <= xr)
            return node.query(ql , qr);

        ll a = 0;

        if(l != nullptr)
            a = __gcd(a , l -> query(xl , xr , ql , qr));
        else
            a = __gcd(a , r -> query(xl , xr , ql , qr));

        return a;
    }



    void pull(int qp)
    {
        ll a = 0;
        if(l != nullptr)
            a = __gcd(a , l -> node.query(qp , qp));

        if(r != nullptr)
            a = __gcd(a , r -> node.query(qp , qp));

        node.add(qp , a);
    }


    void update(int ql , int qr , ll qval)
    {
        if(ri < ql || ql < li)
            return;

        if(li == ri)
        {
            node.add(qr , qval);
            return;
        }

        int mid = (li + ri) / 2;

        if(ql <= mid)
        {
            makel();
            l -> update(ql , qr , qval);
        }
        else
        {
            maker();
            r -> update(ql , qr , qval);
        }

        pull(qr);
    }


    tr()
    {
        l = nullptr;
        r = nullptr;
    }
};


tr tree;


void init(int R , int C)
{
    for(int i = 0; i < maxr; i++)
        rands[i] = i;
    random_shuffle(rands , rands + maxr);


    tree = tr(0 , R - 1);
}



void update(int P , int Q , ll K)
{
    tree.update(P , Q , K);
}


ll calculate(int P , int Q , int U , int V)
{
    return tree.query(P , U , Q , V);
}



/**int main()
{

    #ifdef ONLINE_JUDGE /// promeni
        freopen("input.in", "r", stdin);
        freopen("taxi.out", "w", stdout);
    #endif

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    //startT = std::chrono::high_resolution_clock::now();





    return 0;
}*/

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