Submission #489173

#	Time	Username	Problem	Language	Result	Execution time	Memory
489173		CYMario	Game (IOI13_game)	C++17	100 / 100	2087 ms	39816 KiB

game

#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 (stderr)

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 / 10
• Subtask 2: 27 / 27
• Subtask 3: 26 / 26
• Subtask 4: 17 / 17
• Subtask 5: 20 / 20