oj.uz

Submission #265195

# Submission time Handle Problem Language Result Execution time Memory
265195 2020-08-14T13:52:54 Z evpipis Game (IOI13_game) C++11
100 / 100
 9799 ms 67616 KB 
#include "game.h"

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define mp make_pair
typedef pair<int, int> ii;
typedef long long ll;
const int inf = 1e9+10;

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 treap{
    struct node{
        ii pos;
        int prior;
        ll val, res;
        node *lef, *rig;

        node(ii p = mp(0, 0), ll v = 0){
            pos = p;
            prior = rand();
            val = v;
            res = v;

            lef = NULL;
            rig = NULL;
        }
    };

    // try using my own null
    typedef node *pnode;
    pnode root;

    ///this one
    //map<int, ll> mym;

    treap(){
        root = NULL;
        /// this one
        //mym.clear();
    }

    void upd(pnode t){
        if (t == NULL)
            return;

        t->res = t->val;
        if (t->lef != NULL)
            t->res = gcd2(t->res, t->lef->res);
        if (t->rig != NULL)
            t->res = gcd2(t->res, t->rig->res);
    }

    void split(pnode t, pnode &l, pnode &r, ii k){
        if (t == NULL)
            return void(l = r = NULL);

        if (t->pos <= k)
            split(t->rig, t->rig, r, k), l = t;
        else
            split(t->lef, l, t->lef, k), r = t;

        upd(t);
    }

    void join(pnode &t, pnode l, pnode r){
        if (l == NULL)
            return void(t = r);
        if (r == NULL)
            return void(t = l);

        if (l->prior > r->prior)
            join(l->rig, l->rig, r), t = l;
        else
            join(r->lef, l, r->lef), t = r;

        upd(t);
    }

    void add(ii p, ll v){
        /// this one
        //mym[p] = v;
        //return;

        pnode l = NULL, mid = NULL, r = NULL;

        split(root, l, r, p);
        split(l, l, mid, mp(p.fi, p.se-1));

        mid = new node(p, v);

        join(l, l, mid);
        join(root, l, r);
    }

    ll ask(int a, int b){
        /// this one
        //ll hey = 0;
        //for (auto it: mym)
          //  if (a <= it.first && it.first <= b)
            //    hey = gcd2(hey, it.second);
        //return hey;


        pnode l = NULL, mid = NULL, r = NULL;

        split(root, l, r, mp(b, inf));
        split(l, l, mid, mp(a-1, inf));

        ll ans = 0;
        if (mid != NULL)
            ans = mid->res;

        join(l, l, mid);
        join(root, l, r);

        return ans;
    }

    /*void print(pnode t){
        if (t == NULL)
            return;

        print(t->lef);
        printf(" (%d, %lld)", t->pos, t->val);
        print(t->rig);
    }

    void print(){
        /// this one
        //printf("treap now:");
        //for (auto it: mym)
          //  printf(" (%d, %lld)", it.first, it.second);
        //printf("\n");
        //return;

        printf("treap now:");
        print(root);
        printf("\n");
    }*/
};

ll tot = 0;

struct seg_tree{
    struct node{
        treap tree;
        node *lef, *rig;

        node(node *l = NULL, node *r = NULL){
            tree = treap();

            lef = l;
            rig = r;
        }
    };

    typedef node *pnode;
    pnode root, null;
    int mx;

    /// this one
    //vector<treap> myv;

    seg_tree(int m = 0){
        null = new node();
        null->lef = null->rig = null;
        root = null;
        mx = m;

        //printf("seg_tree initialized, mx = %d\n", mx);
        //printf("starting gcd = %lld\n", root->tree.ask(0, 100));

        ///this one
        //myv.resize(m);
    }

    pnode update(pnode t, int l, int r, int i, int j, ll v){
        if (t == null)
            t = new node(null, null);
        t->tree.add(mp(j, i), v);

        if (l == r)
            return t;

        int mid = (l+r)/2;
        if (i <= mid)
            t->lef = update(t->lef, l, mid, i, j, v);
        else
            t->rig = update(t->rig, mid+1, r, i, j, v);
        return t;
    }

