oj.uz

Submission #1087630

# Submission time Handle Problem Language Result Execution time Memory
1087630 2024-09-13T03:23:00 Z Zero_OP Game (IOI13_game) C++14
63 / 100
 1097 ms 256000 KB 
#ifndef LOCAL
#include "game.h"
#endif //LOCAL

#include <bits/stdc++.h>

using namespace std;

#define sz(v) (int)v.size()
#define all(v) begin(v), end(v)
#define compact(v) v.erase(unique(all(v)), end(v))
#define dbg(x) "[" #x " = " << (x) << "]"

template<typename T>
    bool minimize(T& a, const T& b){
        if(a > b) return a = b, true;
        return false;
    }

template<typename T>
    bool maximize(T& a, const T& b){
        if(a < b) return a = b, true;
        return false;
    }

using ll = long long;
using ld = long double;
using vi = vector<int>;
using vl = vector<ll>;


long long gcd2(long long X, long long Y) {
//    cout << X << ' ' << Y << '\n';
    long long tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}

int N, M;

struct node1D{
    node1D *left, *right;
    long long g;

    node1D(ll g = 0) : g(g), left(nullptr), right(nullptr) {}
    node1D(node1D* left, node1D *right) : left(left), right(right), g(gcd2(left -> g, right -> g)) {}
};

void define1D(node1D*& cur){
    if(cur == nullptr) cur = new node1D();
}

ll eval(node1D* cur){
    if(cur == nullptr) return 0;
    return cur -> g;
}

struct node2D{
    node2D *left, *right;
    node1D *tree;

    node2D() : left(nullptr), right(nullptr), tree(nullptr) {}
    node2D(node2D* left, node2D* right) : left(left), right(right), tree(nullptr) {}
} *tree2D;

void define2D(node2D*& cur){
    if(cur == nullptr) cur = new node2D();
}

void update_y(int lx, int rx, node1D* tl, node1D* tr, node1D*& idy, int ly, int ry, int y, long long k){
    define1D(idy);

    if(ly == ry){
        if(lx == rx) (idy -> g) = k;
        else (idy -> g) = gcd2(eval(tl), eval(tr));
    } else{
        int mid = (ly + ry) >> 1;
        if(y <= mid) update_y(lx, rx, (tl == nullptr ? nullptr : tl -> left), (tr == nullptr ? nullptr : tr -> left), idy -> left, ly, mid, y, k);
        else update_y(lx, rx, (tl == nullptr ? nullptr : tl -> right), (tr == nullptr ? nullptr : tr -> right), idy -> right, mid + 1, ry, y, k);

        (idy -> g) = gcd2(eval(idy -> left), eval(idy -> right));
    }
}

void update_x(node2D* &idx, int lx, int rx, int x, int y, long long k){
    define2D(idx);

    if(lx < rx){
        int mid = lx + rx >> 1;
        if(x <= mid) update_x(idx -> left, lx, mid, x, y, k);
        else update_x(idx -> right, mid + 1, rx, x, y, k);
    }

    update_y(lx, rx, (idx -> left == nullptr ? nullptr : idx -> left -> tree),
              (idx -> right == nullptr ? nullptr : idx -> right -> tree), idx -> tree, 0, M - 1, y, k);
}

long long query_y(node1D* idy, int ly, int ry, int u, int v){
    if((u <= ly && ry <= v) || idy == nullptr) return eval(idy);
    int mid = ly + ry >> 1;
    long long g = 0;
    if(u <= mid) g = gcd2(g, query_y(idy -> left, ly, mid, u, v));
    if(mid < v) g = gcd2(g, query_y(idy -> right, mid + 1, ry, u, v));
    return g;
}

long long query_x(node2D* idx, int lx, int rx, int u, int v, int p, int q){
    if((u <= lx && rx <= v) || idx == nullptr) return query_y((idx == nullptr ? nullptr : idx -> tree), 0, M - 1, p, q);
    int mid = lx + rx >> 1;
    long long g = 0;
    if(u <= mid) g = gcd2(g, query_x(idx -> left, lx, mid, u, v, p, q));
    if(mid < v) g = gcd2(g, query_x(idx -> right, mid + 1, rx, u, v, p, q));
    return g;
}

void init(int R, int C) {
    N = R;
    M = C;
}

void update(int P, int Q, long long K) {
    update_x(tree2D, 0, N - 1, P, Q, K);
}

long long calculate(int P, int Q, int U, int V) {
    return query_x(tree2D, 0, N - 1, P, U, Q, V);
}


