oj.uz

Submission #152471

# Submission time Handle Problem Language Result Execution time Memory
152471 2019-09-08T06:17:13 Z arnold518 Game (IOI13_game) C++14
63 / 100
 3202 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;
    Node1() : val(0), lc(-1), rc(-1) {}
};
vector<Node1> nodes1;
int newNode1()
{
    nodes1.push_back(Node1());
    //printf("???%d %d %lld\n", nodes1.back().lc, nodes1.back().rc, nodes1.back().val);
    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());
    //printf("???%d %d %d\n", nodes2.back().lc, nodes2.back().rc, nodes2.back().val);
    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(x<=mid)
    {
        if(nodes1[node].lc==-1) { int t=newNode1(); nodes1[node].lc=t; }
        update1(nodes1[node].lc, tl, mid, x, val);
    }
    else
    {
        if(nodes1[node].rc==-1) { int t=newNode1(); nodes1[node].rc=t; }
        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;
    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:45: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:67: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:83: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:109:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=tl+tr>>1;
             ~~^~~
game.cpp: In function 'void init(int, int)':
game.cpp:120:9: warning: unused variable 'i' [-Wunused-variable]
     int i, j;
         ^
game.cpp:120:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
game.cpp: In function 'void update(int, int, ll)':
game.cpp:127:9: warning: unused variable 'i' [-Wunused-variable]
     int i, j;
         ^
game.cpp:127:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
game.cpp: In function 'll calculate(int, int, int, int)':
game.cpp:134:9: warning: unused variable 'i' [-Wunused-variable]
     int i, j;
         ^
game.cpp:134: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 380 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 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 380 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 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 2 ms 256 KB Output is correct
4 Correct 872 ms 17040 KB Output is correct
5 Correct 627 ms 16844 KB Output is correct
6 Correct 751 ms 14332 KB Output is correct
7 Correct 824 ms 10328 KB Output is correct
8 Correct 538 ms 9744 KB Output is correct
9 Correct 801 ms 11036 KB Output is correct
10 Correct 716 ms 9936 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 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 256 KB Output is correct
6 Correct 3 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 3 ms 376 KB Output is correct
10 Correct 3 ms 380 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 1525 ms 14444 KB Output is correct
13 Correct 2741 ms 7708 KB Output is correct
14 Correct 409 ms 5640 KB Output is correct
15 Correct 3197 ms 9528 KB Output is correct
16 Correct 310 ms 17420 KB Output is correct
17 Correct 1235 ms 14028 KB Output is correct
18 Correct 2176 ms 19620 KB Output is correct
19 Correct 1834 ms 23008 KB Output is correct
20 Correct 1703 ms 22536 KB Output is correct
21 Correct 2 ms 256 KB Output is correct

Subtask #4
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 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 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 504 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 882 ms 17176 KB Output is correct
13 Correct 618 ms 16856 KB Output is correct
14 Correct 724 ms 14428 KB Output is correct
15 Correct 822 ms 10320 KB Output is correct
16 Correct 520 ms 9704 KB Output is correct
17 Correct 795 ms 10996 KB Output is correct
18 Correct 749 ms 9976 KB Output is correct
19 Correct 1506 ms 14568 KB Output is correct
20 Correct 2747 ms 7964 KB Output is correct
21 Correct 408 ms 5712 KB Output is correct
22 Correct 3182 ms 9748 KB Output is correct
23 Correct 309 ms 17548 KB Output is correct
24 Correct 1230 ms 13916 KB Output is correct
25 Correct 2090 ms 19544 KB Output is correct
26 Correct 1815 ms 23024 KB Output is correct
27 Correct 1706 ms 22680 KB Output is correct
28 Correct 1286 ms 140424 KB Output is correct
29 Runtime error 3017 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
30 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 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 3 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 376 KB Output is correct
9 Correct 3 ms 504 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 876 ms 17200 KB Output is correct
13 Correct 622 ms 16868 KB Output is correct
14 Correct 727 ms 14392 KB Output is correct
15 Correct 814 ms 10212 KB Output is correct
16 Correct 529 ms 9732 KB Output is correct
17 Correct 769 ms 10976 KB Output is correct
18 Correct 685 ms 10064 KB Output is correct
19 Correct 1479 ms 14528 KB Output is correct
20 Correct 2765 ms 7688 KB Output is correct
21 Correct 408 ms 5756 KB Output is correct
22 Correct 3202 ms 9568 KB Output is correct
23 Correct 301 ms 17484 KB Output is correct
24 Correct 1242 ms 13892 KB Output is correct
25 Correct 2005 ms 19508 KB Output is correct
26 Correct 1765 ms 22960 KB Output is correct
27 Correct 1658 ms 22544 KB Output is correct
28 Correct 1259 ms 140540 KB Output is correct
29 Runtime error 2849 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
30 Halted 0 ms 0 KB -