oj.uz

답안 #1087596

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1087596 2024-09-13T02:19:50 Z Zero_OP 게임 (IOI13_game) C++14
0 / 100
 1 ms 440 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], 1, 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);

    init(2, 3);
    update(0, 0, 20);
    update(0, 2, 15);
    update(1, 1, 12);
    cout << calculate(0, 0, 0, 2) << '\n';
    cout << calculate(0, 0, 1, 1) << '\n';
    update(0, 1, 6);
    update(1, 1, 14);
    cout << calculate(0, 0, 0, 2) << '\n';
    cout << calculate(0, 0, 1, 1) << '\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
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 1 ms 440 KB Output isn't correct
3 Halted 0 ms 0 KB -