oj.uz

Submission #1087607

# Submission time Handle Problem Language Result Execution time Memory
1087607 2024-09-13T02:37:49 Z Zero_OP Game (IOI13_game) C++14
63 / 100
 1170 ms 43200 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 = 2e6 + 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 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 1 ms 440 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 444 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 0 ms 348 KB Output is correct
4 Correct 295 ms 13060 KB Output is correct
5 Correct 205 ms 12880 KB Output is correct
6 Correct 262 ms 10324 KB Output is correct
7 Correct 304 ms 10068 KB Output is correct
8 Correct 199 ms 8704 KB Output is correct
9 Correct 297 ms 10252 KB Output is correct
10 Correct 250 ms 9808 KB Output is correct
11 Correct 1 ms 348 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 0 ms 448 KB Output is correct
5 Correct 0 ms 344 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 0 ms 348 KB Output is correct
12 Correct 459 ms 14164 KB Output is correct
13 Correct 737 ms 7660 KB Output is correct
14 Correct 156 ms 5720 KB Output is correct
15 Correct 887 ms 9452 KB Output is correct
16 Correct 102 ms 13908 KB Output is correct
17 Correct 463 ms 11348 KB Output is correct
18 Correct 731 ms 15408 KB Output is correct
19 Correct 653 ms 15440 KB Output is correct
20 Correct 577 ms 14928 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 1 ms 348 KB Output is correct
2 Correct 1 ms 444 KB Output is correct
3 Correct 1 ms 444 KB Output is correct
4 Correct 1 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 600 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 287 ms 13028 KB Output is correct
13 Correct 196 ms 12772 KB Output is correct
14 Correct 258 ms 10324 KB Output is correct
15 Correct 290 ms 10064 KB Output is correct
16 Correct 196 ms 8592 KB Output is correct
17 Correct 301 ms 10068 KB Output is correct
18 Correct 252 ms 9620 KB Output is correct
19 Correct 486 ms 14276 KB Output is correct
20 Correct 734 ms 7444 KB Output is correct
21 Correct 166 ms 5720 KB Output is correct
22 Correct 879 ms 9308 KB Output is correct
23 Correct 99 ms 13908 KB Output is correct
24 Correct 458 ms 11344 KB Output is correct
25 Correct 696 ms 15284 KB Output is correct
26 Correct 631 ms 15484 KB Output is correct
27 Correct 585 ms 14928 KB Output is correct
28 Incorrect 1170 ms 43148 KB Output isn't correct
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 344 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 344 KB Output is correct
8 Correct 0 ms 596 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 294 ms 12968 KB Output is correct
13 Correct 190 ms 12884 KB Output is correct
14 Correct 263 ms 10196 KB Output is correct
15 Correct 311 ms 10068 KB Output is correct
16 Correct 200 ms 8532 KB Output is correct
17 Correct 284 ms 10064 KB Output is correct
18 Correct 282 ms 9816 KB Output is correct
19 Correct 474 ms 14292 KB Output is correct
20 Correct 730 ms 7572 KB Output is correct
21 Correct 154 ms 5712 KB Output is correct
22 Correct 860 ms 9420 KB Output is correct
23 Correct 101 ms 13908 KB Output is correct
24 Correct 475 ms 11388 KB Output is correct
25 Correct 717 ms 15188 KB Output is correct
26 Correct 632 ms 15444 KB Output is correct
27 Correct 557 ms 14928 KB Output is correct
28 Incorrect 1112 ms 43200 KB Output isn't correct
29 Halted 0 ms 0 KB -