oj.uz

Submission #987441

# Submission time Handle Problem Language Result Execution time Memory
987441 2024-05-22T18:51:06 Z canadavid1 Game (IOI13_game) C++17
0 / 100
 1 ms 600 KB 
#include "game.h"
template<typename T,typename... Args>
T* New(Args ...args)
{
    static int i=0;
    static T* b = 0;
    if(i<=0)
    {
        b = new T[1<<16];
        i = 1<<16;
    }
    return new(&b[--i]) T(args...);
}

template<typename T>
using ptr = T*;

#include <vector>
#include <utility>


constexpr int MAX = 1e9+10;
using i64 = long long;
i64 gcd2(i64 X,i64 Y) {
    long long tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}
struct Node
{
    using T = i64;
    T val=0;
    ptr<Node> l,r;
};
i64 query(ptr<Node> n,int l, int r, int rl=0, int rr=MAX)
{
    if(!n) return 0;
    l = std::max(l,rl);
    r = std::min(r,rr);
    if(l==rl && r == rr) return n->val;
    if(l >= r) return 0;
    auto m = (rl+rr)/2;
    return gcd2(query(n->l,l,r,rl,m),query(n->r,l,r,m,rr));
}
ptr<Node> update(ptr<Node> n,i64 val, int p, int rl=0, int rr=MAX)
{
    if(!n) n = New<Node>();
    if(rr-rl == 1)
    {
        n->val = val;
        return n;
    }
    auto m = (rl+rr)/2;
    if(p >= m) n->r = update(n->r,val,p,m,rr);
    else n->l = update(n->l,val,p,rl,m);
    n->val = 0;
    if(n->l) n->val = n->l->val;
    if(n->r) n->val = gcd2(n->val,n->r->val);
    return n;
}

struct Node2d
{
    ptr<Node> val;
    ptr<Node2d> l,r;
};
i64 query(ptr<Node2d> n, int l, int r, int t, int b, int rl=0, int rr=MAX)
{
    if(!n) return 0;
    l = std::max(l,rl);
    r = std::min(r,rr);
    if(l==rl && r == rr) return query(n->val,t,b);
    if(l >= r) return 0;
    auto m = (rl+rr)/2;
    return gcd2(query(n->l,l,r,t,b,rl,m),query(n->r,l,r,t,b,m,rr));
}
ptr<Node2d> update(ptr<Node2d> n, int val, int p, int y, int rl=0, int rr = MAX)
{
    if(!n) n = New<Node2d>();
    if(rr-rl == 1)
    {
        n->val = update(n->val,val,y);
        return n;
    }
    auto m = (rl+rr)/2;
    if(p >= m) n->r = update(n->r,val,p,y,m,rr);
    else n->l = update(n->l,val,p,y,rl,m);
    i64 v = 0;
    if(n->l) v = query(n->l->val,p,p+1);
    if(n->r) v = gcd2(v,query(n->r->val,p,p+1));
    n->val = update(n->val,v,y);
    return n;
}

struct Naive
{
    i64 grid[100][100];
};
i64 query(ptr<Naive> n,int l, int r, int t, int b)
{
    if(!n) return 0;
    i64 o = 0;
    for(int i = l; i < r; i++)
    for(int j = t; j < b; j++)
        o = gcd2(o,n->grid[i][j]);
    return o;
}
ptr<Naive> update(ptr<Naive> n,int val, int p, int y)
{
    if(!n) n = new Naive();
    n->grid[p][y] = val;
    return n;
}




ptr<Naive> tree;
void init(int R, int C) {
    /* ... */
}

void update(int P, int Q, long long K) {
    tree = update(tree,K,P,Q);
}

long long calculate(int P, int Q, int U, int V) {
    return query(tree,P,U+1,Q,V+1);
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 27.0

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

Subtask #3
0 / 26.0

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

Subtask #4
0 / 17.0

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

Subtask #5
0 / 20.0

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