oj.uz

Submission #781133

# Submission time Handle Problem Language Result Execution time Memory
781133 2023-07-12T18:50:10 Z caganyanmaz Game (IOI13_game) C++17
63 / 100
 1160 ms 256000 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 424 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 212 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 403 ms 17976 KB Output is correct
5 Correct 266 ms 18384 KB Output is correct
6 Correct 336 ms 15688 KB Output is correct
7 Correct 370 ms 15684 KB Output is correct
8 Correct 256 ms 13680 KB Output is correct
9 Correct 353 ms 15684 KB Output is correct
10 Correct 394 ms 15196 KB Output is correct
11 Correct 1 ms 300 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 5 ms 472 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 424 KB Output is correct
7 Correct 1 ms 300 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 640 ms 22948 KB Output is correct
13 Correct 972 ms 11144 KB Output is correct
14 Correct 232 ms 5688 KB Output is correct
15 Correct 1144 ms 14244 KB Output is correct
16 Correct 159 ms 24512 KB Output is correct
17 Correct 573 ms 21432 KB Output is correct
18 Correct 966 ms 25312 KB Output is correct
19 Correct 778 ms 26112 KB Output is correct
20 Correct 723 ms 25420 KB Output is correct
21 Correct 1 ms 304 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 428 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 300 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 451 ms 18116 KB Output is correct
13 Correct 269 ms 18360 KB Output is correct
14 Correct 336 ms 15756 KB Output is correct
15 Correct 369 ms 15680 KB Output is correct
16 Correct 268 ms 13624 KB Output is correct
17 Correct 357 ms 15616 KB Output is correct
18 Correct 333 ms 15240 KB Output is correct
19 Correct 628 ms 23152 KB Output is correct
20 Correct 1029 ms 11192 KB Output is correct
21 Correct 233 ms 5592 KB Output is correct
22 Correct 1160 ms 14240 KB Output is correct
23 Correct 161 ms 24564 KB Output is correct
24 Correct 564 ms 21448 KB Output is correct
25 Correct 924 ms 25340 KB Output is correct
26 Correct 786 ms 26172 KB Output is correct
27 Correct 816 ms 25612 KB Output is correct
28 Runtime error 800 ms 256000 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 412 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 424 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 304 KB Output is correct
12 Correct 413 ms 17828 KB Output is correct
13 Correct 274 ms 18296 KB Output is correct
14 Correct 334 ms 15676 KB Output is correct
15 Correct 386 ms 15584 KB Output is correct
16 Correct 256 ms 13704 KB Output is correct
17 Correct 351 ms 15640 KB Output is correct
18 Correct 331 ms 15260 KB Output is correct
19 Correct 618 ms 23196 KB Output is correct
20 Correct 973 ms 11252 KB Output is correct
21 Correct 234 ms 5592 KB Output is correct
22 Correct 1137 ms 14256 KB Output is correct
23 Correct 159 ms 24512 KB Output is correct
24 Correct 555 ms 21280 KB Output is correct
25 Correct 922 ms 24716 KB Output is correct
26 Correct 767 ms 25568 KB Output is correct
27 Correct 719 ms 24828 KB Output is correct
28 Runtime error 834 ms 256000 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -