답안 #962820

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
962820 2024-04-14T08:37:59 Z Ice_man 게임 (IOI13_game) C++14
100 / 100
3841 ms 146644 KB
/**
 ____    ____    ____    __________________    ____    ____    ____
||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;
}*/
# 결과 실행 시간 메모리 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
# 결과 실행 시간 메모리 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
# 결과 실행 시간 메모리 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
# 결과 실행 시간 메모리 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
# 결과 실행 시간 메모리 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