oj.uz

Submission #373743

# Submission time Handle Problem Language Result Execution time Memory
373743 2021-03-05T14:51:04 Z cheissmart Game (IOI13_game) C++14
63 / 100
 2170 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
 
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;
        return gcd2(l < tm ? qry(t -> l, l, r, tl, tm) : 0LL, r > tm ? qry(t -> r, l, r, tm, tr) : 0LL);
    }
    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

# Verdict Execution time Memory 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 0 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 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 492 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory 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 600 ms 12732 KB Output is correct
5 Correct 436 ms 13036 KB Output is correct
6 Correct 511 ms 9836 KB Output is correct
7 Correct 560 ms 9708 KB Output is correct
8 Correct 384 ms 6764 KB Output is correct
9 Correct 545 ms 9708 KB Output is correct
10 Correct 517 ms 9380 KB Output is correct
11 Correct 1 ms 364 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory 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 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 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 901 ms 15980 KB Output is correct
13 Correct 1432 ms 6252 KB Output is correct
14 Correct 316 ms 1028 KB Output is correct
15 Correct 1744 ms 8940 KB Output is correct
16 Correct 257 ms 18284 KB Output is correct
17 Correct 883 ms 11628 KB Output is correct
18 Correct 1622 ms 18684 KB Output is correct
19 Correct 1383 ms 18924 KB Output is correct
20 Correct 1348 ms 18344 KB Output is correct
21 Correct 1 ms 364 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory 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 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 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 544 ms 12652 KB Output is correct
13 Correct 432 ms 13036 KB Output is correct
14 Correct 530 ms 10092 KB Output is correct
15 Correct 572 ms 9708 KB Output is correct
16 Correct 351 ms 6764 KB Output is correct
17 Correct 558 ms 9708 KB Output is correct
18 Correct 508 ms 9452 KB Output is correct
19 Correct 948 ms 15980 KB Output is correct
20 Correct 1433 ms 6424 KB Output is correct
21 Correct 298 ms 996 KB Output is correct
22 Correct 1748 ms 8812 KB Output is correct
23 Correct 250 ms 18284 KB Output is correct
24 Correct 881 ms 11628 KB Output is correct
25 Correct 1633 ms 18668 KB Output is correct
26 Correct 1363 ms 18752 KB Output is correct
27 Correct 1277 ms 18276 KB Output is correct
28 Correct 1094 ms 254220 KB Output is correct
29 Runtime error 2086 ms 256004 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 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 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 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 553 ms 12780 KB Output is correct
13 Correct 438 ms 13164 KB Output is correct
14 Correct 513 ms 9836 KB Output is correct
15 Correct 569 ms 9708 KB Output is correct
16 Correct 366 ms 6892 KB Output is correct
17 Correct 621 ms 9836 KB Output is correct
18 Correct 518 ms 9324 KB Output is correct
19 Correct 921 ms 15916 KB Output is correct
20 Correct 1423 ms 6380 KB Output is correct
21 Correct 304 ms 1132 KB Output is correct
22 Correct 1723 ms 8888 KB Output is correct
23 Correct 260 ms 18284 KB Output is correct
24 Correct 965 ms 11728 KB Output is correct
25 Correct 1658 ms 18804 KB Output is correct
26 Correct 1461 ms 18796 KB Output is correct
27 Correct 1308 ms 18220 KB Output is correct
28 Correct 1139 ms 255444 KB Output is correct
29 Runtime error 2170 ms 256004 KB Execution killed with signal 9
30 Halted 0 ms 0 KB -