oj.uz

Submission #112687

# Submission time Handle Problem Language Result Execution time Memory
112687 2019-05-21T12:39:35 Z arnold518 Game (IOI13_game) C++14
100 / 100
 7549 ms 173340 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 && node->val!=NULL) return query1(node->val, 1, c, lx, rx);
    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:119: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 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 3 ms 384 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 384 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 2 ms 404 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 694 ms 13788 KB Output is correct
5 Correct 491 ms 13480 KB Output is correct
6 Correct 676 ms 11144 KB Output is correct
7 Correct 771 ms 10760 KB Output is correct
8 Correct 435 ms 8824 KB Output is correct
9 Correct 773 ms 10876 KB Output is correct
10 Correct 659 ms 10616 KB Output is correct
11 Correct 2 ms 384 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 2 ms 384 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 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 1264 ms 16940 KB Output is correct
13 Correct 2349 ms 10868 KB Output is correct
14 Correct 337 ms 5824 KB Output is correct
15 Correct 3154 ms 13644 KB Output is correct
16 Correct 291 ms 15816 KB Output is correct
17 Correct 1274 ms 12152 KB Output is correct
18 Correct 2511 ms 17612 KB Output is correct
19 Correct 1876 ms 17668 KB Output is correct
20 Correct 1711 ms 17144 KB Output is correct
21 Correct 2 ms 384 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 2 ms 356 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 738 ms 13836 KB Output is correct
13 Correct 514 ms 13508 KB Output is correct
14 Correct 708 ms 11276 KB Output is correct
15 Correct 731 ms 10796 KB Output is correct
16 Correct 444 ms 8660 KB Output is correct
17 Correct 765 ms 10876 KB Output is correct
18 Correct 728 ms 10744 KB Output is correct
19 Correct 1356 ms 17144 KB Output is correct
20 Correct 2370 ms 10804 KB Output is correct
21 Correct 351 ms 5880 KB Output is correct
22 Correct 2877 ms 13524 KB Output is correct
23 Correct 277 ms 15916 KB Output is correct
24 Correct 1245 ms 12244 KB Output is correct
25 Correct 2413 ms 17552 KB Output is correct
26 Correct 2055 ms 17544 KB Output is correct
27 Correct 1955 ms 17104 KB Output is correct
28 Correct 864 ms 56056 KB Output is correct
29 Correct 2091 ms 51288 KB Output is correct
30 Correct 5765 ms 48304 KB Output is correct
31 Correct 5271 ms 87424 KB Output is correct
32 Correct 728 ms 10828 KB Output is correct
33 Correct 1076 ms 14608 KB Output is correct
34 Correct 387 ms 44952 KB Output is correct
35 Correct 1733 ms 29884 KB Output is correct
36 Correct 3378 ms 49092 KB Output is correct
37 Correct 2797 ms 49344 KB Output is correct
38 Correct 2530 ms 48752 KB Output is correct
39 Correct 2220 ms 40156 KB Output is correct
40 Correct 2 ms 384 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 714 ms 13628 KB Output is correct
13 Correct 493 ms 13560 KB Output is correct
14 Correct 659 ms 11120 KB Output is correct
15 Correct 787 ms 10872 KB Output is correct
16 Correct 443 ms 8788 KB Output is correct
17 Correct 763 ms 10896 KB Output is correct
18 Correct 679 ms 10436 KB Output is correct
19 Correct 1237 ms 17016 KB Output is correct
20 Correct 2319 ms 10840 KB Output is correct
21 Correct 336 ms 5752 KB Output is correct
22 Correct 2713 ms 13572 KB Output is correct
23 Correct 263 ms 15864 KB Output is correct
24 Correct 1181 ms 12280 KB Output is correct
25 Correct 2178 ms 17372 KB Output is correct
26 Correct 1779 ms 17748 KB Output is correct
27 Correct 1805 ms 17076 KB Output is correct
28 Correct 767 ms 56056 KB Output is correct
29 Correct 1896 ms 51316 KB Output is correct
30 Correct 5637 ms 48140 KB Output is correct
31 Correct 5385 ms 87560 KB Output is correct
32 Correct 778 ms 10820 KB Output is correct
33 Correct 1083 ms 14468 KB Output is correct
34 Correct 362 ms 44792 KB Output is correct
35 Correct 1635 ms 29800 KB Output is correct
36 Correct 3447 ms 49148 KB Output is correct
37 Correct 2672 ms 49368 KB Output is correct
38 Correct 2861 ms 48600 KB Output is correct
39 Correct 1167 ms 111024 KB Output is correct
40 Correct 3444 ms 94968 KB Output is correct
41 Correct 7549 ms 95716 KB Output is correct
42 Correct 7448 ms 173340 KB Output is correct
43 Correct 801 ms 89560 KB Output is correct
44 Correct 1104 ms 11228 KB Output is correct
45 Correct 2081 ms 40140 KB Output is correct
46 Correct 4343 ms 93584 KB Output is correct
47 Correct 4437 ms 93764 KB Output is correct
48 Correct 4451 ms 93316 KB Output is correct
49 Correct 2 ms 256 KB Output is correct