Submission #962820

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
962820	2024-04-14T08:37:59 Z	Ice_man	Game (IOI13_game)	C++14	100 / 100	3841 ms	146644 KB

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()
    {
        l = nullptr;
        r = nullptr;
    }


    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));
        
        if(r != nullptr)
            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 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

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	984 ms	78696 KB	Output is correct
2	Correct	981 ms	78696 KB	Output is correct
3	Correct	992 ms	78696 KB	Output is correct
4	Correct	929 ms	78700 KB	Output is correct
5	Correct	1052 ms	78704 KB	Output is correct
6	Correct	1067 ms	78704 KB	Output is correct
7	Correct	923 ms	78700 KB	Output is correct
8	Correct	1099 ms	78704 KB	Output is correct
9	Correct	1130 ms	78696 KB	Output is correct
10	Correct	1014 ms	78700 KB	Output is correct
11	Correct	988 ms	78704 KB	Output is correct
12	Correct	843 ms	78704 KB	Output is correct

Subtask #2

27.0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	985 ms	78696 KB	Output is correct
2	Correct	996 ms	78692 KB	Output is correct
3	Correct	980 ms	78680 KB	Output is correct
4	Correct	1347 ms	87888 KB	Output is correct
5	Correct	1034 ms	87920 KB	Output is correct
6	Correct	1317 ms	85612 KB	Output is correct
7	Correct	1379 ms	85000 KB	Output is correct
8	Correct	1202 ms	84188 KB	Output is correct
9	Correct	1315 ms	84988 KB	Output is correct
10	Correct	1351 ms	84808 KB	Output is correct
11	Correct	828 ms	78700 KB	Output is correct

Subtask #3

26.0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	896 ms	78692 KB	Output is correct
2	Correct	881 ms	78696 KB	Output is correct
3	Correct	855 ms	78928 KB	Output is correct
4	Correct	973 ms	78928 KB	Output is correct
5	Correct	925 ms	78684 KB	Output is correct
6	Correct	968 ms	78700 KB	Output is correct
7	Correct	942 ms	78700 KB	Output is correct
8	Correct	982 ms	78696 KB	Output is correct
9	Correct	865 ms	78696 KB	Output is correct
10	Correct	870 ms	78704 KB	Output is correct
11	Correct	938 ms	78700 KB	Output is correct
12	Correct	1379 ms	90228 KB	Output is correct
13	Correct	1721 ms	84448 KB	Output is correct
14	Correct	1084 ms	82032 KB	Output is correct
15	Correct	1662 ms	85804 KB	Output is correct
16	Correct	1141 ms	88176 KB	Output is correct
17	Correct	1497 ms	85880 KB	Output is correct
18	Correct	1813 ms	88812 KB	Output is correct
19	Correct	1904 ms	88952 KB	Output is correct
20	Correct	1830 ms	88436 KB	Output is correct
21	Correct	1014 ms	78700 KB	Output is correct

Subtask #4

17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	943 ms	78692 KB	Output is correct
2	Correct	988 ms	78692 KB	Output is correct
3	Correct	1004 ms	78696 KB	Output is correct
4	Correct	1004 ms	78700 KB	Output is correct
5	Correct	996 ms	78696 KB	Output is correct
6	Correct	954 ms	78696 KB	Output is correct
7	Correct	941 ms	78696 KB	Output is correct
8	Correct	907 ms	78696 KB	Output is correct
9	Correct	941 ms	78700 KB	Output is correct
10	Correct	885 ms	78696 KB	Output is correct
11	Correct	1000 ms	78700 KB	Output is correct
12	Correct	1244 ms	87916 KB	Output is correct
13	Correct	1120 ms	87920 KB	Output is correct
14	Correct	1319 ms	85108 KB	Output is correct
15	Correct	1410 ms	85008 KB	Output is correct
16	Correct	1124 ms	84028 KB	Output is correct
17	Correct	1397 ms	85100 KB	Output is correct
18	Correct	1334 ms	84724 KB	Output is correct
19	Correct	1372 ms	90012 KB	Output is correct
20	Correct	1810 ms	84684 KB	Output is correct
21	Correct	1071 ms	82112 KB	Output is correct
22	Correct	1837 ms	85824 KB	Output is correct
23	Correct	1066 ms	88160 KB	Output is correct
24	Correct	1506 ms	85924 KB	Output is correct
25	Correct	1841 ms	88920 KB	Output is correct
26	Correct	1723 ms	88896 KB	Output is correct
27	Correct	1697 ms	88564 KB	Output is correct
28	Correct	1546 ms	112652 KB	Output is correct
29	Correct	2098 ms	115544 KB	Output is correct
30	Correct	2067 ms	105076 KB	Output is correct
31	Correct	1942 ms	99612 KB	Output is correct
32	Correct	1112 ms	84208 KB	Output is correct
33	Correct	1128 ms	84596 KB	Output is correct
34	Correct	1490 ms	110608 KB	Output is correct
35	Correct	1826 ms	98936 KB	Output is correct
36	Correct	2529 ms	113296 KB	Output is correct
37	Correct	2215 ms	113456 KB	Output is correct
38	Correct	2254 ms	112532 KB	Output is correct
39	Correct	2090 ms	106844 KB	Output is correct
40	Correct	872 ms	78700 KB	Output is correct

