oj.uz

Submission #152476

# Submission time Handle Problem Language Result Execution time Memory
152476 2019-09-08T06:45:11 Z arnold518 Game (IOI13_game) C++14
80 / 100
 7654 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(nodes1[node].pos!=-1)
    {
        if(xl<=nodes1[node].pos && nodes1[node].pos<=xr) return nodes1[node].val;
        else return 0;
    }
    if(xl<=tl && tr<=xr) return nodes1[node].val;
    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 256 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 380 KB Output is correct
6 Correct 3 ms 504 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 3 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 376 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 874 ms 9476 KB Output is correct
5 Correct 635 ms 9548 KB Output is correct
6 Correct 711 ms 7460 KB Output is correct
7 Correct 806 ms 6628 KB Output is correct
8 Correct 517 ms 4736 KB Output is correct
9 Correct 785 ms 6884 KB Output is correct
10 Correct 702 ms 6628 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 256 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 376 KB Output is correct
8 Correct 2 ms 252 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 1558 ms 16916 KB Output is correct
13 Correct 2912 ms 6780 KB Output is correct
14 Correct 414 ms 1164 KB Output is correct
15 Correct 3442 ms 6612 KB Output is correct
16 Correct 295 ms 12772 KB Output is correct
17 Correct 1184 ms 7408 KB Output is correct
18 Correct 2068 ms 13260 KB Output is correct
19 Correct 1808 ms 13768 KB Output is correct
20 Correct 1631 ms 13492 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 256 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 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 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 869 ms 9476 KB Output is correct
13 Correct 639 ms 9592 KB Output is correct
14 Correct 704 ms 7396 KB Output is correct
15 Correct 809 ms 6632 KB Output is correct
16 Correct 508 ms 4692 KB Output is correct
17 Correct 785 ms 6924 KB Output is correct
18 Correct 733 ms 6628 KB Output is correct
19 Correct 1570 ms 16688 KB Output is correct
20 Correct 2903 ms 6912 KB Output is correct
21 Correct 408 ms 1096 KB Output is correct
22 Correct 3434 ms 6644 KB Output is correct
23 Correct 295 ms 12900 KB Output is correct
24 Correct 1225 ms 7500 KB Output is correct
25 Correct 2081 ms 13076 KB Output is correct
26 Correct 1823 ms 13672 KB Output is correct
27 Correct 1624 ms 13200 KB Output is correct
28 Correct 1226 ms 202792 KB Output is correct
29 Correct 2731 ms 215152 KB Output is correct
30 Correct 7634 ms 100608 KB Output is correct
31 Correct 7191 ms 100736 KB Output is correct
32 Correct 942 ms 10456 KB Output is correct
33 Correct 1192 ms 12644 KB Output is correct
34 Correct 788 ms 203096 KB Output is correct
35 Correct 1802 ms 111560 KB Output is correct
36 Correct 3434 ms 206616 KB Output is correct
37 Correct 2886 ms 213172 KB Output is correct
38 Correct 2783 ms 212344 KB Output is correct
39 Correct 2269 ms 108768 KB Output is correct
40 Correct 3 ms 256 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 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 376 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 875 ms 9548 KB Output is correct
13 Correct 639 ms 9724 KB Output is correct
14 Correct 705 ms 7616 KB Output is correct
15 Correct 794 ms 6752 KB Output is correct
16 Correct 522 ms 4712 KB Output is correct
17 Correct 759 ms 7240 KB Output is correct
18 Correct 694 ms 6752 KB Output is correct
19 Correct 1561 ms 16940 KB Output is correct
20 Correct 2920 ms 7232 KB Output is correct
21 Correct 409 ms 1372 KB Output is correct
22 Correct 3430 ms 6772 KB Output is correct
23 Correct 300 ms 12904 KB Output is correct
24 Correct 1180 ms 7632 KB Output is correct
25 Correct 2182 ms 13344 KB Output is correct
26 Correct 1914 ms 13768 KB Output is correct
27 Correct 1682 ms 13576 KB Output is correct
28 Correct 1238 ms 202912 KB Output is correct
29 Correct 2686 ms 215236 KB Output is correct
30 Correct 7654 ms 100736 KB Output is correct
31 Correct 7183 ms 100792 KB Output is correct
32 Correct 947 ms 10676 KB Output is correct
33 Correct 1195 ms 12512 KB Output is correct
34 Correct 789 ms 202916 KB Output is correct
35 Correct 1823 ms 111404 KB Output is correct
36 Correct 3498 ms 206828 KB Output is correct
37 Correct 2828 ms 213072 KB Output is correct
38 Correct 2761 ms 212412 KB Output is correct
39 Runtime error 1467 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
40 Halted 0 ms 0 KB -