oj.uz

Submission #200147

# Submission time Handle Problem Language Result Execution time Memory
200147 2020-02-05T13:50:23 Z johutha Game (IOI13_game) C++17
0 / 100
 7 ms 376 KB 
#include "game.h"
#include <vector>
#include <iostream>
#include <cassert>
#include <memory>
#include <random>

#define int long long
#define seed 4134

using namespace std;

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

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

struct node;

using node_ptr = shared_ptr<node>;

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

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

    node(int k, int iv) : pos(k), v(iv)
    {
        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, const int pos)
	{
		if (!rt) return {};
		if (pos >= rt->rp) return {move(rt), node_ptr()};
		if (pos <= rt->pos)
		{
			node_ptr l;
			tie(l, rt->l) = split(move(rt->l), pos);
			if (rt) rt->recompute();
			if (l) l->recompute();
			return {move(l), move(rt)};
		}
		else
		{
			node_ptr r;
			tie(rt->r, r) = split(move(rt->r), pos);
			if (rt) rt->recompute();
			if (r) r->recompute();
			return {move(rt), move(r)};
		}
	}

    bool update(int k, int iv)
    {
        if (k == pos)
        {
            v = iv;
            recompute();
            return true;
        }
        if (l && k < pos) return l->update(k, iv);
        if (r && k > pos) return r->update(k, iv);
        recompute();
        return false;
    }

    static node_ptr insert(node_ptr rt, int k, int v)
    {
        node_ptr l, r, np;
        tie(l, r) = split(move(rt), k);
        np = make_shared<node>(k, v);
        l = merge(move(l), move(np));
        r = merge(move(l), move(r));
        return move(r);
    }

    int query(int ql, int qr)
    {
        // cerr << pos << " " << ql << " " << qr << " " << lp << " " << rp << "\n";
        if (ql <= lp && rp <= qr) return cv;
        if (rp < ql || qr < lp) return 0;
        int g = 0;
        if (ql <= pos && pos <= qr) g = v;
        if (l) g = gcd(g, l->query(ql, qr));
        if (r) g = gcd(g, r->query(ql, qr));
        return g;
    }

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

vector<node_ptr> sts;
int r, c;

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

void update(signed P, signed Q, int K)
{
    // cout << P << " " << Q << " " << K << " on:\n";
    // if (!sts[P]) cout << "NO\n";
    // else sts[P]->print(0);
    if (sts[P])
    {
        if (sts[P]->update(Q, K))
        {
            // cout << "DONE\n";
            // sts[P]->print(0);
            return;
        }
    }
    sts[P] = node::insert(sts[P], Q, K);
    // cout << "DONE\n";
    // sts[P]->print(0);
}
 
int calculate(signed P, signed Q, signed U, signed V) 
{
    // cout << "\n";
    if (U < P) swap(U, P);
    if (V < Q) swap(Q, V);
    
    int ret = 0;

    for (int i = P; i <= U; i++)
    {
        if (!sts[i]) continue;
        ret = gcd(ret, sts[i]->query(Q, V));
    }
    return ret;
}

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
0 / 10.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 Incorrect 5 ms 376 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 256 KB Output is correct
2 Incorrect 5 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 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 Incorrect 5 ms 256 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 17.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 Incorrect 6 ms 256 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 20.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 Incorrect 5 ms 256 KB Output isn't correct
5 Halted 0 ms 0 KB -