oj.uz

Submission #754241

# Submission time Handle Problem Language Result Execution time Memory
754241 2023-06-07T10:12:14 Z marvinthang Game (IOI13_game) C++17
100 / 100
 2566 ms 66836 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) {
        l = _l; r = _r;
        val = 0;
        left = right = nullptr;
    }
    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 (l >= v || r <= u) return 0;
        if (u <= l && r <= v) return val;
        return gcd2(left == nullptr ? 0 : left->get(u, v), right == nullptr ? 0 : right->get(u, v));
    }
};

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 x, int y, long long v) {
        if (r - l == 1) {
            val->update(y, v);
            return;
        }
        int m = l + r >> 1;
        if (x < m) {
            if (left == nullptr) left = new Node2D(l, m, val->r);
            left->update(x, y, v);
        } else {
            if (right == nullptr) right = new Node2D(m, r, val->r);
            right->update(x, y, v);
        }
        val->update(y, gcd2(left == nullptr ? 0 : left->val->get(y, y + 1), right == nullptr ? 0 : right->val->get(y, y + 1)));
    }
    long long get(int u, int v, int x, int y) {
        if (l >= v || r <= u) return 0;
        if (u <= l && r <= v) return val->get(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 'void Node2D::update(int, int, long long int)':
game.cpp:121:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  121 |         int m = l + r >> 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 340 KB Output is correct
3 Correct 1 ms 308 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 308 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 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 410 ms 7844 KB Output is correct
5 Correct 283 ms 8224 KB Output is correct
6 Correct 402 ms 5000 KB Output is correct
7 Correct 414 ms 4604 KB Output is correct
8 Correct 293 ms 4076 KB Output is correct
9 Correct 417 ms 4812 KB Output is correct
10 Correct 402 ms 4408 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 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 308 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 340 KB Output is correct
12 Correct 646 ms 10364 KB Output is correct
13 Correct 1201 ms 4552 KB Output is correct
14 Correct 214 ms 1724 KB Output is correct
15 Correct 1328 ms 5336 KB Output is correct
16 Correct 186 ms 8016 KB Output is correct
17 Correct 582 ms 5596 KB Output is correct
18 Correct 993 ms 8212 KB Output is correct
19 Correct 831 ms 8296 KB Output is correct
20 Correct 874 ms 7852 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 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 308 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 410 ms 7956 KB Output is correct
13 Correct 287 ms 8148 KB Output is correct
14 Correct 412 ms 4940 KB Output is correct
15 Correct 421 ms 4720 KB Output is correct
16 Correct 287 ms 4032 KB Output is correct
17 Correct 406 ms 4868 KB Output is correct
18 Correct 387 ms 4324 KB Output is correct
19 Correct 667 ms 10048 KB Output is correct
20 Correct 1179 ms 4636 KB Output is correct
21 Correct 212 ms 1700 KB Output is correct
22 Correct 1374 ms 5420 KB Output is correct
23 Correct 185 ms 7828 KB Output is correct
24 Correct 627 ms 5588 KB Output is correct
25 Correct 1060 ms 8336 KB Output is correct
26 Correct 802 ms 8360 KB Output is correct
27 Correct 873 ms 7948 KB Output is correct
28 Correct 382 ms 29000 KB Output is correct
29 Correct 1016 ms 38620 KB Output is correct
30 Correct 1847 ms 28076 KB Output is correct
31 Correct 1682 ms 23284 KB Output is correct
32 Correct 274 ms 10116 KB Output is correct
33 Correct 381 ms 10420 KB Output is correct
34 Correct 224 ms 32300 KB Output is correct
35 Correct 749 ms 23720 KB Output is correct
36 Correct 1702 ms 36620 KB Output is correct
37 Correct 1127 ms 36616 KB Output is correct
38 Correct 1257 ms 36024 KB Output is correct
39 Correct 1002 ms 30640 KB Output is correct
40 Correct 1 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 1 ms 312 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 304 KB Output is correct
12 Correct 405 ms 7768 KB Output is correct
13 Correct 291 ms 8084 KB Output is correct
14 Correct 367 ms 4748 KB Output is correct
15 Correct 435 ms 4692 KB Output is correct
16 Correct 286 ms 3916 KB Output is correct
17 Correct 406 ms 4732 KB Output is correct
18 Correct 373 ms 4276 KB Output is correct
19 Correct 673 ms 9840 KB Output is correct
20 Correct 1220 ms 4416 KB Output is correct
21 Correct 219 ms 1740 KB Output is correct
22 Correct 1315 ms 5200 KB Output is correct
23 Correct 183 ms 7700 KB Output is correct
24 Correct 573 ms 5416 KB Output is correct
25 Correct 1132 ms 8336 KB Output is correct
26 Correct 879 ms 8224 KB Output is correct
27 Correct 790 ms 7672 KB Output is correct
28 Correct 385 ms 28876 KB Output is correct
29 Correct 1016 ms 38640 KB Output is correct
30 Correct 1869 ms 28032 KB Output is correct
31 Correct 1701 ms 23280 KB Output is correct
32 Correct 287 ms 10156 KB Output is correct
33 Correct 387 ms 10584 KB Output is correct
34 Correct 242 ms 32380 KB Output is correct
35 Correct 834 ms 23700 KB Output is correct
36 Correct 1872 ms 36524 KB Output is correct
37 Correct 1358 ms 36684 KB Output is correct
38 Correct 1358 ms 36016 KB Output is correct
39 Correct 507 ms 65648 KB Output is correct
40 Correct 1751 ms 66836 KB Output is correct
41 Correct 2566 ms 51688 KB Output is correct
42 Correct 2413 ms 40876 KB Output is correct
43 Correct 376 ms 61576 KB Output is correct
44 Correct 331 ms 10572 KB Output is correct
45 Correct 1010 ms 30576 KB Output is correct
46 Correct 2278 ms 65768 KB Output is correct
47 Correct 2083 ms 65880 KB Output is correct
48 Correct 2184 ms 65396 KB Output is correct
49 Correct 1 ms 308 KB Output is correct