oj.uz

Submission #135507

# Submission time Handle Problem Language Result Execution time Memory
135507 2019-07-24T07:15:43 Z ksmzzang2003 Game (IOI13_game) C++17
100 / 100
 8716 ms 173244 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 m = (s+e)/2;
        if(pos>=0)
        {
            if(pos<=m)
            {
                lc = new node1d;
                lc->pos=pos,lc->val=val;
            }
            else
            {
                rc = new node1d;
                rc->pos=pos,rc->val=val;
            }
            pos=-1;
        }
        if(t<=m)
        {
            if(lc==nullptr)
            {
                lc = new node1d;
                lc->pos = t,lc->val =  v;
            }
            else
                lc-> update(s,m,t,v);
        }
        else
        {
            if(rc==nullptr)
            {
                rc= new node1d;
                rc->pos = t,rc->val = v;
            }
            else
                rc->update(m+1,e,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 m =(s+e)/2;
        ll ret=0;
        if(lc!=nullptr)
            ret = __gcd(ret,lc->query(s,m,ts,te));
        if(rc!=nullptr)
            ret = __gcd(ret,rc->query(m+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 m = (s+e)/2;
        if(tx<=m)
        {
            if(lc==nullptr)
                lc = new node2d;
            lc->update(s,m,tx,ty,v);
        }
        else
        {
            if(rc==nullptr)
                rc = new node2d;
            rc->update(m+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 m = (s+e)/2;
        ll ret=0;
        if(lc!=nullptr)
            ret = __gcd(ret,lc->query(s,m,txs,txe,tys,tye));
        if(rc!=nullptr)
            ret = __gcd(ret,rc->query(m+1,e,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
10.0 / 10.0

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 252 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 833 ms 13732 KB Output is correct
5 Correct 602 ms 13596 KB Output is correct
6 Correct 723 ms 11180 KB Output is correct
7 Correct 808 ms 10744 KB Output is correct
8 Correct 503 ms 8572 KB Output is correct
9 Correct 791 ms 10960 KB Output is correct
10 Correct 702 ms 10476 KB Output is correct
11 Correct 2 ms 256 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 3 ms 380 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 2 ms 380 KB Output is correct
8 Correct 2 ms 252 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 1492 ms 17112 KB Output is correct
13 Correct 2748 ms 10736 KB Output is correct
14 Correct 411 ms 5780 KB Output is correct
15 Correct 3225 ms 13540 KB Output is correct
16 Correct 286 ms 15864 KB Output is correct
17 Correct 1243 ms 12004 KB Output is correct
18 Correct 2234 ms 17408 KB Output is correct
19 Correct 1868 ms 17508 KB Output is correct
20 Correct 1693 ms 17080 KB Output is correct
21 Correct 2 ms 376 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 380 KB Output is correct
12 Correct 863 ms 13804 KB Output is correct
13 Correct 638 ms 13432 KB Output is correct
14 Correct 724 ms 11128 KB Output is correct
15 Correct 827 ms 10816 KB Output is correct
16 Correct 507 ms 8620 KB Output is correct
17 Correct 858 ms 10844 KB Output is correct
18 Correct 714 ms 10660 KB Output is correct
19 Correct 1487 ms 17032 KB Output is correct
20 Correct 2750 ms 10812 KB Output is correct
21 Correct 406 ms 5792 KB Output is correct
22 Correct 3202 ms 13520 KB Output is correct
23 Correct 287 ms 16000 KB Output is correct
24 Correct 1186 ms 12284 KB Output is correct
25 Correct 2419 ms 17512 KB Output is correct
26 Correct 1836 ms 17440 KB Output is correct
27 Correct 1688 ms 16908 KB Output is correct
28 Correct 823 ms 55928 KB Output is correct
29 Correct 2124 ms 51264 KB Output is correct
30 Correct 6857 ms 48240 KB Output is correct
31 Correct 6446 ms 87352 KB Output is correct
32 Correct 903 ms 10692 KB Output is correct
33 Correct 1230 ms 14440 KB Output is correct
34 Correct 400 ms 44792 KB Output is correct
35 Correct 1631 ms 29724 KB Output is correct
36 Correct 3020 ms 48948 KB Output is correct
37 Correct 2580 ms 49220 KB Output is correct
38 Correct 2378 ms 48716 KB Output is correct
39 Correct 2283 ms 40304 KB Output is correct
40 Correct 2 ms 256 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 831 ms 13860 KB Output is correct
13 Correct 591 ms 13560 KB Output is correct
14 Correct 780 ms 11156 KB Output is correct
15 Correct 797 ms 10760 KB Output is correct
16 Correct 507 ms 8684 KB Output is correct
17 Correct 760 ms 10872 KB Output is correct
18 Correct 693 ms 10404 KB Output is correct
19 Correct 1447 ms 16988 KB Output is correct
20 Correct 2776 ms 10816 KB Output is correct
21 Correct 403 ms 5752 KB Output is correct
22 Correct 3214 ms 13620 KB Output is correct
23 Correct 288 ms 15864 KB Output is correct
24 Correct 1197 ms 12108 KB Output is correct
25 Correct 2122 ms 17440 KB Output is correct
26 Correct 1902 ms 17784 KB Output is correct
27 Correct 1946 ms 16876 KB Output is correct
28 Correct 831 ms 55808 KB Output is correct
29 Correct 2163 ms 51084 KB Output is correct
30 Correct 6811 ms 48044 KB Output is correct
31 Correct 6402 ms 87416 KB Output is correct
32 Correct 920 ms 10820 KB Output is correct
33 Correct 1211 ms 14740 KB Output is correct
34 Correct 414 ms 44796 KB Output is correct
35 Correct 1570 ms 29688 KB Output is correct
36 Correct 3049 ms 49000 KB Output is correct
37 Correct 2415 ms 49220 KB Output is correct
38 Correct 2435 ms 48732 KB Output is correct
39 Correct 1119 ms 110940 KB Output is correct
40 Correct 3311 ms 94796 KB Output is correct
41 Correct 8716 ms 95340 KB Output is correct
42 Correct 8641 ms 173244 KB Output is correct
43 Correct 899 ms 89432 KB Output is correct
44 Correct 1379 ms 11104 KB Output is correct
45 Correct 2200 ms 40120 KB Output is correct
46 Correct 3885 ms 93496 KB Output is correct
47 Correct 3875 ms 93640 KB Output is correct
48 Correct 3980 ms 93112 KB Output is correct
49 Correct 2 ms 256 KB Output is correct