#ifdef LOCAL
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

    #define filename "task"
    if(fopen(filename".inp", "r")){
        freopen(filename".inp", "r", stdin);
        freopen(filename".out", "w", stdout);
    }

    int Q;
    cin >> N >> M >> Q;

    init(N, M);

    while(Q--){
        int type;
        cin >> type;
        if(type == 1){
            int x, y; long long z;
            cin >> x >> y >> z;
            update(x, y, z);
        } else{
            int p, q, u, v;
            cin >> p >> q >> u >> v;
//            cout << calculate(p, q, u, v) << '\n';
        }
    }


    return 0;
}
#endif // LOCAL

Compilation message

game.cpp: In constructor 'node1D::node1D(ll)':
game.cpp:47:15: warning: 'node1D::g' will be initialized after [-Wreorder]
   47 |     long long g;
      |               ^
game.cpp:46:13: warning:   'node1D* node1D::left' [-Wreorder]
   46 |     node1D *left, *right;
      |             ^~~~
game.cpp:49:5: warning:   when initialized here [-Wreorder]
   49 |     node1D(ll g = 0) : g(g), left(nullptr), right(nullptr) {}
      |     ^~~~~~
game.cpp: In function 'void update_x(node2D*&, int, int, int, int, long long int)':
game.cpp:93:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   93 |         int mid = lx + rx >> 1;
      |                   ~~~^~~~
game.cpp: In function 'long long int query_y(node1D*, int, int, int, int)':
game.cpp:104:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  104 |     int mid = ly + ry >> 1;
      |               ~~~^~~~
game.cpp: In function 'long long int query_x(node2D*, int, int, int, int, int, int)':
game.cpp:113:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  113 |     int mid = lx + rx >> 1;
      |               ~~~^~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 436 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 440 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 312 ms 17112 KB Output is correct
5 Correct 212 ms 16976 KB Output is correct
6 Correct 265 ms 14624 KB Output is correct
7 Correct 308 ms 14164 KB Output is correct
8 Correct 205 ms 10812 KB Output is correct
9 Correct 285 ms 14420 KB Output is correct
10 Correct 259 ms 13956 KB Output is correct
11 Correct 0 ms 348 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 489 ms 19860 KB Output is correct
13 Correct 755 ms 10120 KB Output is correct
14 Correct 157 ms 5664 KB Output is correct
15 Correct 922 ms 13136 KB Output is correct
16 Correct 116 ms 22552 KB Output is correct
17 Correct 487 ms 16408 KB Output is correct
18 Correct 745 ms 23940 KB Output is correct
19 Correct 664 ms 24000 KB Output is correct
20 Correct 596 ms 23356 KB Output is correct
21 Correct 0 ms 344 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 428 KB Output is correct
12 Correct 305 ms 16980 KB Output is correct
13 Correct 219 ms 16896 KB Output is correct
14 Correct 276 ms 14476 KB Output is correct
15 Correct 304 ms 14164 KB Output is correct
16 Correct 212 ms 11112 KB Output is correct
17 Correct 297 ms 14416 KB Output is correct
18 Correct 255 ms 13908 KB Output is correct
19 Correct 543 ms 20048 KB Output is correct
20 Correct 754 ms 10064 KB Output is correct
21 Correct 162 ms 5692 KB Output is correct
22 Correct 916 ms 13092 KB Output is correct
23 Correct 120 ms 22372 KB Output is correct
24 Correct 511 ms 16416 KB Output is correct
25 Correct 882 ms 23952 KB Output is correct
26 Correct 765 ms 24144 KB Output is correct
27 Correct 682 ms 23380 KB Output is correct
28 Correct 603 ms 256000 KB Output is correct
29 Runtime error 1097 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 0 ms 436 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 440 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 365 ms 16952 KB Output is correct
13 Correct 228 ms 16980 KB Output is correct
14 Correct 290 ms 14432 KB Output is correct
15 Correct 366 ms 14160 KB Output is correct
16 Correct 207 ms 10832 KB Output is correct
17 Correct 334 ms 14416 KB Output is correct
18 Correct 282 ms 13872 KB Output is correct
19 Correct 488 ms 19940 KB Output is correct
20 Correct 803 ms 10020 KB Output is correct
21 Correct 165 ms 5672 KB Output is correct
22 Correct 912 ms 13032 KB Output is correct
23 Correct 120 ms 22488 KB Output is correct
24 Correct 512 ms 16356 KB Output is correct
25 Correct 841 ms 23788 KB Output is correct
26 Correct 717 ms 24148 KB Output is correct
27 Correct 642 ms 23484 KB Output is correct
28 Correct 588 ms 256000 KB Output is correct
29 Runtime error 1050 ms 256000 KB Execution killed with signal 9
30 Halted 0 ms 0 KB -