oj.uz

Submission #134386

# Submission time Handle Problem Language Result Execution time Memory
134386 2019-07-22T14:09:03 Z ksmzzang2003 Game (IOI13_game) C++17
100 / 100
 8808 ms 166832 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 =v ;
            }
            else lc ->update(s,mid,t,v);
        }
        else 
        {
            if(rc==nullptr)
            {
                rc =new node1d;
                rc->pos = t,rc->val =v;
            }
            else rc->update(mid+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 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(mid+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 252 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 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 2 ms 376 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 834 ms 10100 KB Output is correct
5 Correct 590 ms 10616 KB Output is correct
6 Correct 708 ms 7204 KB Output is correct
7 Correct 852 ms 7032 KB Output is correct
8 Correct 573 ms 5200 KB Output is correct
9 Correct 847 ms 7060 KB Output is correct
10 Correct 677 ms 6648 KB Output is correct
11 Correct 2 ms 376 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 368 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 2 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 376 KB Output is correct
12 Correct 1451 ms 13816 KB Output is correct
13 Correct 2757 ms 7672 KB Output is correct
14 Correct 427 ms 1840 KB Output is correct
15 Correct 3314 ms 9992 KB Output is correct
16 Correct 292 ms 12476 KB Output is correct
17 Correct 1208 ms 8132 KB Output is correct
18 Correct 2112 ms 12872 KB Output is correct
19 Correct 1876 ms 12992 KB Output is correct
20 Correct 1665 ms 12448 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 17 ms 256 KB Output is correct
8 Correct 2 ms 376 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 376 KB Output is correct
12 Correct 831 ms 10144 KB Output is correct
13 Correct 619 ms 10508 KB Output is correct
14 Correct 792 ms 7260 KB Output is correct
15 Correct 880 ms 7160 KB Output is correct
16 Correct 527 ms 5172 KB Output is correct
17 Correct 916 ms 6924 KB Output is correct
18 Correct 704 ms 6644 KB Output is correct
19 Correct 1462 ms 13648 KB Output is correct
20 Correct 2756 ms 7608 KB Output is correct
21 Correct 414 ms 1916 KB Output is correct
22 Correct 3220 ms 9936 KB Output is correct
23 Correct 280 ms 12588 KB Output is correct
24 Correct 1182 ms 8008 KB Output is correct
25 Correct 2285 ms 13004 KB Output is correct
26 Correct 1849 ms 12884 KB Output is correct
27 Correct 1651 ms 12368 KB Output is correct
28 Correct 807 ms 46160 KB Output is correct
29 Correct 2207 ms 41920 KB Output is correct
30 Correct 6877 ms 41968 KB Output is correct
31 Correct 6494 ms 81284 KB Output is correct
32 Correct 926 ms 2296 KB Output is correct
33 Correct 1255 ms 6084 KB Output is correct
34 Correct 479 ms 38860 KB Output is correct
35 Correct 1708 ms 20664 KB Output is correct
36 Correct 3168 ms 39152 KB Output is correct
37 Correct 2489 ms 39404 KB Output is correct
38 Correct 2471 ms 38724 KB Output is correct
39 Correct 2106 ms 30692 KB Output is correct
40 Correct 2 ms 376 KB Output is correct

Subtask #5
20.0 / 20.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 504 KB Output is correct
4 Correct 2 ms 380 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 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 838 ms 10208 KB Output is correct
13 Correct 612 ms 10436 KB Output is correct
14 Correct 716 ms 7276 KB Output is correct
15 Correct 844 ms 6952 KB Output is correct
16 Correct 501 ms 5116 KB Output is correct
17 Correct 768 ms 7032 KB Output is correct
18 Correct 678 ms 6500 KB Output is correct
19 Correct 1453 ms 13816 KB Output is correct
20 Correct 2769 ms 7700 KB Output is correct
21 Correct 406 ms 1856 KB Output is correct
22 Correct 3225 ms 9948 KB Output is correct
23 Correct 286 ms 12460 KB Output is correct
24 Correct 1203 ms 8168 KB Output is correct
25 Correct 2138 ms 13008 KB Output is correct
26 Correct 1825 ms 13132 KB Output is correct
27 Correct 1650 ms 12488 KB Output is correct
28 Correct 824 ms 46172 KB Output is correct
29 Correct 2136 ms 41820 KB Output is correct
30 Correct 6830 ms 41980 KB Output is correct
31 Correct 6460 ms 81264 KB Output is correct
32 Correct 904 ms 2240 KB Output is correct
33 Correct 1200 ms 5984 KB Output is correct
34 Correct 409 ms 38912 KB Output is correct
35 Correct 1492 ms 20612 KB Output is correct
36 Correct 2949 ms 39152 KB Output is correct
37 Correct 2370 ms 39384 KB Output is correct
38 Correct 2337 ms 38756 KB Output is correct
39 Correct 1136 ms 100952 KB Output is correct
40 Correct 3507 ms 84932 KB Output is correct
41 Correct 8808 ms 88896 KB Output is correct
42 Correct 8645 ms 166832 KB Output is correct
43 Correct 797 ms 82936 KB Output is correct
44 Correct 1384 ms 2280 KB Output is correct
45 Correct 1960 ms 30448 KB Output is correct
46 Correct 3932 ms 83112 KB Output is correct
47 Correct 3995 ms 83400 KB Output is correct
48 Correct 4016 ms 82928 KB Output is correct
49 Correct 2 ms 256 KB Output is correct