Submission #781133

#	Time	Username	Problem	Language	Result	Execution time	Memory
781133		caganyanmaz	Game (IOI13_game)	C++17	63 / 100	1160 ms	256000 KiB

game

#include <bits/stdc++.h>
#include "game.h"
#define pb push_back
//#define DEBUGGING

void __print(int i) { std::cerr << i; }
void __print(long long int i) { std::cerr << i; }
void __print(const char *c) { std::cerr << c; }

template<typename T>
void __print(T& t) { std::cerr <<"{";int f = 0; for (auto& i : t) { std::cerr << ((f++) ? ", ": ""); __print(i); } std::cerr << "}"; }
void _print() { std::cerr << "]\n"; }
template<typename T, typename... V>
void _print(T t, V... v) { __print(t); if (sizeof...(v)) std::cerr << ", "; _print(v...); }


#ifdef DEBUGGING
#define debug(x...) std::cerr << "[" << (#x) << "] = ["; _print(x)
#else
#define debug(x...)
#endif

long long gcd(long long X, long long Y) {
        long long tmp;
        while (X != Y && Y != 0) {
                tmp = X;
                X = Y;
                Y = tmp % Y;
        }
        return X;
}


struct SegTree1D
{
        std::vector<int> up, down;
        std::vector<long long> data;
        SegTree1D() {}
        void push(int u, int d, int index)
        {
                if (d - u == 1)
                        return;
                if (up[index] == -1)
                {
                        up[index] = data.size();
                        up.pb(-1);
                        down.pb(-1);
                        data.pb(0);
                }
                if (down[index] == -1)
                {
                        down[index] = data.size();
                        up.pb(-1);
                        down.pb(-1);
                        data.pb(0);
                }
        }
        void set(int u, int d, int index, int y, long long val)
        {
                debug(u, d, index, y, val);
                if (y >= d || u > y)
                        return;
                push(u, d, index);
                if (u + 1 == d)
                {
                        data[index] = val;
                        return;
                }
                int m = u+d>>1;
                set(u, m, up[index], y, val);
                set(m, d, down[index], y, val);
                data[index] = gcd(data[up[index]], data[down[index]]);
        }
        long long int get(int u, int d, int index, int uu, int dd)
        {
                if (uu >= d || u >= dd || index == -1)
                        return 0;
                if (dd >= d && u >= uu)
                        return data[index];
                int m = u+d>>1;
                long long ures = get(u, m, up[index], uu, dd);
                long long dres = get(m, d, down[index], uu, dd);
                return gcd(ures, dres);
        }
};

SegTree1D st;
std::map<int, int> sts;
int R, C;
struct SegTree2D
{
        std::vector<int> up, down, root;
        std::vector<int> left, right;
        std::vector<long long> data;
        SegTree2D() : up(1, -1), down(1, -1), root(1, -1) {}
        void push_x(int l, int r, int index)
        {
                if (r - l == 1)
                        return;
                if (left[index] == -1)
                {
                        left[index] = data.size();
                        left.pb(-1);
                        right.pb(-1);
                        data.pb(0);
                }
                if (right[index] == -1)
                {
                        right[index] = data.size();
                        left.pb(-1);
                        right.pb(-1);
                        data.pb(0);
                }
        }

        void push_y(int u, int d, int index)
        {
                if (up[index] == -1 && d - u > 1)
                {
                        up[index] = root.size();
                        up.pb(-1);
                        down.pb(-1);
                        root.pb(-1);
                }
                if (down[index] == -1 && d - u > 1)
                {
                        down[index] = root.size();
                        up.pb(-1);
                        down.pb(-1);
                        root.pb(-1);
                }
                if (root[index] == -1)
                {
                        root[index] = data.size();
                        left.pb(-1);
                        right.pb(-1);
                        data.pb(0);
                }
        }
        long long int query1d(int l, int r, int index, int ll, int rr)
        {
                if (index == -1 || ll >= r || l >= rr)
                        return 0;
                if (rr >= r && l >= ll)
                        return data[index];
                int m = l+r>>1;
                long long int lres = query1d(l, m, left[index], ll, rr);
                long long int rres = query1d(m, r, right[index], ll, rr);
                return gcd(lres, rres);
        }

        long long int query2d(int u, int d, int index, int uu, int dd, int ll, int rr)
        {
                if (index == -1 || uu >= d || u >= dd)
                        return 0;
                if (dd >= d && u >= uu)
                        return query1d(0, C, root[index], ll, rr);
                int m = u+d>>1;
                long long int ures = query2d(u, m, up[index], uu, dd, ll, rr);
                long long int dres = query2d(m, d, down[index], uu, dd, ll, rr);
                return gcd(ures, dres);
        }

        void update1d(int l, int r, int index, int x, long long int val)
        {
                if (x >= r || l > x)
                        return;
                push_x(l, r, index);
                if (l + 1 == r)
                {
                        data[index] = val;
                        return;
                }
                int m = l+r>>1;
                update1d(l, m, left[index], x, val);
                update1d(m, r, right[index], x, val);
                data[index] = gcd(data[left[index]], data[right[index]]);
        }

        void update2d(int u, int d, int index, int y, int x)
        {
                if (y >= d || u > y)
                        return;
                push_y(u, d, index);
                update1d(0, C, root[index], x, st.get(0, R, sts[x], u, d));
                debug(u, d, y, x, root[index], x, st[sts[x]].get(0, R, 0, u, d));
                if (u + 1 == d)
                        return;
                int m = u+d>>1;
                update2d(u, m, up[index], y, x);
                update2d(m, d, down[index], y, x);
        }
};


SegTree2D st2;
void init(int r, int c)
{
        R = r;
        C = c;
}

void update(int P, int Q, long long int K)
{
        if (sts.find(Q) == sts.end())
        {
                sts[Q] = st.data.size();
                st.data.pb(0);
                st.up.pb(-1);
                st.down.pb(-1);
        }
        st.set(0, R, sts[Q], P, K);
        st2.update2d(0, R, 0, P, Q);
}

long long int calculate(int P, int Q, int U, int V)
{
        return st2.query2d(0, R, 0, P, U+1, Q, V+1);
}

Compilation message (stderr)

game.cpp: In member function 'void SegTree1D::set(int, int, int, int, long long int)':
game.cpp:69:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   69 |                 int m = u+d>>1;
      |                         ~^~
game.cpp: In member function 'long long int SegTree1D::get(int, int, int, int, int)':
game.cpp:80:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   80 |                 int m = u+d>>1;
      |                         ~^~
game.cpp: In member function 'long long int SegTree2D::query1d(int, int, int, int, int)':
game.cpp:146:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  146 |                 int m = l+r>>1;
      |                         ~^~
game.cpp: In member function 'long long int SegTree2D::query2d(int, int, int, int, int, int, int)':
game.cpp:158:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  158 |                 int m = u+d>>1;
      |                         ~^~
game.cpp: In member function 'void SegTree2D::update1d(int, int, int, int, long long int)':
game.cpp:174:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  174 |                 int m = l+r>>1;
      |                         ~^~
game.cpp: In member function 'void SegTree2D::update2d(int, int, int, int, int)':
game.cpp:189:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  189 |                 int m = u+d>>1;
      |                         ~^~

• Subtask 1: 10 / 10
• Subtask 2: 27 / 27
• Subtask 3: 26 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20