oj.uz

Submission #264980

# Submission time Handle Problem Language Result Execution time Memory
264980 2020-08-14T12:00:24 Z evpipis Game (IOI13_game) C++11
37 / 100
 13000 ms 9164 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;
        }
    };

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

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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 360 KB Output is correct
3 Correct 1 ms 256 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 256 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 1 ms 256 KB Output is correct
9 Correct 1 ms 256 KB Output is correct
10 Correct 1 ms 276 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 512 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 0 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 1270 ms 7348 KB Output is correct
5 Correct 431 ms 9060 KB Output is correct
6 Correct 1866 ms 6504 KB Output is correct
7 Correct 2102 ms 6416 KB Output is correct
8 Correct 1429 ms 6564 KB Output is correct
9 Correct 2088 ms 6384 KB Output is correct
10 Correct 1828 ms 5952 KB Output is correct
11 Correct 0 ms 256 KB Output is correct

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 256 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 256 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 1 ms 256 KB Output is correct
9 Correct 1 ms 256 KB Output is correct
10 Correct 1 ms 256 KB Output is correct
11 Correct 1 ms 256 KB Output is correct
12 Execution timed out 13004 ms 7064 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
0 / 17.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 1 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 1 ms 256 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 1 ms 256 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 256 KB Output is correct
11 Correct 1 ms 256 KB Output is correct
12 Correct 1284 ms 7500 KB Output is correct
13 Correct 429 ms 9080 KB Output is correct
14 Correct 1803 ms 6600 KB Output is correct
15 Correct 2159 ms 6296 KB Output is correct
16 Correct 1420 ms 6512 KB Output is correct
17 Correct 2012 ms 6400 KB Output is correct
18 Correct 1831 ms 6080 KB Output is correct
19 Execution timed out 13057 ms 8340 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 368 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 256 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 256 KB Output is correct
7 Correct 0 ms 256 KB Output is correct
8 Correct 0 ms 256 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 256 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1232 ms 7832 KB Output is correct
13 Correct 431 ms 9164 KB Output is correct
14 Correct 1789 ms 6668 KB Output is correct
15 Correct 2150 ms 6324 KB Output is correct
16 Correct 1426 ms 6528 KB Output is correct
17 Correct 1993 ms 6616 KB Output is correct
18 Correct 1795 ms 6164 KB Output is correct
19 Execution timed out 13082 ms 8376 KB Time limit exceeded
20 Halted 0 ms 0 KB -