oj.uz

Submission #152477

# Submission time Handle Problem Language Result Execution time Memory
152477 2019-09-08T06:48:56 Z arnold518 Game (IOI13_game) C++14
80 / 100
 7360 ms 256004 KB 
#include "game.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

int R, C;

struct Node1
{
    ll val; int lc, rc, pos;
    Node1() : val(0), lc(-1), rc(-1), pos(-1) {}
};
vector<Node1> nodes1;
int newNode1()
{
    nodes1.push_back(Node1());
    return (int)nodes1.size()-1;
}

struct Node2
{
    int val; int lc, rc;
    Node2() : val(-1), lc(-1), rc(-1) {}
};
vector<Node2> nodes2;
int newNode2()
{
    nodes2.push_back(Node2());
    return (int)nodes2.size()-1;
}

void update1(int node, int tl, int tr, int x, ll val)
{
    //printf("%d %d %d %d %lld\n", node, tl, tr, x, val);
    if(tl==tr)
    {
        nodes1[node].val=val;
        return;
    }

    int mid=tl+tr>>1;
    if(nodes1[node].pos!=-1)
    {
        if(nodes1[node].pos<=mid)
        {
            int t=newNode1(); nodes1[node].lc=t;
            nodes1[nodes1[node].lc].pos=nodes1[node].pos;
            nodes1[nodes1[node].lc].val=nodes1[node].val;
        }
        else
        {
            int t=newNode1(); nodes1[node].rc=t;
            nodes1[nodes1[node].rc].pos=nodes1[node].pos;
            nodes1[nodes1[node].rc].val=nodes1[node].val;
        }
        nodes1[node].pos=-1;
    }

    if(x<=mid)
    {
        if(nodes1[node].lc==-1)
        {
            int t=newNode1(); nodes1[node].lc=t;
            nodes1[nodes1[node].lc].pos=x;
            nodes1[nodes1[node].lc].val=val;
        }
        else update1(nodes1[node].lc, tl, mid, x, val);
    }
    else
    {
        if(nodes1[node].rc==-1)
        {
            int t=newNode1(); nodes1[node].rc=t;
            nodes1[nodes1[node].rc].pos=x;
            nodes1[nodes1[node].rc].val=val;
        }
        update1(nodes1[node].rc, mid+1, tr, x, val);
    }
    ll t=0;
    if(nodes1[node].lc!=-1) t=__gcd(t, nodes1[nodes1[node].lc].val);
    if(nodes1[node].rc!=-1) t=__gcd(t, nodes1[nodes1[node].rc].val);
    nodes1[node].val=t;
}

ll query1(int node, int tl, int tr, int xl, int xr)
{
    //printf("%d %d %d %d %d\n", node, tl, tr, xl, xr);
    if(xr<tl || tr<xl) return 0;
    if(xl<=tl && tr<=xr) return nodes1[node].val;
    if(nodes1[node].pos!=-1)
    {
        if(xl<=nodes1[node].pos && nodes1[node].pos<=xr) return nodes1[node].val;
        else return 0;
    }
    int mid=tl+tr>>1;
    ll ret=0;
    if(nodes1[node].lc!=-1) ret=__gcd(ret, query1(nodes1[node].lc, tl, mid, xl, xr));
    if(nodes1[node].rc!=-1) ret=__gcd(ret, query1(nodes1[node].rc, mid+1, tr, xl, xr));
    return ret;
}

void update2(int node, int tl, int tr, int y, int x, ll val)
{
    //printf("%d %d %d %d %d %lld\n", node, tl, tr, y, x, val);
    if(nodes2[node].val==-1) { int t=newNode1(); nodes2[node].val=t; }
    if(tl==tr)
    {
        update1(nodes2[node].val, 1, C, x, val);
        return;
    }
    int mid=tl+tr>>1;
    if(y<=mid)
    {
        if(nodes2[node].lc==-1) { int t=newNode2(); nodes2[node].lc=t; }
        update2(nodes2[node].lc, tl, mid, y, x, val);
    }
    else
    {
        if(nodes2[node].rc==-1) { int t=newNode2(); nodes2[node].rc=t; }
        update2(nodes2[node].rc, mid+1, tr, y, x, val);
    }
    ll t=0;
    if(nodes2[node].lc!=-1) t=__gcd(t, query1(nodes2[nodes2[node].lc].val, 1, C, x, x));
    if(nodes2[node].rc!=-1) t=__gcd(t, query1(nodes2[nodes2[node].rc].val, 1, C, x, x));
    update1(nodes2[node].val, 1, C, x, t);
}

ll query2(int node, int tl, int tr, int yl, int yr, int xl, int xr)
{
    //printf("%d %d %d %d %d %d %d\n", node, tl, tr, yl, yr, xl, xr);
    if(yr<tl || tr<yl) return 0;
    if(yl<=tl && tr<=yr)
    {
        if(nodes2[node].val!=-1) return query1(nodes2[node].val, 1, C, xl, xr);
        else return 0;
    }
    int mid=tl+tr>>1;
    ll ret=0;
    if(nodes2[node].lc!=-1) ret=__gcd(ret, query2(nodes2[node].lc, tl, mid, yl, yr, xl, xr));
    if(nodes2[node].rc!=-1) ret=__gcd(ret, query2(nodes2[node].rc, mid+1, tr, yl, yr, xl, xr));
    return ret;
}

int root;

void init(int _R, int _C)
{
    int i, j;
    R=_R; C=_C;
    root=newNode2();
}

void update(int P, int Q, ll K)
{
    int i, j;
    P++; Q++;
    update2(root, 1, R, P, Q, K);
}

