oj.uz

Submission #52012

# Submission time Handle Problem Language Result Execution time Memory
52012 2018-06-23T08:45:16 Z Crown Game (IOI13_game) C++14
0 / 100
 4 ms 584 KB 
#include "game.h"
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define pb push_back
#define mp make_pair
typedef pair<int, int> ii;
typedef long long ll;

int maxn;

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_node
{
    ll val, gcd;
    int key, prio;
    treap_node *left, *right;
    treap_node(int _key, ll _val)
    {
        val = gcd = _val;
        key = _key;
        prio = (rand()<<16)^rand();
        left = right = NULL;
    }
    void calc()
    {
        gcd = val;
        if(left) gcd = gcd2(gcd, left->gcd);
        if(right) gcd = gcd2(gcd, right->gcd);
    }
};

treap_node* merge(treap_node *L, treap_node *R)
{
    if(!L || !R) return L?L:R;
    if(L->prio > R->prio)
    {
        L->right = merge(L->right, R);
        L->calc();
        return L;
    }
    else
    {
        R->left = merge(L, R->left);
        R->calc();
        return R;
    }
} 
void split(treap_node *big, treap_node* &L, treap_node* &R, int key)
{
    L = R = NULL;
    if(!big)
    {
        return;
    }
    if(big->key<= key)
    {
        L = big;
        split(big->right, big->right, R, key);
    }
    else 
    {
        R = big;
        split(big->left, L, big->left, key);
    }
    big->calc();
}
ll ask_treap(int i, int j, treap_node *u)
{
    treap_node *one, *two;
    split(u, one, u, i-1);
    split(u, u, two, j);
    ll ret = u?u->gcd:0;
    u = merge(one, u);
    u = merge(u, two);
    return ret;
}

void upd_treap(treap_node* &u, int x, ll val)
{
    treap_node *one, *two;
    split(u, one, u, x-1);
    split(u, u, two, x);
    if(!u)
    {
        u = new treap_node(x, val);
    }
    else
    {
        assert(!(u->left));
        assert(!(u->right));
        u->key = u->gcd = val;
    }
    u = merge(one, u);
    u = merge(u, two);
}

struct node
{
    treap_node *x;
    node *left, *right;
    node()
    {
        x = NULL;
        left = right = NULL;
    }
    node* getL()
    {
        if(left) return left;
        return left = new node();
    }
    node* getR()
    {
        if(right) return right;
        return right = new node();
    }
};

ll ask(node *u, int i1, int j1, int i2, int j2, int L = 0, int R = maxn-1)
{
    if(!u) return 0;
    if(i1> R || i2< L) return 0;
    if(i1<= L && R<= i2)
    {
        treap_node *one, *two;
        one = two = NULL;
        split(u->x, one, u->x, j1-1);
        split(u->x, u->x, two, j2);
        ll ret = u->x?u->x->gcd:0;
        u->x = merge(one, u->x);
        u->x = merge(u->x, two);
        return ret;
    }
    ll x = ask(u->left, i1, j1, i2, j2, L, (L+R)/2);
    ll y = ask(u->right, i1, j1, i2, j2, (L+R)/2+1, R);
    return gcd2(x, y);
}

void Update(node *u, int x, int y, ll val, int L = 0, int R = maxn-1)
{
    treap_node *one, *two;
    one = two = NULL;
    split(u->x, one, u->x, y-1);
    split(u->x, u->x, two, y);
    if(!(u->x))
    {
        u->x = new treap_node(y, val);
    }
    else
    {
        assert(!(u->x->left));
        assert(!(u->x->right));
        u->x->val = u->x->gcd = val;
    }
    u->x = merge(one, u->x);
    u->x = merge(u->x, two);
    if(L == R) return; 
    int M = (L+R)/2;
    if(x<= M) Update(u->getL(), x, y, val, L, M);
    else Update(u->getR(), x, y, val, M+1, R);
}

node *root;

void init(int R, int C)
{
    srand(time(NULL));
    maxn = R;
    root = new node();
}

void update(int P, int Q, long long K)
{
    Update(root, P, Q, K);
}

long long calculate(int P, int Q, int U, int V)
{
    return ask(root, P, Q, U, V);
}

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 2 ms 248 KB Output is correct
2 Incorrect 3 ms 356 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

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

Subtask #3
0 / 26.0

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

Subtask #4
0 / 17.0

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

Subtask #5
0 / 20.0

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