Submission #264980

#	Time	Username	Problem	Language	Result	Execution time	Memory
264980		evpipis	Game (IOI13_game)	C++11	37 / 100	13082 ms	9164 KiB

game

#include "game.h"

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

typedef long long ll;

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

        node(int p = 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, int 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(int 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, p-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, b);
        split(l, l, mid, a-1);

        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");
    }
};

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;

        //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(j, 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;

        //printf("seg_tree::making (%d, %d) = %lld\n", r, c, v);
        root = update(root, 0, mx-1, 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){
        if (r < i || j < l)
            return 0;
        if (i <= l && r <= j){
            //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){
        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);
        return query(root, 0, mx-1, ar, br, ac, bc);
    }
};

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;
      |      ^~~

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