oj.uz

Submission #134357

# Submission time Handle Problem Language Result Execution time Memory
134357 2019-07-22T13:41:54 Z ksmzzang2003 Game (IOI13_game) C++17
0 / 100
 2 ms 380 KB 
#include "game.h"
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
int R,C,Q;
struct node1d
{
    ll val = 0; int pos = -1;
    node1d *lc = nullptr, *rc = nullptr;
    void update(int s,int e,int t,ll v)
    {
        if(e<t || t<s) return ;
        if(s==e)
        {
            val = v;
            return ;
        }
        int mid = (s+e)/2;
        if(pos>=0)
        {
            if(pos<=mid)
            {
                lc = new node1d;
                lc->pos = pos , lc->val = val;
            }
            else
            {
                rc = new node1d;
                rc-> pos = pos, rc->val = val;
            }
            pos = -1;
        }
        if(t<=mid)
        {
            if(lc==nullptr)
            {
                lc = new node1d;
                lc->pos = t ; lc->val = val;
            }
            else lc->update(s,mid,t,v);
        }
        else
        {
            if(rc==nullptr)
            {
                rc = new node1d;
                rc->pos = t ; rc->val = val;
            }
            else rc->update(s,mid,t,v);
        }
        val = 0;
        if(lc!=nullptr) val = __gcd(val,lc->val);
        if(rc!=nullptr) val = __gcd(val,rc->val);
    }

    ll query(int s,int e,int ts,int te)
    {
        if(te<s || e<ts) return 0 ;
        if(ts<=s &&e <= te) return val;
        if(pos>=0)
        {
            if(ts<=pos && pos <=te) return val;
            return 0;
        }
        int mid = (s+e)/2;
        ll ret= 0 ;
        if(lc!=nullptr) ret= __gcd(ret,lc->query(s,mid,ts,te));
        if(rc!=nullptr) ret= __gcd(ret,rc->query(mid+1,e,ts,te));
        return ret;
    }
};

struct node2d
{
    node1d *T = new node1d;
    node2d *lc = nullptr,*rc = nullptr;
    void update(int s,int e,int tx,int ty,ll v)
    {
        if(e<tx || tx<s) return ;
        if(s==e)
        {
            T->update(0,C-1,ty,v);
            return ;
        }
        int mid = (s+e)/2;
        if(tx<=mid)
        {
            if(lc==nullptr) lc = new node2d;
            lc->update(s,mid,tx,ty,v);
        }
        else
        {
            if(rc == nullptr) rc = new node2d;
            rc->update(mid+1,e,tx,ty,v);
        }
        ll ret=0;
        if(lc!=nullptr) ret= __gcd(ret,lc->T->query(0,C-1,ty,ty));
        if(rc!=nullptr) ret= __gcd(ret,rc->T->query(0,C-1,ty,ty));
        T->update(0,C-1,ty,ret);
    }

    ll query(int s,int e,int txs,int txe,int tys,int tye)
    {
        if(txe<s || e<txs) return 0;
        if(txs<=s && e<=txe) return T->query(0,C-1,tys,tye);
        int mid = (s+e)/2;
        ll ret= 0;
        if(lc!=nullptr) ret = __gcd(ret,lc->query(s,mid,txs,txe,tys,tye));
        if(rc!=nullptr) ret = __gcd(ret,rc->query(s,mid,txs,txe,tys,tye));
        return ret;
    }
}* Seg = new node2d;

void init(int r,int c)
{
    R=r,C=c;
}
void update(int x,int y,ll v)
{
    Seg->update(0,R-1,x,y,v);
}

ll calculate(int x1,int y1,int x2,int y2)
{
    return Seg->query(0,R-1,x1,x2,y1,y2);
}

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 376 KB Output is correct
2 Incorrect 2 ms 372 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 380 KB Output is correct
2 Incorrect 2 ms 376 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 376 KB Output is correct
2 Incorrect 2 ms 376 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 256 KB Output is correct
2 Incorrect 2 ms 376 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 376 KB Output is correct
2 Incorrect 2 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -