oj.uz

Submission #127151

# Submission time Handle Problem Language Result Execution time Memory
127151 2019-07-09T01:02:22 Z arnold518 Game (IOI13_game) C++14
100 / 100
 8718 ms 173492 KB 
#include <bits/stdc++.h>
#include "game.h"
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
int r, c;
 
struct Node1
{
    Node1() : val(0), pos(-1), lc(NULL), rc(NULL) {}
    ll val, pos; Node1 *lc, *rc;
};
 
struct Node2
{
    Node2() : val(NULL), lc(NULL), rc(NULL) {}
    Node1 *val; Node2 *lc, *rc;
};
 
Node2 *root;
 
void init(int R, int C)
{
    r=R; c=C;
    root=new Node2();
}
 
void update1(Node1* node, int tl, int tr, int x, ll val)
{
    if(tl==tr) { node->val=val; return; }
    int mid=tl+tr>>1;
 
    if(node->pos!=-1)
    {
        if(node->pos<=mid)
        {
            node->lc=new Node1();
            node->lc->pos=node->pos;
            node->lc->val=node->val;
        }
        else
        {
            node->rc=new Node1();
            node->rc->val=node->val;
            node->rc->pos=node->pos;
        }
        node->pos=-1;
    }
 
    if(x<=mid)
    {
        if(node->lc==NULL)
        {
            node->lc=new Node1();
            node->lc->pos=x;
            node->lc->val=val;
        }
        else update1(node->lc, tl, mid, x, val);
    }
    else
    {
        if(node->rc==NULL)
        {
            node->rc=new Node1();
            node->rc->pos=x;
            node->rc->val=val;
        }
        else update1(node->rc, mid+1, tr, x, val);
    }
    node->val=0;
    if(node->lc!=NULL) node->val=__gcd(node->val, node->lc->val);
    if(node->rc!=NULL) node->val=__gcd(node->val, node->rc->val);
}
 
ll query1(Node1* node, int tl, int tr, int lx, int rx)
{
    if(tr<lx || rx<tl) return 0;
    if(lx<=tl && tr<=rx) return node->val;
    if(node->pos!=-1)
    {
        if(lx<=node->pos && node->pos<=rx) return node->val;
        else return 0;
    }
    int mid=tl+tr>>1;
    ll ret=0;
    if(node->lc!=NULL) ret=__gcd(ret, query1(node->lc, tl, mid, lx, rx));
    if(node->rc!=NULL) ret=__gcd(ret, query1(node->rc, mid+1, tr, lx, rx));
    return ret;
}
 
void update2(Node2* node, int tl, int tr, int y, int x, ll val)
{
    if(node->val==NULL) node->val=new Node1();
    if(tl==tr) { update1(node->val, 1, c, x, val); return; }
    int mid=tl+tr>>1;
    if(y<=mid)
    {
        if(node->lc==NULL) node->lc=new Node2();
        update2(node->lc, tl, mid, y, x, val);
    }
    else
    {
        if(node->rc==NULL) node->rc=new Node2();
        update2(node->rc, mid+1, tr, y, x, val);
    }
    ll t=0;
    if(node->lc!=NULL) t=__gcd(t, query1(node->lc->val, 1, c, x, x));
    if(node->rc!=NULL) t=__gcd(t, query1(node->rc->val, 1, c, x, x));
    update1(node->val, 1, c, x, t);
}
 
ll query2(Node2 *node, int tl, int tr, int ly, int ry, int lx, int rx)
{
    if(tr<ly || ry<tl) return 0;
    if(ly<=tl && tr<=ry)
    {
        if(node->val!=NULL) return query1(node->val, 1, c, lx, rx);
        else return 0;
    }
    int mid=tl+tr>>1;
    ll ret=0;
    if(node->lc!=NULL) ret=__gcd(ret, query2(node->lc, tl, mid, ly, ry, lx, rx));
    if(node->rc!=NULL) ret=__gcd(ret, query2(node->rc, mid+1, tr, ly, ry, lx, rx));
    return ret;
}
 
void update(int P, int Q, ll K)
{
    P++; Q++;
    update2(root, 1, r, P, Q, K);
}
 
