oj.uz

답안 #373741

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
373741 2021-03-05T14:45:08 Z cheissmart 게임 (IOI13_game) C++14
63 / 100
 2043 ms 256004 KB 
#include "game.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define EB emplace_back
#define V vector
#define ALL(v) (v).begin(), (v).end()
#define debug(x) cerr << "LINE(" << __LINE__ << ") -> " << #x << " is " << (x) << endl
#define tm (tl + tr) / 2

using namespace std;
 
typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;
 
const int INF = 1e9 + 7;

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;
}

int R, C;

struct seg_y {
    struct node {
        node *l, *r;
        ll g; // gcd
        node(ll _g = 0) {
            l = r = nullptr;
            g = _g;
        }
    };
    node* root;
    seg_y() {
        root = nullptr;
    }
    ll g(node* t) {
        return t ? t -> g : 0LL;
    }
    void pull(node* t) {   
        t -> g = gcd2(g(t -> l), g(t -> r));
    }
    void upd(node* &t, int y, ll val, int tl = 0, int tr = C) {
        if(!t) t = new node();
        if(tr - tl == 1) {
            t -> g = val;
            return;
        }
        // int tm = (tl + tr) / 2;
        if(y < tm) upd(t -> l, y, val, tl, tm);
        else upd(t -> r, y, val, tm, tr);
        pull(t);
    }
    ll qry(node* t, int l, int r, int tl = 0, int tr = C) {
        if(!t) return 0;
        if(l <= tl && tr <= r) return t -> g;
        // int tm = (tl + tr) / 2;
        ll g = 0;
        if(l < tm) g = gcd2(g, qry(t -> l, l, r, tl, tm));
        if(r > tm) g = gcd2(g, qry(t -> r, l, r, tm, tr));
        return g;
    }
    void upd(int y, ll val) {
        upd(root, y, val);
    }
    ll qry(int l, int r) {
        return qry(root, l, r);
    }
    ll qry(int y) {
        return qry(y, y + 1);
    }
};

struct seg_x {
    struct node {
        node *l, *r;
        seg_y seg;
        node() {
            l = r = nullptr;
        }
    };
    node* root;
    void pull(node* t, int y) {
        ll g = 0;
        if(t -> l) g = gcd2(g, t -> l -> seg.qry(y));
        if(t -> r) g = gcd2(g, t -> r -> seg.qry(y));
        t -> seg.upd(y, g);
    }
    void upd(node* &t, int x, int y, ll val, int tl = 0, int tr = R) {
        if(!t) t = new node();
        if(tr - tl == 1) {
            t -> seg.upd(y, val);
            return;
        }
        // int tm = (tl + tr) / 2;
        if(x < tm) upd(t -> l, x, y, val, tl, tm);
        else upd(t -> r, x, y, val, tm, tr);
        pull(t, y);
    }
    void upd(int x, int y, ll val) {
        upd(root, x, y, val);
    }
    ll qry(node* t, int xl, int xr, int yl, int yr, int tl = 0, int tr = R) {
        if(!t) return 0;
        if(xl <= tl && tr <= xr) return t -> seg.qry(yl, yr);
        // int tm = (tl + tr) / 2;
        ll g = 0;
        if(xl < tm) g = gcd2(g, qry(t -> l, xl, xr, yl, yr, tl, tm));
        if(xr > tm) g = gcd2(g, qry(t -> r, xl, xr, yl, yr, tm, tr));
        return g;
    }
    ll qry(int xl, int xr, int yl, int yr) {
        return qry(root, xl, xr, yl, yr);
    }
} seg;

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

void update(int P, int Q, long long K) {
    seg.upd(P, Q, K);
}

long long calculate(int P, int Q, int U, int V) {
    return seg.qry(P, U + 1, Q, V + 1);
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct

Subtask #2
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 572 ms 14580 KB Output is correct
5 Correct 417 ms 14828 KB Output is correct
6 Correct 510 ms 11628 KB Output is correct
7 Correct 571 ms 11500 KB Output is correct
8 Correct 358 ms 8556 KB Output is correct
9 Correct 574 ms 11628 KB Output is correct
10 Correct 544 ms 11116 KB Output is correct
11 Correct 1 ms 364 KB Output is correct

Subtask #3
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 492 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 868 ms 17772 KB Output is correct
13 Correct 1385 ms 8172 KB Output is correct
14 Correct 310 ms 2924 KB Output is correct
15 Correct 1685 ms 10840 KB Output is correct
16 Correct 250 ms 20076 KB Output is correct
17 Correct 917 ms 13436 KB Output is correct
18 Correct 1658 ms 20160 KB Output is correct
19 Correct 1352 ms 20460 KB Output is correct
20 Correct 1320 ms 19536 KB Output is correct
21 Correct 1 ms 364 KB Output is correct

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 564 ms 14700 KB Output is correct
13 Correct 425 ms 15496 KB Output is correct
14 Correct 502 ms 12244 KB Output is correct
15 Correct 619 ms 12208 KB Output is correct
16 Correct 362 ms 10476 KB Output is correct
17 Correct 616 ms 12524 KB Output is correct
18 Correct 529 ms 11756 KB Output is correct
19 Correct 888 ms 19308 KB Output is correct
20 Correct 1443 ms 8588 KB Output is correct
21 Correct 297 ms 5612 KB Output is correct
22 Correct 1684 ms 13384 KB Output is correct
23 Correct 250 ms 22508 KB Output is correct
24 Correct 891 ms 16236 KB Output is correct
25 Correct 1652 ms 23180 KB Output is correct
26 Correct 1368 ms 23144 KB Output is correct
27 Correct 1266 ms 22400 KB Output is correct
28 Correct 1212 ms 256000 KB Output is correct
29 Runtime error 2043 ms 256004 KB Execution killed with signal 9
30 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 564 ms 13804 KB Output is correct
13 Correct 410 ms 14188 KB Output is correct
14 Correct 489 ms 10732 KB Output is correct
15 Correct 590 ms 10540 KB Output is correct
16 Correct 371 ms 7916 KB Output is correct
17 Correct 573 ms 10660 KB Output is correct
18 Correct 534 ms 10092 KB Output is correct
19 Correct 860 ms 17260 KB Output is correct
20 Correct 1388 ms 7468 KB Output is correct
21 Correct 293 ms 1772 KB Output is correct
22 Correct 1711 ms 10032 KB Output is correct
23 Correct 253 ms 19760 KB Output is correct
24 Correct 855 ms 12524 KB Output is correct
25 Correct 1591 ms 19436 KB Output is correct
26 Correct 1321 ms 19536 KB Output is correct
27 Correct 1305 ms 19180 KB Output is correct
28 Correct 1091 ms 256000 KB Output is correct
29 Runtime error 2004 ms 256000 KB Execution killed with signal 9
30 Halted 0 ms 0 KB -