    void add(int r, int c, ll v){
        /// this one
        //myv[r].add(c, v);
        //return;

        root = update(root, 0, mx-1, r, c, v);

        int deb = 0;
        //if (63 <= r && r <= 83 && 31 <= c && c <= 42)
          //  deb = 1;

        if (deb)
            printf("r = %d, c = %d, v = %lld\n", r, c, v);
        if (deb)
            tot = gcd2(tot, v);
        if (deb)
            printf("tot = %lld\n", tot);
        if (deb)
            printf("rows:63-64, colss:37, ans = %lld\n", query(root, 0, mx-1, 63, 64, 37, 37));
        //if (deb)
          //  print(root, 0, mx-1);

        //printf("seg_tree::making (%d, %d) = %lld\n", r, c, v);
        //printf("now root: %lld\n", query(root, 0, mx-1, 0, mx-1, 0, 1000000));
    }

    ll query(pnode t, int l, int r, int i, int j, int a, int b){
        int deb = 0;
        if (63 == i && j == 83 && 31 == a && b == 42)
            deb = 1;

        //if (deb)
          //  printf("query: l = %d, r = %d\n", l, r);

        if (r < i || j < l)
            return 0;
        if (i <= l && r <= j){
            //if (deb)
              //  printf("l = %d, r = %d, res = %lld\n", l, r, t->tree.ask(a, b)), t->tree.print();
            //printf("query, l = %d, r = %d, i = %d, j = %d\n", l, r, i, j);
            //t->tree.print();
            return t->tree.ask(a, b);
        }

        int mid = (l+r)/2;
        return gcd2(query(t->lef, l, mid, i, j, a, b), query(t->rig, mid+1, r, i, j, a, b));
    }

    ll ask(int ar, int br, int ac, int bc){
        /// this one
        //ll hey = 0;
        //for (int i = ar; i <= br; i++)
          //  hey = gcd2(hey, myv[i].ask(ac, bc));
        //return hey;

        //printf("seg_tree::asking for (%d, %d) and (%d, %d)\n", ar, br, ac, bc);
        //printf("null is: %lld\n", null->tree.ask(0, 10000));
        return query(root, 0, mx-1, ar, br, ac, bc);
    }

    /*void print(pnode t, int l, int r){
        if (l == r){
            printf("row%d: ", l);
            t->tree.print();
            return;
        }

        int mid = (l+r)/2;
        print(t->lef, l, mid);
        print(t->rig, mid+1, r);
    }*/
};

seg_tree data;

void init(int R, int C) {
    data = seg_tree(R);

    /*treap test;

    int q = 10;
    printf("you are allowed to ask up to %d questions\n", q);
    while (q--){
        int tp;
        scanf("%d", &tp);

        // tp == 1 - add
        // tp == 0 - ask

        if (tp == 1){
            int p;
            ll v;
            scanf("%d %lld", &p, &v);
            test.add(p, v);

            test.print();
        }
        else{
            int l, r;
            scanf("%d %d", &l, &r);
            printf("res: %lld\n", test.ask(l, r));
        }
    }*/
}

void update(int P, int Q, long long K) {
    data.add(P, Q, K);
}

long long calculate(int ar, int ac, int br, int bc) {
    return data.ask(ar, br, ac, bc);
}

Compilation message

grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
   18 |  int res;
      |      ^~~
game.cpp: In member function 'll seg_tree::query(seg_tree::pnode, int, int, int, int, int, int)':
game.cpp:232:13: warning: variable 'deb' set but not used [-Wunused-but-set-variable]
  232 |         int deb = 0;
      |             ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 0 ms 256 KB Output is correct