ll calculate(int P, int Q, int U, int V)
{
    int i, j;
    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(int, int, int, int, ll)':
game.cpp:44:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=tl+tr>>1;
             ~~^~~
game.cpp: In function 'll query1(int, int, int, int, int)':
game.cpp:98:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=tl+tr>>1;
             ~~^~~
game.cpp: In function 'void update2(int, int, int, int, int, ll)':
game.cpp:114:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=tl+tr>>1;
             ~~^~~
game.cpp: In function 'll query2(int, int, int, int, int, int, int)':
game.cpp:140:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=tl+tr>>1;
             ~~^~~
game.cpp: In function 'void init(int, int)':
game.cpp:151:9: warning: unused variable 'i' [-Wunused-variable]
     int i, j;
         ^
game.cpp:151:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
game.cpp: In function 'void update(int, int, ll)':
game.cpp:158:9: warning: unused variable 'i' [-Wunused-variable]
     int i, j;
         ^
game.cpp:158:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
game.cpp: In function 'll calculate(int, int, int, int)':
game.cpp:165:9: warning: unused variable 'i' [-Wunused-variable]
     int i, j;
         ^
game.cpp:165:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^

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 504 KB Output is correct
3 Correct 3 ms 504 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 252 KB Output is correct
6 Correct 3 ms 504 KB Output is correct
7 Correct 2 ms 380 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 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 256 KB Output is correct
4 Correct 849 ms 10144 KB Output is correct
5 Correct 612 ms 10340 KB Output is correct
6 Correct 691 ms 8236 KB Output is correct
7 Correct 784 ms 7012 KB Output is correct
8 Correct 513 ms 5472 KB Output is correct
9 Correct 765 ms 7648 KB Output is correct
10 Correct 684 ms 7340 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 376 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 3 ms 504 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 3 ms 504 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 504 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 1481 ms 17432 KB Output is correct
13 Correct 2769 ms 7740 KB Output is correct
14 Correct 404 ms 1784 KB Output is correct
15 Correct 3227 ms 7028 KB Output is correct
16 Correct 288 ms 13156 KB Output is correct
17 Correct 1179 ms 8292 KB Output is correct
18 Correct 1981 ms 13924 KB Output is correct
19 Correct 1815 ms 14352 KB Output is correct
20 Correct 1640 ms 13900 KB Output is correct
21 Correct 2 ms 256 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 3 ms 504 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 504 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 7 ms 376 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 872 ms 10124 KB Output is correct
13 Correct 611 ms 10344 KB Output is correct
14 Correct 722 ms 8164 KB Output is correct
15 Correct 789 ms 7012 KB Output is correct
16 Correct 511 ms 5352 KB Output is correct
17 Correct 795 ms 7780 KB Output is correct
18 Correct 674 ms 7268 KB Output is correct
19 Correct 1474 ms 17596 KB Output is correct
20 Correct 2773 ms 7584 KB Output is correct
21 Correct 404 ms 1784 KB Output is correct
22 Correct 3243 ms 7024 KB Output is correct
23 Correct 290 ms 13156 KB Output is correct
24 Correct 1195 ms 8204 KB Output is correct
25 Correct 2124 ms 13804 KB Output is correct
26 Correct 1760 ms 14332 KB Output is correct
27 Correct 1631 ms 13956 KB Output is correct
28 Correct 1231 ms 203464 KB Output is correct
29 Correct 2609 ms 206816 KB Output is correct
30 Correct 7337 ms 100872 KB Output is correct
31 Correct 6953 ms 100764 KB Output is correct
32 Correct 925 ms 2472 KB Output is correct
33 Correct 1164 ms 4240 KB Output is correct
34 Correct 790 ms 203040 KB Output is correct
35 Correct 1845 ms 103772 KB Output is correct
36 Correct 3355 ms 203716 KB Output is correct
37 Correct 2847 ms 204492 KB Output is correct
38 Correct 2816 ms 203788 KB Output is correct
39 Correct 2308 ms 103200 KB Output is correct
40 Correct 2 ms 256 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 252 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 3 ms 476 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 488 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 348 KB Output is correct
10 Correct 2 ms 348 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 843 ms 10316 KB Output is correct
13 Correct 616 ms 10456 KB Output is correct
14 Correct 702 ms 8308 KB Output is correct
15 Correct 776 ms 7012 KB Output is correct
16 Correct 501 ms 5548 KB Output is correct
17 Correct 747 ms 7728 KB Output is correct
18 Correct 672 ms 7244 KB Output is correct
19 Correct 1478 ms 17588 KB Output is correct
20 Correct 2763 ms 7668 KB Output is correct
21 Correct 406 ms 1908 KB Output is correct
22 Correct 3255 ms 6992 KB Output is correct
23 Correct 288 ms 13028 KB Output is correct
24 Correct 1230 ms 8336 KB Output is correct
25 Correct 2039 ms 14096 KB Output is correct
26 Correct 1734 ms 14480 KB Output is correct
27 Correct 1658 ms 14096 KB Output is correct
28 Correct 1256 ms 203708 KB Output is correct
29 Correct 2637 ms 206712 KB Output is correct
30 Correct 7360 ms 100652 KB Output is correct
31 Correct 6968 ms 100788 KB Output is correct
32 Correct 920 ms 2424 KB Output is correct
33 Correct 1163 ms 4456 KB Output is correct
34 Correct 789 ms 203028 KB Output is correct
35 Correct 1827 ms 103696 KB Output is correct
36 Correct 3336 ms 203696 KB Output is correct
37 Correct 2900 ms 204408 KB Output is correct
38 Correct 2840 ms 203872 KB Output is correct
39 Runtime error 1474 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
40 Halted 0 ms 0 KB -