oj.uz

Submission #754263

# Submission time Handle Problem Language Result Execution time Memory
754263 2023-06-07T11:21:52 Z marvinthang Game (IOI13_game) C++17
100 / 100
 2087 ms 28056 KB 
/*************************************
*    author: marvinthang             *
*    created: 07.06.2023 15:56:53    *
*************************************/

#include "game.h"
#include <bits/stdc++.h>

using namespace std;

#define                  fi  first
#define                  se  second
#define                left  ___left
#define               right  ___right
#define                TIME  (1.0 * clock() / CLOCKS_PER_SEC)
#define             MASK(i)  (1LL << (i))
#define           BIT(x, i)  ((x) >> (i) & 1)
#define  __builtin_popcount  __builtin_popcountll
#define              ALL(v)  (v).begin(), (v).end()
#define           REP(i, n)  for (int i = 0, _n = (n); i < _n; ++i)
#define          REPD(i, n)  for (int i = (n); i--; )
#define        FOR(i, a, b)  for (int i = (a), _b = (b); i < _b; ++i) 
#define       FORD(i, b, a)  for (int i = (b), _a = (a); --i >= _a; ) 
#define       FORE(i, a, b)  for (int i = (a), _b = (b); i <= _b; ++i) 
#define      FORDE(i, b, a)  for (int i = (b), _a = (a); i >= _a; --i) 
#define        scan_op(...)  istream & operator >> (istream &in, __VA_ARGS__ &u)
#define       print_op(...)  ostream & operator << (ostream &out, const __VA_ARGS__ &u)
#ifdef LOCAL
    #include "debug.h"
#else
    #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
    #define DB(...) 23
    #define db(...) 23
    #define debug(...) 23
#endif

template <class U, class V> scan_op(pair <U, V>)  { return in >> u.first >> u.second; }
template <class T> scan_op(vector <T>)  { for (size_t i = 0; i < u.size(); ++i) in >> u[i]; return in; }
template <class U, class V> print_op(pair <U, V>)  { return out << '(' << u.first << ", " << u.second << ')'; }
template <size_t i, class T> ostream & print_tuple_utils(ostream &out, const T &tup) { if constexpr(i == tuple_size<T>::value) return out << ")";  else return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup); }
template <class ...U> print_op(tuple<U...>) { return print_tuple_utils<0, tuple<U...>>(out, u); }
template <class Con, class = decltype(begin(declval<Con>()))> typename enable_if <!is_same<Con, string>::value, ostream&>::type operator << (ostream &out, const Con &con) { out << '{'; for (__typeof(con.begin()) it = con.begin(); it != con.end(); ++it) out << (it == con.begin() ? "" : ", ") << *it; return out << '}'; }

// end of template

static char buf[250 << 20];
void* operator new(size_t s) {
    static size_t i = sizeof buf;
    assert(s < i);
    return (void*)&buf[i -= s];
}
void operator delete(void*) {}

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

struct Node {
    int l, r;
    long long val;
    Node *left, *right;
    Node(int _l, int _r, long long _v = 0, Node *_left = nullptr, Node *_right = nullptr) {
        l = _l; r = _r;
        val = _v;
        left = _left; right = _right;
    }
    void update(int p, long long v) {
        if (r - l == 1) {
            val = v;
            return;
        }
        int m = l + r >> 1;
        Node *&child = p < m ? left : right;
        if (child == nullptr) child = new Node(p, p + 1);
        else if (child->r <= p || child->l > p) {
            int x = l, y = r;
            int a = min(child->l, p);
            int b = max(child->r, p + 1);
            while (true) {
                int m = x + y >> 1;
                if (a >= m) x = m;
                else if (b <= m) y = m;
                else break;
            }
            m = x + y >> 1;
            Node *nxt = new Node(x, y);
            if (p < m) nxt->right = child;
            else nxt->left = child;
            child = nxt;
        }
        child->update(p, v);
        val = gcd2(left == nullptr ? 0 : left->val, right == nullptr ? 0 : right->val);
    }
    long long get(int u, int v) {
        if (u <= l && r <= v) return val;
        int m = l + r >> 1;
        if (v <= m) return left == nullptr ? 0 : left->get(u, v);
        if (m <= u) return right == nullptr ? 0 : right->get(u, v);
        return gcd2(left == nullptr ? 0 : left->get(u, v), right == nullptr ? 0 : right->get(u, v));
    }
};

Node *copy(Node *cur) {
    return new Node(cur->l, cur->r, cur->val, cur->left == nullptr ? nullptr : copy(cur->left), cur->right == nullptr ? nullptr : copy(cur->right));
}

