답안 #152478

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
152478	2019-09-08T06:49:57 Z	arnold518	게임 (IOI13_game)	C++14	100 / 100	8600 ms	102708 KB

game

#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;
        }
        else 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

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	352 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	256 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	256 KB	Output is correct
9	Correct	3 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	2 ms	376 KB	Output is correct

Subtask #2

27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	256 KB	Output is correct
2	Correct	2 ms	360 KB	Output is correct
3	Correct	2 ms	256 KB	Output is correct
4	Correct	811 ms	7340 KB	Output is correct
5	Correct	582 ms	7468 KB	Output is correct
6	Correct	666 ms	4636 KB	Output is correct
7	Correct	737 ms	4044 KB	Output is correct
8	Correct	481 ms	3688 KB	Output is correct
9	Correct	721 ms	4152 KB	Output is correct
10	Correct	651 ms	3732 KB	Output is correct
11	Correct	2 ms	256 KB	Output is correct

Subtask #3

26.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	256 KB	Output is correct
2	Correct	3 ms	376 KB	Output is correct
3	Correct	0 ms	380 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	380 KB	Output is correct
7	Correct	2 ms	396 KB	Output is correct
8	Correct	2 ms	256 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	1452 ms	9936 KB	Output is correct
13	Correct	2768 ms	4248 KB	Output is correct
14	Correct	413 ms	1320 KB	Output is correct
15	Correct	3219 ms	6776 KB	Output is correct
16	Correct	270 ms	6780 KB	Output is correct
17	Correct	1121 ms	4884 KB	Output is correct
18	Correct	1850 ms	7196 KB	Output is correct
19	Correct	1564 ms	7672 KB	Output is correct
20	Correct	1502 ms	7316 KB	Output is correct
21	Correct	2 ms	256 KB	Output is correct

Subtask #4

17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	252 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	256 KB	Output is correct
6	Correct	3 ms	380 KB	Output is correct
7	Correct	2 ms	248 KB	Output is correct
8	Correct	2 ms	256 KB	Output is correct
9	Correct	3 ms	360 KB	Output is correct
10	Correct	2 ms	360 KB	Output is correct
11	Correct	2 ms	380 KB	Output is correct
12	Correct	802 ms	7240 KB	Output is correct
13	Correct	579 ms	7468 KB	Output is correct
14	Correct	673 ms	4560 KB	Output is correct
15	Correct	744 ms	3940 KB	Output is correct
16	Correct	475 ms	3556 KB	Output is correct
17	Correct	718 ms	4060 KB	Output is correct
18	Correct	650 ms	3816 KB	Output is correct
19	Correct	1433 ms	9980 KB	Output is correct
20	Correct	2771 ms	4380 KB	Output is correct
21	Correct	410 ms	1308 KB	Output is correct
22	Correct	3219 ms	6860 KB	Output is correct
23	Correct	277 ms	6784 KB	Output is correct
24	Correct	1087 ms	4832 KB	Output is correct
25	Correct	1856 ms	7168 KB	Output is correct
26	Correct	1584 ms	7576 KB	Output is correct
27	Correct	1467 ms	7196 KB	Output is correct
28	Correct	759 ms	28424 KB	Output is correct
29	Correct	1990 ms	33040 KB	Output is correct
30	Correct	6767 ms	27528 KB	Output is correct
31	Correct	6363 ms	51484 KB	Output is correct
32	Correct	925 ms	1944 KB	Output is correct
33	Correct	1205 ms	3844 KB	Output is correct
34	Correct	369 ms	29936 KB	Output is correct
35	Correct	1383 ms	16768 KB	Output is correct
36	Correct	2640 ms	30696 KB	Output is correct
37	Correct	2109 ms	31260 KB	Output is correct
38	Correct	2001 ms	30860 KB	Output is correct
39	Correct	1851 ms	18852 KB	Output is correct
40	Correct	2 ms	256 KB	Output is correct

Subtask #5

20.0 / 20.0

#	결과	실행 시간	메모리	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	128 KB	Output is correct
6	Correct	3 ms	376 KB	Output is correct
7	Correct	2 ms	256 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	808 ms	7648 KB	Output is correct
13	Correct	578 ms	8040 KB	Output is correct
14	Correct	675 ms	5000 KB	Output is correct
15	Correct	755 ms	4716 KB	Output is correct
16	Correct	480 ms	4152 KB	Output is correct
17	Correct	728 ms	4836 KB	Output is correct
18	Correct	680 ms	4548 KB	Output is correct
19	Correct	1438 ms	10600 KB	Output is correct
20	Correct	2757 ms	5108 KB	Output is correct
21	Correct	410 ms	2040 KB	Output is correct
22	Correct	3222 ms	6908 KB	Output is correct
23	Correct	265 ms	7688 KB	Output is correct
24	Correct	1100 ms	5500 KB	Output is correct
25	Correct	1860 ms	8160 KB	Output is correct
26	Correct	1576 ms	8492 KB	Output is correct
27	Correct	1461 ms	8308 KB	Output is correct
28	Correct	753 ms	29284 KB	Output is correct
29	Correct	1988 ms	33356 KB	Output is correct
30	Correct	6778 ms	27420 KB	Output is correct
31	Correct	6404 ms	51140 KB	Output is correct
32	Correct	911 ms	1440 KB	Output is correct
33	Correct	1141 ms	3576 KB	Output is correct
34	Correct	366 ms	29820 KB	Output is correct
35	Correct	1371 ms	16352 KB	Output is correct
36	Correct	2642 ms	30328 KB	Output is correct
37	Correct	2123 ms	30968 KB	Output is correct
38	Correct	2021 ms	30288 KB	Output is correct
39	Correct	1044 ms	65992 KB	Output is correct
40	Correct	3068 ms	68696 KB	Output is correct
41	Correct	8600 ms	54304 KB	Output is correct
42	Correct	8423 ms	102708 KB	Output is correct
43	Correct	718 ms	59796 KB	Output is correct
44	Correct	1360 ms	10980 KB	Output is correct
45	Correct	1754 ms	28572 KB	Output is correct
46	Correct	3323 ms	67100 KB	Output is correct
47	Correct	3312 ms	66808 KB	Output is correct
48	Correct	3273 ms	66572 KB	Output is correct
49	Correct	2 ms	256 KB	Output is correct