Submission #265195

#	Time	Username	Problem	Language	Result	Execution time	Memory
265195		evpipis	Game (IOI13_game)	C++11	100 / 100	9799 ms	67616 KiB

game

#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 (stderr)

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 / 10
• Subtask 2: 27 / 27
• Subtask 3: 26 / 26
• Subtask 4: 17 / 17
• Subtask 5: 20 / 20