oj.uz

Submission #361617

# Submission time Handle Problem Language Result Execution time Memory
361617 2021-01-30T20:26:55 Z gratus907 Game (IOI13_game) C++17
100 / 100
 3800 ms 82360 KB 
#include <bits/stdc++.h>
#include "game.h"
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#define ll long long
#define int ll
#define eps 1e-7
#define all(x) ((x).begin()),((x).end())
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
const int MAXR = 1000000007;
const int MAXC = 1000000007;

int game_gcd(int a, int b) 
{
    if (a == 0 || b == 0) return a + b;
    else return __gcd(a, b);
}
void init(int32_t R, int32_t C) {}
int agg(int a, int b) {return game_gcd(a, b);}
struct Dynamic2DSeg
{
    struct Node
    {
        Node (int l, int r, int v = 0) : l(l), r(r), v(v), lc(NULL), rc(NULL){}
        int l, r, v;
        Node *lc, *rc;
    };
    struct RowNode
    {
        RowNode () : lc(NULL), rc(NULL), rowRoot(0, MAXC, 0){}
        Node rowRoot;
        RowNode *lc, *rc;
    };
    RowNode root;
    static void update2(Node *node, int idx, int dt)
    {
        int lo = node -> l;
        int hi = node -> r;
        int mid = (lo + hi) / 2;
        if (lo + 1 == hi)
        {
            node -> v = dt;
            return;
        }
        Node *& next = idx < mid ? node -> lc : node -> rc;
        if (next == NULL)
            next = new Node(idx, idx + 1, dt);
        else if (next -> l <= idx && idx < next -> r)
            update2(next, idx, dt);
        else
        {
            do {
                (idx < mid ? hi : lo) = mid;
                mid = (lo + hi) / 2;
            } while ((idx < mid) == (next->l < mid));
            Node * nnode = new Node(lo, hi);
            (next->l < mid ? nnode->lc : nnode->rc) = next;
            next = nnode;

            update2(nnode, idx, dt);
        }
        node -> v = agg(node->lc?node->lc->v:0, node->rc?node->rc->v:0);
    }
    static void update1(RowNode * node, int lo, int hi, int ridx, int idx, int dt)
    {
        int mid = (lo + hi) / 2;
        if (lo + 1 == hi)
            update2(&node -> rowRoot, idx, dt);
        else
        {
            RowNode *& nnode = ridx < mid ? node -> lc : node -> rc;
            (ridx < mid ? hi : lo) = mid;
            if (nnode == NULL)
                nnode = new RowNode();
            update1(nnode, lo, hi, ridx, idx, dt);
            dt = agg(node->lc ? query2(&node->lc->rowRoot, idx, idx + 1) : 0,
                     node->rc ? query2(&node->rc->rowRoot, idx, idx + 1) : 0);
            update2(&node->rowRoot, idx, dt);
        }
    }
    static int query2(Node *node, int a, int b)
    {
        if (node == NULL || b <= node -> l || node -> r <= a)
            return 0;
        else if (a <= node -> l && node -> r <= b)
            return node -> v;
        return agg(query2(node->lc, a, b), query2(node->rc, a, b));
    }
    static int query1(RowNode *node, int lo, int hi, int a1, int b1, int a2, int b2)
    {
        if (node == NULL || b1 <= lo || hi <= a1)
            return 0;
        else if (a1 <= lo && hi <= b1)
            return query2(&node->rowRoot, a2, b2);
        int mid = (lo + hi) / 2;
        return agg(query1(node->lc, lo, mid, a1, b1, a2, b2),
                   query1(node->rc, mid, hi, a1, b1, a2, b2));
    }
    void update(int x, int y, int dt)
    {
        update1(&root, 0, MAXR, x, y, dt);
    }
    int query(int x1, int y1, int x2, int y2)
    {
        return query1(&root, 0, MAXR, x1, x2 + 1, y1, y2 + 1);
    }
} DSEG;

void update(int32_t P,int32_t Q,long long K)
{
    DSEG.update(P, Q, K);
}
long long calculate(int32_t P,int32_t Q,int32_t U,int32_t V){
    return DSEG.query(P, Q, U, V);
}

Compilation message

game.cpp: In constructor 'Dynamic2DSeg::RowNode::RowNode()':
game.cpp:34:23: warning: 'Dynamic2DSeg::RowNode::rc' will be initialized after [-Wreorder]
   34 |         RowNode *lc, *rc;
      |                       ^~
game.cpp:33:14: warning:   'Dynamic2DSeg::Node Dynamic2DSeg::RowNode::rowRoot' [-Wreorder]
   33 |         Node rowRoot;
      |              ^~~~~~~
game.cpp:32:9: warning:   when initialized here [-Wreorder]
   32 |         RowNode () : lc(NULL), rc(NULL), rowRoot(0, MAXC, 0){}
      |         ^~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 492 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 2 ms 512 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 2 ms 492 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 492 KB Output is correct
