oj.uz

Submission #200885

# Submission time Handle Problem Language Result Execution time Memory
200885 2020-02-08T11:35:07 Z johutha Game (IOI13_game) C++17
37 / 100
 13000 ms 9720 KB 
#include <iostream>
#include <vector>
#include <memory>
#include <random>
#include "game.h"

#define int long long
#define seed 4142

using namespace std;

mt19937 rng(seed);
uniform_int_distribution<int> uni(0, 1e12);

int gcd(int a, int b)
{
    if (a > b) swap(a, b);
    if (a == 0) return b;
    return gcd(b % a, a);
}

struct node;

using node_ptr = unique_ptr<node>;

struct node
{
    node_ptr l, r;
    int pos, lp, rp;
    int val;
    int cv;
    int x;

    void recompute()
    {
        cv = val;
        lp = pos;
        rp = pos;
        if (l)
        {
            lp = l->lp;
            cv = gcd(cv, l->cv);
        }
        if (r)
        {
            rp = r->rp;
            cv = gcd(cv, r->cv);
        }
    }

    node(int ipos, int ival) : pos(ipos), val(ival), x(uni(rng)) { recompute(); }

    static node_ptr merge(node_ptr l, node_ptr r)
    {
        if (!l) return r;
        if (!r) return l;

        if (l->x > r->x)
        {
            l->r = merge(move(l->r), move(r));
            l->recompute();
            return l;
        }
        else
        {
            r->l = merge(move(l), move(r->l));
            r->recompute();
            return r;
        }
    }

    static pair<node_ptr,node_ptr> split(node_ptr rt, int pos)
    {
        if (!rt) return {};

        if (pos <= rt->pos)
        {
            node_ptr l;
            tie(l, rt->l) = split(move(rt->l), pos);
            if (l) l->recompute();
            if (rt) rt->recompute();
            return {move(l), move(rt)};
        }
        else
        {
            node_ptr r;
            tie(rt->r, r) = split(move(rt->r), pos);
            if (r) r->recompute();
            if (rt) rt->recompute();
            return {move(rt), move(r)};
        }
    }

    void print(int ind)
    {
        if (l) l->print(ind + 1);
        for (int i = 0; i < ind; i++) cout << "  ";
        cout << pos << " " << val << " " << cv << "  " << lp << " " << rp << "\n";
        if (r) r->print(ind + 1);
    }

    static node_ptr insert(node_ptr rt, int pos, int v)
    {
        node_ptr nw = make_unique<node>(pos, v);
        auto p = split(move(rt), pos);
        p.first = merge(move(p.first), move(nw));
        p.second = merge(move(p.first), move(p.second));
        return move(p.second);
    }

    bool contains(int key)
    {
        if (pos == key) return true;
        if (pos < key && r) return r->contains(key);
        if (key < pos && l) return l->contains(key);
        return false;
    }

    void update(int k, int nv)
    {
        if (k == pos) val = nv;
        if (k < pos) l->update(k, nv);
        if (k > pos) r->update(k, nv);
        recompute();
    }

    int query(int ql, int qr)
    {
        if (rp < ql || qr < lp) return 0;
        if (ql <= lp && rp <= qr) { return cv; }
        int res = 0;
        if (ql <= pos && pos <= qr) res = gcd(val, res);
        if (l) res = gcd(res, l->query(ql, qr));
        if (r) res = gcd(res, r->query(ql, qr));
        return res;
    }
};

int r;
vector<node_ptr> alln;

void init(signed R, signed C)
{
    r = R;
    alln.resize(R);
}

void update(signed P, signed Q, int K)
{
    if (alln[P] && alln[P]->contains(Q))
    {
        alln[P]->update(Q, K);
    }
    else
    {
        alln[P] = node::insert(move(alln[P]), Q, K);
    }
/*
    cout << "\nUpdate:\n";
    for (int i = 0; i < r; i++)
    {
        if (alln[i])
        {
            cout << i << ":\n";
            alln[i]->print(i);
        }
    } 
*/
}

int calculate(signed P, signed Q, signed U, signed V)
{
    if (P > U) swap(P, U);
    if (Q > V) swap(Q, V);

    int res = 0;
    // cout << "\nQuery:\n";
    for (int i = P; i <= U; i++)
    {
        if (!alln[i]) continue;
        int mr = alln[i]->query(Q, V);
        // cout << i << " " << mr << "\n";
        res = gcd(res, mr);
    }
    return res;
}

Compilation message

grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  int res;
      ^~~

Subtask #1
10.0 / 10.0

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 256 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 858 ms 9548 KB Output is correct
5 Correct 297 ms 9464 KB Output is correct
6 Correct 736 ms 6776 KB Output is correct
7 Correct 864 ms 6648 KB Output is correct
8 Correct 529 ms 6520 KB Output is correct
9 Correct 817 ms 6776 KB Output is correct
10 Correct 812 ms 6456 KB Output is correct
11 Correct 5 ms 256 KB Output is correct

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 256 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 380 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 5 ms 376 KB Output is correct
12 Correct 4190 ms 9576 KB Output is correct
13 Correct 12544 ms 5896 KB Output is correct
14 Correct 522 ms 5872 KB Output is correct
15 Execution timed out 13082 ms 6596 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 256 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 256 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 5 ms 376 KB Output is correct
12 Correct 867 ms 9656 KB Output is correct
13 Correct 295 ms 9336 KB Output is correct
14 Correct 745 ms 6884 KB Output is correct
15 Correct 880 ms 6776 KB Output is correct
16 Correct 511 ms 6776 KB Output is correct
17 Correct 868 ms 6648 KB Output is correct
18 Correct 812 ms 6392 KB Output is correct
19 Correct 4327 ms 9620 KB Output is correct
20 Correct 12660 ms 6096 KB Output is correct
21 Correct 536 ms 5624 KB Output is correct
22 Execution timed out 13019 ms 6616 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 256 KB Output is correct
5 Correct 5 ms 256 KB Output is correct
6 Correct 5 ms 380 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 256 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 5 ms 376 KB Output is correct
12 Correct 864 ms 9720 KB Output is correct
13 Correct 278 ms 9464 KB Output is correct
14 Correct 736 ms 6892 KB Output is correct
15 Correct 855 ms 6776 KB Output is correct
16 Correct 517 ms 6648 KB Output is correct
17 Correct 823 ms 6648 KB Output is correct
18 Correct 797 ms 6264 KB Output is correct
19 Correct 4169 ms 9484 KB Output is correct
20 Correct 12688 ms 5928 KB Output is correct
21 Correct 515 ms 5760 KB Output is correct
22 Execution timed out 13091 ms 6524 KB Time limit exceeded
23 Halted 0 ms 0 KB -