oj.uz

Submission #264813

# Submission time Handle Problem Language Result Execution time Memory
264813 2020-08-14T10:03:50 Z evpipis Game (IOI13_game) C++11
0 / 100
 2 ms 384 KB 
#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;
        }
    };

    typedef node *pnode;
    pnode root;

    treap(){
        root = NULL;
    }

    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){
        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){
        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(){
        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;

    seg_tree(int m = 0){
        null = new node();
        null->lef = null->rig = null;
        root = null;
        mx = 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){
        //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){
        //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

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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Incorrect 1 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Incorrect 1 ms 256 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Incorrect 2 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Incorrect 1 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Incorrect 2 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -