oj.uz

Submission #1087608

# Submission time Handle Problem Language Result Execution time Memory
1087608 2024-09-13T02:38:52 Z Zero_OP Game (IOI13_game) C++14
63 / 100
 915 ms 194644 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;
}

const int MAX = 6e6 + 5;
int N, M, tree2D, left_x[MAX], right_x[MAX], left_y[MAX], right_y[MAX], id[MAX], num_x, num_y;
long long st[MAX];

void define_y(int& y){
    if(y == 0) y = ++num_y;
}

void define_x(int& x){
    if(x == 0) x = ++num_x;
}

void update_y(int& idx, int lx, int rx, int tl, int tr, int& idy, int ly, int ry, int y, long long k){
    define_y(idy);
//    cout << dbg(ly) << dbg(ry) << dbg(y) << dbg(k) << '\n';

    if(ly == ry){
        if(lx == rx) st[idy] = k;
        else st[idy] = gcd2(st[tl], st[tr]);
    } else{
        int mid = (ly + ry) >> 1;
        if(y <= mid) update_y(idx, lx, rx, left_y[tl], left_y[tr], left_y[idy], ly, mid, y, k);
        else update_y(idx, lx, rx, right_y[tl], right_y[tr], right_y[idy], mid + 1, ry, y, k);

        st[idy] = gcd2(st[left_y[idy]], st[right_y[idy]]);
    }

//    cout << dbg(idx) << dbg(idy) << dbg(ly) << dbg(ry) << dbg(st[idy]) << '\n';
}

void update_x(int& idx, int lx, int rx, int x, int y, long long k){
    define_x(idx);
//    cout << dbg(idx) << dbg(lx) << dbg(rx) << '\n';

    if(lx < rx){
        int mid = lx + rx >> 1;
        if(x <= mid) update_x(left_x[idx], lx, mid, x, y, k);
        else update_x(right_x[idx], mid + 1, rx, x, y, k);
    }

    update_y(idx, lx, rx, id[left_x[idx]], id[right_x[idx]], id[idx], 0, M - 1, y, k);
}

long long query_y(int& idy, int ly, int ry, int u, int v){
    if((u <= ly && ry <= v) || idy == 0) return st[idy];
    int mid = ly + ry >> 1;
    long long g = 0;
    if(u <= mid) g = gcd2(g, query_y(left_y[idy], ly, mid, u, v));
    if(mid < v) g = gcd2(g, query_y(right_y[idy], mid + 1, ry, u, v));
    return g;
}

long long query_x(int& idx, int lx, int rx, int u, int v, int p, int q){
    if((u <= lx && rx <= v) || idx == 0) return query_y(id[idx], 0, M - 1, p, q);
     int mid = lx + rx >> 1;
     long long g = 0;
     if(u <= mid) g = gcd2(g, query_x(left_x[idx], lx, mid, u, v, p, q));
     if(mid < v) g = gcd2(g, query_x(right_x[idx], 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 function 'void update_x(int&, int, int, int, int, long long int)':
game.cpp:78:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   78 |         int mid = lx + rx >> 1;
      |                   ~~~^~~~
game.cpp: In function 'long long int query_y(int&, int, int, int, int)':
game.cpp:88:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   88 |     int mid = ly + ry >> 1;
      |               ~~~^~~~
game.cpp: In function 'long long int query_x(int&, int, int, int, int, int, int)':
game.cpp:97:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   97 |      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 0 ms 348 KB Output is correct
3 Correct 0 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 1 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 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct

Subtask #2
27.0 / 27.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 600 KB Output is correct
4 Correct 302 ms 8528 KB Output is correct
5 Correct 209 ms 8824 KB Output is correct
6 Correct 291 ms 5716 KB Output is correct
7 Correct 286 ms 5468 KB Output is correct
8 Correct 193 ms 4224 KB Output is correct
9 Correct 284 ms 5460 KB Output is correct
10 Correct 275 ms 5036 KB Output is correct
11 Correct 1 ms 344 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 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 0 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 460 ms 10124 KB Output is correct
13 Correct 783 ms 3628 KB Output is correct
14 Correct 158 ms 848 KB Output is correct
15 Correct 915 ms 4944 KB Output is correct
16 Correct 102 ms 9636 KB Output is correct
17 Correct 515 ms 6480 KB Output is correct
18 Correct 705 ms 10064 KB Output is correct
19 Correct 621 ms 10232 KB Output is correct
20 Correct 596 ms 9556 KB Output is correct
21 Correct 0 ms 348 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 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 404 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 303 ms 8556 KB Output is correct
13 Correct 200 ms 8836 KB Output is correct
14 Correct 265 ms 5780 KB Output is correct
15 Correct 303 ms 5456 KB Output is correct
16 Correct 203 ms 4436 KB Output is correct
17 Correct 282 ms 5480 KB Output is correct
18 Correct 242 ms 5200 KB Output is correct
19 Correct 458 ms 10224 KB Output is correct
20 Correct 724 ms 3688 KB Output is correct
21 Correct 150 ms 1064 KB Output is correct
22 Correct 881 ms 4828 KB Output is correct
23 Correct 108 ms 9812 KB Output is correct
24 Correct 471 ms 6736 KB Output is correct
25 Correct 709 ms 10064 KB Output is correct
26 Correct 614 ms 10236 KB Output is correct
27 Correct 572 ms 9420 KB Output is correct
28 Runtime error 331 ms 194644 KB Execution killed with signal 11
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 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 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 298 ms 8632 KB Output is correct
13 Correct 189 ms 8764 KB Output is correct
14 Correct 274 ms 5752 KB Output is correct
15 Correct 289 ms 5428 KB Output is correct
16 Correct 202 ms 4432 KB Output is correct
17 Correct 276 ms 5396 KB Output is correct
18 Correct 249 ms 5204 KB Output is correct
19 Correct 458 ms 10068 KB Output is correct
20 Correct 744 ms 3744 KB Output is correct
21 Correct 150 ms 1064 KB Output is correct
22 Correct 864 ms 4776 KB Output is correct
23 Correct 102 ms 9580 KB Output is correct
24 Correct 454 ms 6484 KB Output is correct
25 Correct 712 ms 10068 KB Output is correct
26 Correct 641 ms 10248 KB Output is correct
27 Correct 599 ms 9812 KB Output is correct
28 Runtime error 364 ms 194644 KB Execution killed with signal 11
29 Halted 0 ms 0 KB -