8 Correct 1 ms 256 KB Output is correct
9 Correct 1 ms 512 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 256 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 1100 ms 11464 KB Output is correct
5 Correct 483 ms 11588 KB Output is correct
6 Correct 1384 ms 8932 KB Output is correct
7 Correct 1643 ms 8516 KB Output is correct
8 Correct 1093 ms 7548 KB Output is correct
9 Correct 1579 ms 8700 KB Output is correct
10 Correct 1532 ms 8244 KB Output is correct
11 Correct 0 ms 368 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 2 ms 372 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1728 ms 15532 KB Output is correct
13 Correct 4650 ms 12096 KB Output is correct
14 Correct 877 ms 13080 KB Output is correct
15 Correct 5076 ms 13244 KB Output is correct
16 Correct 593 ms 12920 KB Output is correct
17 Correct 2593 ms 10144 KB Output is correct
18 Correct 4966 ms 14368 KB Output is correct
19 Correct 4013 ms 14524 KB Output is correct
20 Correct 3796 ms 13952 KB Output is correct
21 Correct 1 ms 416 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 1 ms 256 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1004 ms 11568 KB Output is correct
13 Correct 447 ms 11384 KB Output is correct
14 Correct 1383 ms 9204 KB Output is correct
15 Correct 1638 ms 8552 KB Output is correct
16 Correct 1058 ms 7628 KB Output is correct
17 Correct 1552 ms 8824 KB Output is correct
18 Correct 1378 ms 8312 KB Output is correct
19 Correct 1643 ms 15376 KB Output is correct
20 Correct 4513 ms 11876 KB Output is correct
21 Correct 759 ms 13184 KB Output is correct
22 Correct 4697 ms 13396 KB Output is correct
23 Correct 547 ms 13104 KB Output is correct
24 Correct 2426 ms 10332 KB Output is correct
25 Correct 4455 ms 14376 KB Output is correct
26 Correct 3600 ms 14468 KB Output is correct
27 Correct 3574 ms 13888 KB Output is correct
28 Correct 1638 ms 36472 KB Output is correct
29 Correct 2641 ms 39028 KB Output is correct
30 Correct 6763 ms 30232 KB Output is correct
31 Correct 6457 ms 29748 KB Output is correct
32 Correct 1259 ms 29396 KB Output is correct
33 Correct 1626 ms 29464 KB Output is correct
34 Correct 619 ms 32888 KB Output is correct
35 Correct 3045 ms 24044 KB Output is correct
36 Correct 5903 ms 36856 KB Output is correct
37 Correct 4149 ms 37488 KB Output is correct
38 Correct 4614 ms 36672 KB Output is correct
39 Correct 3552 ms 31000 KB Output is correct
40 Correct 1 ms 256 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1028 ms 11460 KB Output is correct
13 Correct 487 ms 11512 KB Output is correct
14 Correct 1409 ms 8828 KB Output is correct
15 Correct 1649 ms 8624 KB Output is correct
16 Correct 1082 ms 7628 KB Output is correct
17 Correct 1626 ms 8744 KB Output is correct
18 Correct 1671 ms 8256 KB Output is correct
19 Correct 1857 ms 15412 KB Output is correct
20 Correct 4399 ms 11880 KB Output is correct
21 Correct 914 ms 12988 KB Output is correct
22 Correct 4761 ms 13116 KB Output is correct
23 Correct 553 ms 12920 KB Output is correct
24 Correct 2330 ms 10376 KB Output is correct
25 Correct 4555 ms 14408 KB Output is correct
26 Correct 3863 ms 14624 KB Output is correct
27 Correct 3798 ms 13872 KB Output is correct
28 Correct 1742 ms 36472 KB Output is correct
29 Correct 2663 ms 39220 KB Output is correct
30 Correct 6365 ms 30376 KB Output is correct
31 Correct 5626 ms 30004 KB Output is correct
32 Correct 1184 ms 29432 KB Output is correct
33 Correct 1596 ms 29488 KB Output is correct
34 Correct 594 ms 32764 KB Output is correct
35 Correct 2854 ms 24236 KB Output is correct
36 Correct 5362 ms 36912 KB Output is correct
37 Correct 4316 ms 37224 KB Output is correct
38 Correct 4280 ms 36716 KB Output is correct
39 Correct 2156 ms 65848 KB Output is correct
40 Correct 4447 ms 67616 KB Output is correct
41 Correct 9799 ms 57424 KB Output is correct
42 Correct 8527 ms 55664 KB Output is correct
43 Correct 986 ms 62284 KB Output is correct
44 Correct 1976 ms 53008 KB Output is correct
45 Correct 3675 ms 30932 KB Output is correct
46 Correct 6537 ms 66468 KB Output is correct
47 Correct 6623 ms 66424 KB Output is correct
48 Correct 6915 ms 66020 KB Output is correct
49 Correct 1 ms 256 KB Output is correct