12 Correct 1 ms 364 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 875 ms 34540 KB Output is correct
5 Correct 588 ms 36204 KB Output is correct
6 Correct 904 ms 33848 KB Output is correct
7 Correct 1004 ms 33772 KB Output is correct
8 Correct 604 ms 19840 KB Output is correct
9 Correct 1000 ms 33600 KB Output is correct
10 Correct 987 ms 33308 KB Output is correct
11 Correct 1 ms 364 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 492 KB Output is correct
3 Correct 2 ms 492 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 2 ms 492 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 2 ms 492 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 492 KB Output is correct
12 Correct 926 ms 17772 KB Output is correct
13 Correct 1350 ms 11116 KB Output is correct
14 Correct 339 ms 5880 KB Output is correct
15 Correct 1543 ms 14068 KB Output is correct
16 Correct 403 ms 18028 KB Output is correct
17 Correct 959 ms 14628 KB Output is correct
18 Correct 1929 ms 19692 KB Output is correct
19 Correct 1577 ms 19564 KB Output is correct
20 Correct 1503 ms 19136 KB Output is correct
21 Correct 1 ms 364 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 492 KB Output is correct
3 Correct 2 ms 492 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 2 ms 492 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 492 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 492 KB Output is correct
12 Correct 904 ms 36460 KB Output is correct
13 Correct 577 ms 36260 KB Output is correct
14 Correct 881 ms 33948 KB Output is correct
15 Correct 1064 ms 33604 KB Output is correct
16 Correct 570 ms 19856 KB Output is correct
17 Correct 1044 ms 33504 KB Output is correct
18 Correct 993 ms 33432 KB Output is correct
19 Correct 916 ms 17656 KB Output is correct
20 Correct 1343 ms 11000 KB Output is correct
21 Correct 338 ms 5868 KB Output is correct
22 Correct 1535 ms 13980 KB Output is correct
23 Correct 412 ms 18156 KB Output is correct
24 Correct 962 ms 14540 KB Output is correct
25 Correct 1870 ms 19596 KB Output is correct
26 Correct 1542 ms 19560 KB Output is correct
27 Correct 1472 ms 19052 KB Output is correct
28 Correct 518 ms 43244 KB Output is correct
29 Correct 1584 ms 45588 KB Output is correct
30 Correct 2606 ms 35616 KB Output is correct
31 Correct 2253 ms 28852 KB Output is correct
32 Correct 383 ms 10348 KB Output is correct
33 Correct 521 ms 10812 KB Output is correct
34 Correct 796 ms 39192 KB Output is correct
35 Correct 1111 ms 27116 KB Output is correct
36 Correct 2348 ms 43428 KB Output is correct
37 Correct 1806 ms 43712 KB Output is correct
38 Correct 1801 ms 42904 KB Output is correct
39 Correct 1463 ms 35712 KB Output is correct
40 Correct 1 ms 364 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 492 KB Output is correct
3 Correct 2 ms 492 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 2 ms 492 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 2 ms 492 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 492 KB Output is correct
12 Correct 860 ms 36588 KB Output is correct
13 Correct 580 ms 36228 KB Output is correct
14 Correct 889 ms 33900 KB Output is correct
15 Correct 1000 ms 33532 KB Output is correct
16 Correct 565 ms 19896 KB Output is correct
17 Correct 1008 ms 33516 KB Output is correct
18 Correct 995 ms 33376 KB Output is correct
19 Correct 922 ms 17684 KB Output is correct
20 Correct 1346 ms 11136 KB Output is correct
21 Correct 338 ms 5780 KB Output is correct
22 Correct 1504 ms 14124 KB Output is correct
23 Correct 407 ms 18156 KB Output is correct
24 Correct 979 ms 14716 KB Output is correct
25 Correct 1904 ms 19664 KB Output is correct
26 Correct 1553 ms 19564 KB Output is correct
27 Correct 1507 ms 19284 KB Output is correct
28 Correct 552 ms 43372 KB Output is correct
29 Correct 1556 ms 45548 KB Output is correct
30 Correct 2583 ms 35392 KB Output is correct
31 Correct 2317 ms 28648 KB Output is correct
32 Correct 378 ms 10320 KB Output is correct
33 Correct 515 ms 10988 KB Output is correct
34 Correct 788 ms 39404 KB Output is correct
35 Correct 1071 ms 27372 KB Output is correct
36 Correct 2293 ms 43628 KB Output is correct
37 Correct 1781 ms 43580 KB Output is correct
38 Correct 1765 ms 43052 KB Output is correct
39 Correct 675 ms 81260 KB Output is correct
40 Correct 2630 ms 82360 KB Output is correct
41 Correct 3800 ms 67180 KB Output is correct
42 Correct 3208 ms 52588 KB Output is correct
43 Correct 1086 ms 76908 KB Output is correct
44 Correct 468 ms 10732 KB Output is correct
45 Correct 1406 ms 35948 KB Output is correct
46 Correct 2973 ms 81004 KB Output is correct
47 Correct 3019 ms 81132 KB Output is correct
48 Correct 2924 ms 80708 KB Output is correct
49 Correct 1 ms 364 KB Output is correct