oj.uz

Submission #781130

# Submission time Handle Problem Language Result Execution time Memory
781130 2023-07-12T18:43:29 Z caganyanmaz Game (IOI13_game) C++17
63 / 100
 1585 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() : up(1, -1), down(1, -1), data(1, 0) {}
        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);
        }
};

std::vector<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[sts[x]].get(0, R, 0, 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.size();
                st.pb(SegTree1D());
        }
        st[sts[Q]].set(0, R, 0, 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 468 KB Output is correct
4 Correct 1 ms 300 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 296 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 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 212 KB Output is correct
4 Correct 453 ms 19140 KB Output is correct
5 Correct 270 ms 19000 KB Output is correct
6 Correct 358 ms 16620 KB Output is correct
7 Correct 380 ms 16340 KB Output is correct
8 Correct 265 ms 13984 KB Output is correct
9 Correct 375 ms 16460 KB Output is correct
10 Correct 345 ms 16032 KB Output is correct
11 Correct 1 ms 212 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 1 ms 468 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 296 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 304 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 631 ms 23288 KB Output is correct
13 Correct 988 ms 10608 KB Output is correct
14 Correct 234 ms 5656 KB Output is correct
15 Correct 1161 ms 13776 KB Output is correct
16 Correct 172 ms 23892 KB Output is correct
17 Correct 566 ms 21172 KB Output is correct
18 Correct 952 ms 25384 KB Output is correct
19 Correct 801 ms 25520 KB Output is correct
20 Correct 759 ms 24920 KB Output is correct
21 Correct 1 ms 340 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 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 468 KB Output is correct
7 Correct 1 ms 300 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 428 KB Output is correct
10 Correct 1 ms 296 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 412 ms 19104 KB Output is correct
13 Correct 267 ms 19020 KB Output is correct
14 Correct 350 ms 16724 KB Output is correct
15 Correct 391 ms 16248 KB Output is correct
16 Correct 261 ms 14004 KB Output is correct
17 Correct 377 ms 16472 KB Output is correct
18 Correct 354 ms 16152 KB Output is correct
19 Correct 612 ms 23232 KB Output is correct
20 Correct 981 ms 10684 KB Output is correct
21 Correct 233 ms 5704 KB Output is correct
22 Correct 1177 ms 13660 KB Output is correct
23 Correct 170 ms 23960 KB Output is correct
24 Correct 577 ms 21220 KB Output is correct
25 Correct 873 ms 25396 KB Output is correct
26 Correct 788 ms 25504 KB Output is correct
27 Correct 755 ms 24928 KB Output is correct
28 Correct 925 ms 256000 KB Output is correct
29 Runtime error 1562 ms 256000 KB Execution killed with signal 9
30 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 424 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 468 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 300 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 296 KB Output is correct
12 Correct 412 ms 19160 KB Output is correct
13 Correct 289 ms 19044 KB Output is correct
14 Correct 342 ms 16540 KB Output is correct
15 Correct 389 ms 16444 KB Output is correct
16 Correct 265 ms 14012 KB Output is correct
17 Correct 365 ms 16488 KB Output is correct
18 Correct 340 ms 16084 KB Output is correct
19 Correct 617 ms 23284 KB Output is correct
20 Correct 972 ms 10612 KB Output is correct
21 Correct 236 ms 5608 KB Output is correct
22 Correct 1223 ms 13708 KB Output is correct
23 Correct 173 ms 23900 KB Output is correct
24 Correct 585 ms 21220 KB Output is correct
25 Correct 969 ms 25344 KB Output is correct
26 Correct 910 ms 25588 KB Output is correct
27 Correct 855 ms 24944 KB Output is correct
28 Correct 858 ms 256000 KB Output is correct
29 Runtime error 1585 ms 256000 KB Execution killed with signal 9
30 Halted 0 ms 0 KB -