struct Node2D {
    int l, r;
    Node *val;
    Node2D *left, *right;
    Node2D(int _l, int _r, int _n) {
        l = _l; r = _r;
        val = new Node(0, _n);
        left = right = nullptr;
    }
    void update(int p, int k, long long v) {
        if (r - l == 1) {
            val->update(k, v);
            return;
        }
        int m = l + r >> 1;
        Node2D *&child = p < m ? left : right;
        if (child == nullptr) child = new Node2D(p, p + 1, val->r);
        else if (child->r <= p || child->l > p) {
            int x = l, y = r;
            int a = min(child->l, p);
            int b = max(child->r, p + 1);
            while (true) {
                int m = x + y >> 1;
                if (a >= m) x = m;
                else if (b <= m) y = m;
                else break;
            }
            m = x + y >> 1;
            Node2D *nxt = new Node2D(x, y, val->r);
            if (p < m) nxt->right = child;
            else nxt->left = child;
            nxt->val = copy(child->val);
            child = nxt;
        }
        child->update(p, k, v);
        val->update(k, gcd2(left == nullptr ? 0 : left->val->get(k, k + 1), right == nullptr ? 0 : right->val->get(k, k + 1)));
    }
    long long get(int u, int v, int x, int y) {
        if (u <= l && r <= v) return val->get(x, y);
        int m = l + r >> 1;
        if (v <= m) return left == nullptr ? 0 : left->get(u, v, x, y);
        if (m <= u) return right == nullptr ? 0 : right->get(u, v, x, y);
        return gcd2(left == nullptr ? 0 : left->get(u, v, x, y), right == nullptr ? 0 : right->get(u, v, x, y));
    }
} *root;

