oj.uz

Submission #489173

# Submission time Handle Problem Language Result Execution time Memory
489173 2021-11-21T12:03:17 Z CYMario Game (IOI13_game) C++17
100 / 100
 2087 ms 39816 KB 
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <utility>
#include "game.h"
typedef long long ll;
const int N = 300010;
using namespace std;
typedef pair<int, int> ii;
//from errorgorn
ll rd()
{
    ll k = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9')
    {
        k = (k << 1) + (k << 3) + (c ^ 48);
        c = getchar();
    }
    return f > 0 ? k : -k;
}
void wr(ll x)
{
    if (x < 0)
        putchar('-'), x = -x;
    if (x > 9)
        wr(x / 10);
    putchar(x % 10 + '0');
}
 
inline long long func(long long X, long long Y)
{
    
    long long tmp;
    while (X != Y && Y != 0)
    {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
    
   //return X + Y;
}
/*
int __builtin_clz(int x) {
    if (!x)return 32;
    int ret = 0;
    //if (!(x & 0xFFFFFFFF00000000ll)) ret += 32, x <<= 32;
    if (!(x & 0xFFFF0000)) ret += 16, x <<= 16;
    if (!(x & 0xFF000000)) ret += 8, x <<= 8;
    if (!(x & 0xF0000000)) ret += 4, x <<= 4;
    if (!(x & 0xC0000000)) ret += 2, x <<= 2;
    if (!(x & 0x80000000)) ret += 1, x <<= 1;
    return ret;
}
*/
ii lca(int l, int r, int pos)
{ // find lca of 2 nodes
    if (pos < l)
    {
        int p = 32 - __builtin_clz(pos ^ l);
        int lp = (pos >> p) << p;
        return ii(lp, lp + (1 << p) - 1);
    }
    if (r < pos)
    {
        int p = 32 - __builtin_clz(r ^ pos);
        int lp = (l >> p) << p;
        return ii(lp, lp + (1 << p) - 1);
    }
    return ii(pos, 0);
}
 
struct node
{
    int s, e, m;
    long long val = 0;
    node *l = nullptr, *r = nullptr;
 
    node(int _s, int _e)
    {
        s = _s, e = _e, m = (s + e) >> 1;
    }
 
    bool inside(int i)
    {
        return s <= i && i <= e;
    }
 
    void update(int i, long long j)
    {
        if (s == e)
            val = j;
        else
        {
            if (i <= m)
            {
                if (l == nullptr)
                    l = new node(i, i);
                else if (!l->inside(i))
                {
                    node *temp = l;
                    ii child = lca(l->s, l->e, i);
                    l = new node(child.first, child.second);
                    if (temp->e <= l->m)
                        l->l = temp;
                    else
                        l->r = temp;
                }
                l->update(i, j);
            }
            else
            {
                if (r == nullptr)
                    r = new node(i, i);
                else if (!r->inside(i))
                {
                    node *temp = r;
                    ii child = lca(r->s, r->e, i);
                    r = new node(child.first, child.second);
                    if (temp->e <= r->m)
                        r->l = temp;
                    else
                        r->r = temp;
                }
                r->update(i, j);
            }
            val = func((l == nullptr) ? 0 : l->val, (r == nullptr) ? 0 : r->val);
        }
    }
 
    long long query(int i, int j)
    {
        if (i <= s && e <= j)
            return val;
        else if (j <= m)
            return (l == nullptr) ? 0 : l->query(i, j);
        else if (m < i)
            return (r == nullptr) ? 0 : r->query(i, j);
        else
            return func((l == nullptr) ? 0 : l->query(i, m), (r == nullptr) ? 0 : r->query(m + 1, j));
    }
 
    node *clone()
    {
        node *res = new node(s, e);
        res->val = val;
        res->l = (l == nullptr) ? nullptr : l->clone();
        res->r = (r == nullptr) ? nullptr : r->clone();
        return res;
    }
};
 
struct node2d
{
    int s, e, m;
    node *val = new node(0, (1 << 30) - 1);
    node2d *l = nullptr, *r = nullptr;
 
    node2d(int _s, int _e)
    {
        s = _s, e = _e, m = s + e >> 1;
    }
 
    bool inside(int i)
    {
        return s <= i && i <= e;
    }
 
    void update(int i, int j, long long k)
    {
        if (s == e)
            val->update(j, k);
        else
        {
            if (i <= m)
            {
                if (l == nullptr)
                    l = new node2d(i, i);
                else if (!l->inside(i))
                {
                    node2d *temp = l;
                    ii child = lca(l->s, l->e, i);
                    l = new node2d(child.first, child.second);
                    if (temp->e <= l->m)
                        l->l = temp;
                    else
                        l->r = temp;
                    l->val = temp->val->clone();
                }
                l->update(i, j, k);
            }
            else
            {
                if (r == nullptr)
                    r = new node2d(i, i);
                else if (!r->inside(i))
                {
                    node2d *temp = r;
                    ii child = lca(r->s, r->e, i);
                    r = new node2d(child.first, child.second);
                    if (temp->e <= r->m)
                        r->l = temp;
                    else
                        r->r = temp;
                    r->val = temp->val->clone();
                }
                r->update(i, j, k);
            }
            val->update(j, func((l == nullptr) ? 0 : l->val->query(j, j), (r == nullptr) ? 0 : r->val->query(j, j)));
        }
    }
 
    long long query(int i, int j, int i2, int j2)
    {
        if (i <= s && e <= j)
            return val->query(i2, j2);
        else if (j <= m)
            return (l == nullptr) ? 0 : l->query(i, j, i2, j2);
        else if (m < i)
            return (r == nullptr) ? 0 : r->query(i, j, i2, j2);
        else
            return func((l == nullptr) ? 0 : l->query(i, m, i2, j2), (r == nullptr) ? 0 : r->query(m + 1, j, i2, j2));
    }
} *root = new node2d(0, (1 << 30) - 1);
 
void init(int R, int C)
{
}
 
void update(int P, int Q, long long K)
{
    root->update(P, Q, K);
}
 
long long calculate(int P, int Q, int U, int V)
{
    return root->query(P, U, Q, V);
}
 
void test_interaction()
{
    int n = rd(), m = rd();
    init(n, m);
    int q = rd();
    while(q--)
    {
        int op = rd();
        //op 1 : update single point
        if (op == 1)
        {
            int x = rd(), y = rd(); ll w = rd();
            update(x, y, w);
        }
        //op 2 : 2D gcd query
        else 
        {
            int xl = rd(), yl = rd(), xr = rd(), yr = rd();
            wr(calculate(xl, yl, xr, yr)), putchar('\n');
        }
    }
}

Compilation message

game.cpp: In constructor 'node2d::node2d(int, int)':
game.cpp:169:31: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  169 |         s = _s, e = _e, m = s + e >> 1;
      |                             ~~^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 276 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 0 ms 280 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 0 ms 204 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 340 ms 11912 KB Output is correct
5 Correct 235 ms 12232 KB Output is correct
6 Correct 343 ms 8812 KB Output is correct
7 Correct 392 ms 8728 KB Output is correct
8 Correct 256 ms 6752 KB Output is correct
9 Correct 370 ms 8656 KB Output is correct
10 Correct 354 ms 8196 KB Output is correct
11 Correct 0 ms 204 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 648 ms 14068 KB Output is correct
13 Correct 1089 ms 7476 KB Output is correct
14 Correct 180 ms 3284 KB Output is correct
15 Correct 1223 ms 8916 KB Output is correct
16 Correct 241 ms 12844 KB Output is correct
17 Correct 511 ms 8912 KB Output is correct
18 Correct 1030 ms 13184 KB Output is correct
19 Correct 809 ms 13288 KB Output is correct
20 Correct 754 ms 12684 KB Output is correct
21 Correct 0 ms 204 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 276 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 216 KB Output is correct
9 Correct 0 ms 332 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 341 ms 11896 KB Output is correct
13 Correct 242 ms 12460 KB Output is correct
14 Correct 337 ms 8772 KB Output is correct
15 Correct 390 ms 8552 KB Output is correct
16 Correct 253 ms 6704 KB Output is correct
17 Correct 374 ms 8668 KB Output is correct
18 Correct 344 ms 8252 KB Output is correct
19 Correct 642 ms 14120 KB Output is correct
20 Correct 1095 ms 7600 KB Output is correct
21 Correct 186 ms 3272 KB Output is correct
22 Correct 1201 ms 8688 KB Output is correct
23 Correct 243 ms 12852 KB Output is correct
24 Correct 507 ms 8972 KB Output is correct
25 Correct 1084 ms 13060 KB Output is correct
26 Correct 800 ms 13256 KB Output is correct
27 Correct 765 ms 12776 KB Output is correct
28 Correct 394 ms 18516 KB Output is correct
29 Correct 919 ms 21128 KB Output is correct
30 Correct 1563 ms 14672 KB Output is correct
31 Correct 1426 ms 11968 KB Output is correct
32 Correct 201 ms 3192 KB Output is correct
33 Correct 279 ms 3448 KB Output is correct
34 Correct 393 ms 18272 KB Output is correct
35 Correct 575 ms 10708 KB Output is correct
36 Correct 1354 ms 18516 KB Output is correct
37 Correct 960 ms 18868 KB Output is correct
38 Correct 954 ms 18068 KB Output is correct
39 Correct 793 ms 14812 KB Output is correct
40 Correct 0 ms 204 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 280 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 264 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 1 ms 284 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 338 ms 11876 KB Output is correct
13 Correct 238 ms 12116 KB Output is correct
14 Correct 334 ms 8804 KB Output is correct
15 Correct 395 ms 8572 KB Output is correct
16 Correct 249 ms 6732 KB Output is correct
17 Correct 368 ms 8584 KB Output is correct
18 Correct 356 ms 8216 KB Output is correct
19 Correct 643 ms 14168 KB Output is correct
20 Correct 1081 ms 7576 KB Output is correct
21 Correct 194 ms 3208 KB Output is correct
22 Correct 1206 ms 8656 KB Output is correct
23 Correct 236 ms 12800 KB Output is correct
24 Correct 510 ms 9028 KB Output is correct
25 Correct 1038 ms 13104 KB Output is correct
26 Correct 851 ms 13280 KB Output is correct
27 Correct 778 ms 12528 KB Output is correct
28 Correct 345 ms 18204 KB Output is correct
29 Correct 894 ms 20952 KB Output is correct
30 Correct 1533 ms 14568 KB Output is correct
31 Correct 1430 ms 11724 KB Output is correct
32 Correct 196 ms 3052 KB Output is correct
33 Correct 279 ms 3268 KB Output is correct
34 Correct 389 ms 17976 KB Output is correct
35 Correct 607 ms 10508 KB Output is correct
36 Correct 1303 ms 18240 KB Output is correct
37 Correct 964 ms 18396 KB Output is correct
38 Correct 959 ms 17584 KB Output is correct
39 Correct 496 ms 38420 KB Output is correct
40 Correct 1499 ms 39816 KB Output is correct
41 Correct 2087 ms 29812 KB Output is correct
42 Correct 1907 ms 22388 KB Output is correct
43 Correct 589 ms 37828 KB Output is correct
44 Correct 232 ms 2680 KB Output is correct
45 Correct 771 ms 14384 KB Output is correct
46 Correct 1820 ms 38012 KB Output is correct
47 Correct 1840 ms 38088 KB Output is correct
48 Correct 1744 ms 37772 KB Output is correct
49 Correct 0 ms 204 KB Output is correct