ll calculate(int P, int Q, int U, int V)
{
    P++; Q++; U++; V++;
    return query2(root, 1, r, P, U, Q, 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;
      ^~~
game.cpp: In function 'void update1(Node1*, int, int, int, ll)':
game.cpp:34:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=tl+tr>>1;
             ~~^~~
game.cpp: In function 'll query1(Node1*, int, int, int, int)':
game.cpp:87:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=tl+tr>>1;
             ~~^~~
game.cpp: In function 'void update2(Node2*, int, int, int, int, ll)':
game.cpp:98:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=tl+tr>>1;
             ~~^~~
game.cpp: In function 'll query2(Node2*, int, int, int, int, int, int)':
game.cpp:123:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=tl+tr>>1;
             ~~^~~

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 380 KB Output is correct
4 Correct 2 ms 376 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 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 256 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 811 ms 13728 KB Output is correct
5 Correct 573 ms 13560 KB Output is correct
6 Correct 699 ms 11128 KB Output is correct
7 Correct 765 ms 10872 KB Output is correct
8 Correct 488 ms 8568 KB Output is correct
9 Correct 754 ms 10872 KB Output is correct
10 Correct 715 ms 10488 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 504 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 380 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 504 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 1433 ms 17088 KB Output is correct
13 Correct 2795 ms 10740 KB Output is correct
14 Correct 404 ms 5880 KB Output is correct
15 Correct 3198 ms 13560 KB Output is correct
16 Correct 286 ms 15992 KB Output is correct
17 Correct 1174 ms 12280 KB Output is correct
18 Correct 2033 ms 17620 KB Output is correct
19 Correct 1721 ms 17492 KB Output is correct
20 Correct 1582 ms 16888 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 256 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 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 809 ms 13680 KB Output is correct
13 Correct 569 ms 13604 KB Output is correct
14 Correct 690 ms 11176 KB Output is correct
15 Correct 803 ms 10872 KB Output is correct
16 Correct 496 ms 8684 KB Output is correct
17 Correct 736 ms 10876 KB Output is correct
18 Correct 667 ms 10488 KB Output is correct
19 Correct 1437 ms 17164 KB Output is correct
20 Correct 2781 ms 10744 KB Output is correct
21 Correct 409 ms 5752 KB Output is correct
22 Correct 3248 ms 13688 KB Output is correct
23 Correct 276 ms 15864 KB Output is correct
24 Correct 1194 ms 12208 KB Output is correct
25 Correct 2141 ms 17400 KB Output is correct
26 Correct 1772 ms 17528 KB Output is correct
27 Correct 1551 ms 17044 KB Output is correct
28 Correct 801 ms 56048 KB Output is correct
29 Correct 2191 ms 51372 KB Output is correct
30 Correct 6855 ms 48300 KB Output is correct
31 Correct 6441 ms 87480 KB Output is correct
32 Correct 945 ms 10872 KB Output is correct
33 Correct 1227 ms 14456 KB Output is correct
34 Correct 384 ms 44792 KB Output is correct
35 Correct 1475 ms 29740 KB Output is correct
36 Correct 2885 ms 49052 KB Output is correct
37 Correct 2240 ms 49328 KB Output is correct
38 Correct 2271 ms 48744 KB Output is correct
39 Correct 1976 ms 40024 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 376 KB Output is correct
4 Correct 2 ms 252 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 3 ms 400 KB Output is correct
7 Correct 2 ms 376 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 3 ms 376 KB Output is correct
12 Correct 813 ms 13940 KB Output is correct
13 Correct 586 ms 13700 KB Output is correct
14 Correct 704 ms 11128 KB Output is correct
15 Correct 785 ms 10980 KB Output is correct
16 Correct 501 ms 8612 KB Output is correct
17 Correct 834 ms 10872 KB Output is correct
18 Correct 682 ms 10560 KB Output is correct
19 Correct 1499 ms 16920 KB Output is correct
20 Correct 2751 ms 10716 KB Output is correct
21 Correct 407 ms 5880 KB Output is correct
22 Correct 3224 ms 13540 KB Output is correct
23 Correct 282 ms 15864 KB Output is correct
24 Correct 1246 ms 12120 KB Output is correct
25 Correct 2025 ms 17528 KB Output is correct
26 Correct 1719 ms 17536 KB Output is correct
27 Correct 1569 ms 16964 KB Output is correct
28 Correct 772 ms 56208 KB Output is correct
29 Correct 2177 ms 51240 KB Output is correct
30 Correct 6778 ms 48212 KB Output is correct
31 Correct 6493 ms 87500 KB Output is correct
32 Correct 947 ms 10744 KB Output is correct
33 Correct 1197 ms 14552 KB Output is correct
34 Correct 396 ms 44792 KB Output is correct
35 Correct 1500 ms 29944 KB Output is correct
36 Correct 2869 ms 49116 KB Output is correct
37 Correct 2308 ms 49400 KB Output is correct
38 Correct 2212 ms 48632 KB Output is correct
39 Correct 1114 ms 110976 KB Output is correct
40 Correct 3255 ms 94924 KB Output is correct
41 Correct 8718 ms 95692 KB Output is correct
42 Correct 8663 ms 173492 KB Output is correct
43 Correct 841 ms 89464 KB Output is correct
44 Correct 1423 ms 11128 KB Output is correct
45 Correct 1890 ms 40160 KB Output is correct
46 Correct 3726 ms 93564 KB Output is correct
47 Correct 3733 ms 93624 KB Output is correct
48 Correct 3523 ms 93052 KB Output is correct
49 Correct 2 ms 256 KB Output is correct