void init(int R, int C) {
    root = new Node2D(0, R, 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->get(P, U + 1, Q, V + 1);
}

#ifdef LOCAL
#include <stdio.h>
#include <stdlib.h>
#include "game.h"

#define fail(s, x...) do { \
        fprintf(stderr, s "\n", ## x); \
        exit(1); \
    } while(0)

#define MAX_SIZE 1000000000
#define MAX_N 272000

int main() {
    freopen("game.out", "w", stdout);
    int R, C, N;
    int P, Q, U, V;
    long long K;
    int i, type;
    int res;

    FILE *f = fopen("game.in", "r");
    if (!f)
        fail("Failed to open input file.");

    res = fscanf(f, "%d", &R);
    res = fscanf(f, "%d", &C);
    res = fscanf(f, "%d", &N);

    init(R, C);

    for (i = 0; i < N; i++) {
        res = fscanf(f, "%d", &type);
        if (type == 1) {
            res = fscanf(f, "%d%d%lld", &P, &Q, &K);
            update(P, Q, K);
        } else if (type == 2) {
            res = fscanf(f, "%d%d%d%d", &P, &Q, &U, &V);
            printf("%lld\n", calculate(P, Q, U, V));
        } else
            fail("Invalid action type in input file.");
    }
    fclose(f);
    cerr << "end game\n";
    return 0;
}
#endif

Compilation message

game.cpp: In member function 'void Node::update(int, long long int)':
game.cpp:78:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   78 |         int m = l + r >> 1;
      |                 ~~^~~
game.cpp:86:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   86 |                 int m = x + y >> 1;
      |                         ~~^~~
game.cpp:91:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   91 |             m = x + y >> 1;
      |                 ~~^~~
game.cpp: In member function 'long long int Node::get(int, int)':
game.cpp:102:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  102 |         int m = l + r >> 1;
      |                 ~~^~~
game.cpp: In member function 'void Node2D::update(int, int, long long int)':
game.cpp:127:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  127 |         int m = l + r >> 1;
      |                 ~~^~~
game.cpp:135:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  135 |                 int m = x + y >> 1;
      |                         ~~^~~
game.cpp:140:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  140 |             m = x + y >> 1;
      |                 ~~^~~
game.cpp: In member function 'long long int Node2D::get(int, int, int, int)':
game.cpp:152:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  152 |         int m = l + r >> 1;
      |                 ~~^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 340 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 308 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 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 1 ms 212 KB Output is correct
2 Correct 1 ms 308 KB Output is correct
3 Correct 1 ms 304 KB Output is correct
4 Correct 400 ms 10864 KB Output is correct
5 Correct 263 ms 10444 KB Output is correct
6 Correct 356 ms 7848 KB Output is correct
7 Correct 410 ms 7668 KB Output is correct
8 Correct 251 ms 6568 KB Output is correct
9 Correct 414 ms 7720 KB Output is correct
10 Correct 342 ms 7464 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 340 KB Output is correct
3 Correct 1 ms 340 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 340 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 340 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 640 ms 12584 KB Output is correct
13 Correct 1114 ms 6852 KB Output is correct
14 Correct 204 ms 4692 KB Output is correct
15 Correct 1341 ms 8192 KB Output is correct
16 Correct 165 ms 10416 KB Output is correct
17 Correct 505 ms 8800 KB Output is correct
18 Correct 872 ms 11920 KB Output is correct
19 Correct 773 ms 12132 KB Output is correct
20 Correct 734 ms 11392 KB Output is correct
21 Correct 1 ms 212 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 340 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 340 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 340 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 374 ms 10620 KB Output is correct
13 Correct 318 ms 10380 KB Output is correct
14 Correct 385 ms 7852 KB Output is correct
15 Correct 386 ms 7424 KB Output is correct
16 Correct 260 ms 6496 KB Output is correct
17 Correct 390 ms 7568 KB Output is correct
18 Correct 323 ms 7380 KB Output is correct
19 Correct 603 ms 12168 KB Output is correct
20 Correct 1138 ms 6856 KB Output is correct
21 Correct 199 ms 4736 KB Output is correct
22 Correct 1243 ms 8076 KB Output is correct
23 Correct 171 ms 10188 KB Output is correct
24 Correct 525 ms 8652 KB Output is correct
25 Correct 932 ms 11668 KB Output is correct
26 Correct 747 ms 11804 KB Output is correct
27 Correct 686 ms 11204 KB Output is correct
28 Correct 325 ms 17496 KB Output is correct
29 Correct 857 ms 19960 KB Output is correct
30 Correct 1659 ms 15032 KB Output is correct
31 Correct 1555 ms 13076 KB Output is correct
32 Correct 204 ms 6932 KB Output is correct
33 Correct 343 ms 7072 KB Output is correct
34 Correct 198 ms 16544 KB Output is correct
35 Correct 579 ms 12288 KB Output is correct
36 Correct 1221 ms 17288 KB Output is correct
37 Correct 1026 ms 17488 KB Output is correct
38 Correct 974 ms 16844 KB Output is correct
39 Correct 766 ms 14340 KB Output is correct
40 Correct 0 ms 212 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 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 340 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 340 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 358 ms 10584 KB Output is correct
13 Correct 305 ms 10460 KB Output is correct
14 Correct 322 ms 7884 KB Output is correct
15 Correct 397 ms 7588 KB Output is correct
16 Correct 266 ms 6792 KB Output is correct
17 Correct 345 ms 7680 KB Output is correct
18 Correct 386 ms 7316 KB Output is correct
19 Correct 669 ms 12152 KB Output is correct
20 Correct 1108 ms 6312 KB Output is correct
21 Correct 190 ms 4172 KB Output is correct
22 Correct 1242 ms 7236 KB Output is correct
23 Correct 173 ms 9420 KB Output is correct
24 Correct 528 ms 7836 KB Output is correct
25 Correct 819 ms 11044 KB Output is correct
26 Correct 722 ms 10964 KB Output is correct
27 Correct 738 ms 10316 KB Output is correct
28 Correct 355 ms 13784 KB Output is correct
29 Correct 798 ms 17084 KB Output is correct
30 Correct 1616 ms 10704 KB Output is correct
31 Correct 1482 ms 8344 KB Output is correct
32 Correct 205 ms 3552 KB Output is correct
33 Correct 285 ms 3508 KB Output is correct
34 Correct 195 ms 12180 KB Output is correct
35 Correct 559 ms 8620 KB Output is correct
36 Correct 1138 ms 13832 KB Output is correct
37 Correct 827 ms 13924 KB Output is correct
38 Correct 801 ms 13304 KB Output is correct
39 Correct 393 ms 27084 KB Output is correct
40 Correct 1195 ms 28056 KB Output is correct
41 Correct 2087 ms 20948 KB Output is correct
42 Correct 1959 ms 15644 KB Output is correct
43 Correct 301 ms 25804 KB Output is correct
44 Correct 236 ms 2448 KB Output is correct
45 Correct 670 ms 10300 KB Output is correct
46 Correct 1602 ms 26040 KB Output is correct
47 Correct 1748 ms 25420 KB Output is correct
48 Correct 1489 ms 24856 KB Output is correct
49 Correct 0 ms 212 KB Output is correct