Subtask #5

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	861 ms	78936 KB	Output is correct
2	Correct	1162 ms	78700 KB	Output is correct
3	Correct	930 ms	78696 KB	Output is correct
4	Correct	1002 ms	78700 KB	Output is correct
5	Correct	1077 ms	78756 KB	Output is correct
6	Correct	1053 ms	78696 KB	Output is correct
7	Correct	1006 ms	78696 KB	Output is correct
8	Correct	1012 ms	78704 KB	Output is correct
9	Correct	891 ms	78696 KB	Output is correct
10	Correct	914 ms	78696 KB	Output is correct
11	Correct	1165 ms	78696 KB	Output is correct
12	Correct	1333 ms	88032 KB	Output is correct
13	Correct	1191 ms	87928 KB	Output is correct
14	Correct	1424 ms	85084 KB	Output is correct
15	Correct	1472 ms	85304 KB	Output is correct
16	Correct	1222 ms	83996 KB	Output is correct
17	Correct	1386 ms	85184 KB	Output is correct
18	Correct	1358 ms	84728 KB	Output is correct
19	Correct	1542 ms	89944 KB	Output is correct
20	Correct	1777 ms	84384 KB	Output is correct
21	Correct	1252 ms	82032 KB	Output is correct
22	Correct	1859 ms	85832 KB	Output is correct
23	Correct	1098 ms	88172 KB	Output is correct
24	Correct	1553 ms	86608 KB	Output is correct
25	Correct	1892 ms	89356 KB	Output is correct
26	Correct	1705 ms	89384 KB	Output is correct
27	Correct	1763 ms	88744 KB	Output is correct
28	Correct	1753 ms	112248 KB	Output is correct
29	Correct	2131 ms	115340 KB	Output is correct
30	Correct	2198 ms	104896 KB	Output is correct
31	Correct	2143 ms	99696 KB	Output is correct
32	Correct	1137 ms	84028 KB	Output is correct
33	Correct	1257 ms	84880 KB	Output is correct
34	Correct	1709 ms	110500 KB	Output is correct
35	Correct	1853 ms	98856 KB	Output is correct
36	Correct	2692 ms	112952 KB	Output is correct
37	Correct	2318 ms	113016 KB	Output is correct
38	Correct	2376 ms	112624 KB	Output is correct
39	Correct	2095 ms	144504 KB	Output is correct
40	Correct	3228 ms	146644 KB	Output is correct
41	Correct	3176 ms	130240 KB	Output is correct
42	Correct	2644 ms	118364 KB	Output is correct
43	Correct	2143 ms	142880 KB	Output is correct
44	Correct	1273 ms	84544 KB	Output is correct
45	Correct	2190 ms	106468 KB	Output is correct
46	Correct	3841 ms	145304 KB	Output is correct
47	Correct	3714 ms	145304 KB	Output is correct
48	Correct	3722 ms	144772 KB	Output is correct
49	Correct	1069 ms	78704 KB	Output is correct