oj.uz

Submission #330032

# Submission time Handle Problem Language Result Execution time Memory
330032 2020-11-23T13:51:20 Z 2qbingxuan Game (IOI13_game) C++14
63 / 100
 2028 ms 256004 KB 
#include <bits/stdc++.h>
#include "game.h"

using namespace std;
using ll = long long;

int R, C;
class Segtree1d {
    // 1d, dynamic
private:
    struct node {
        ll ans;
        node *l, *r;
        node() : ans(0), l(nullptr), r(nullptr) {}
        void pull() {
            ans = __gcd( l ? l->ans : 0, r ? r->ans : 0);
        }
    } *root;
    void modify(int pos, ll v, node *&cur, int l, int r) {
        if(!cur) cur = new node();
        if(l+1 == r) {
            cur->ans = v;
            return;
        }
        int m = l+(r-l)/2;
        if(pos < m)
            modify(pos, v, cur->l, l, m);
        else
            modify(pos, v, cur->r, m, r);
        cur->pull();
    }
    ll query(int ql, int qr, node *cur, int l, int r) {
        if(l >= qr || r <= ql || !cur) return 0;
        if(ql <= l && r <= qr) return cur->ans;
        int m = l+(r-l)/2;
        return __gcd(query(ql, qr, cur->l, l, m), query(ql, qr, cur->r, m, r));
    }
public:
    Segtree1d() : root(nullptr) {}
    void modify(int pos, ll v) {
        modify(pos, v, root, 0, C);
    }
    ll query(int l, int r) {
        return query(l, r, root, 0, C);
    }
};

class Segtree2d {
private:
    struct node {
        Segtree1d st;
        node *l, *r;
        node() : l(nullptr), r(nullptr) {}
        // Complexity of pull would TLE
        // Notice that only posy would change
        void pull(int y) {
            st.modify(y, __gcd(l ? l->st.query(y, y+1) : 0, r ? r->st.query(y, y+1) : 0));
        }
    } *root;
    void modify(int posx, int posy, ll v, node *&cur, int l, int r) {
        if(!cur) cur = new node();
        if(l+1 == r) {
            cur->st.modify(posy, v);
            return;
        }
        int m = l+(r-l)/2;
        if(posx < m)
            modify(posx, posy, v, cur->l, l, m);
        else
            modify(posx, posy, v, cur->r, m, r);
        cur->pull(posy);
    }
    ll query(int lx, int rx, int ly, int ry, node *cur, int l, int r) {
        if(r <= lx || l >= rx || !cur) return 0;
        if(lx <= l && r <= rx) return cur->st.query(ly, ry);
        int m = l+(r-l)/2;
        return __gcd(query(lx, rx, ly, ry, cur->l, l, m), query(lx, rx, ly, ry, cur->r, m, r));
    }
public:
    Segtree2d() : root(nullptr) {}
    void modify(int posx, int posy, ll v) {
        modify(posx, posy, v, root, 0, R);
    }
    ll query(int lx, int rx, int ly, int ry) {
        return query(lx, rx, ly, ry, root, 0, R);
    }
} sgt;

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

void update(int x, int y, ll k) {
    sgt.modify(x, y, k);
}

ll calculate(int lx, int ly, int rx, int ry) {
    if(lx > rx) swap(lx, rx);
    if(ly > ry) swap(ly, ry);
    return sgt.query(lx, rx+1, ly, ry+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 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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 559 ms 17132 KB Output is correct
5 Correct 418 ms 17260 KB Output is correct
6 Correct 517 ms 14572 KB Output is correct
7 Correct 559 ms 14316 KB Output is correct
8 Correct 373 ms 10988 KB Output is correct
9 Correct 548 ms 14444 KB Output is correct
10 Correct 515 ms 14060 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 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 877 ms 20076 KB Output is correct
13 Correct 1351 ms 10220 KB Output is correct
14 Correct 319 ms 5868 KB Output is correct
15 Correct 1601 ms 13292 KB Output is correct
16 Correct 251 ms 22636 KB Output is correct
17 Correct 900 ms 16492 KB Output is correct
18 Correct 1547 ms 24044 KB Output is correct
19 Correct 1329 ms 24172 KB Output is correct
20 Correct 1243 ms 23404 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 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 549 ms 17260 KB Output is correct
13 Correct 416 ms 16876 KB Output is correct
14 Correct 499 ms 14700 KB Output is correct
15 Correct 550 ms 14276 KB Output is correct
16 Correct 363 ms 10988 KB Output is correct
17 Correct 603 ms 14536 KB Output is correct
18 Correct 500 ms 14060 KB Output is correct
19 Correct 881 ms 19948 KB Output is correct
20 Correct 1359 ms 10092 KB Output is correct
21 Correct 306 ms 5740 KB Output is correct
22 Correct 1595 ms 13292 KB Output is correct
23 Correct 254 ms 22508 KB Output is correct
24 Correct 884 ms 16492 KB Output is correct
25 Correct 1536 ms 24032 KB Output is correct
26 Correct 1322 ms 24172 KB Output is correct
27 Correct 1244 ms 23660 KB Output is correct
28 Correct 1161 ms 256000 KB Output is correct
29 Runtime error 2020 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
30 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 2 ms 504 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 2 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 560 ms 17224 KB Output is correct
13 Correct 411 ms 16876 KB Output is correct
14 Correct 498 ms 14444 KB Output is correct
15 Correct 572 ms 14188 KB Output is correct
16 Correct 369 ms 10988 KB Output is correct
17 Correct 565 ms 14424 KB Output is correct
18 Correct 504 ms 14060 KB Output is correct
19 Correct 877 ms 20092 KB Output is correct
20 Correct 1369 ms 10320 KB Output is correct
21 Correct 308 ms 5728 KB Output is correct
22 Correct 1600 ms 13308 KB Output is correct
23 Correct 251 ms 22524 KB Output is correct
24 Correct 957 ms 16492 KB Output is correct
25 Correct 1718 ms 23916 KB Output is correct
26 Correct 1429 ms 24044 KB Output is correct
27 Correct 1421 ms 23636 KB Output is correct
28 Correct 1159 ms 256000 KB Output is correct
29 Runtime error 2028 ms 256000 KB Execution killed with signal 9 (could be triggered by violating memory limits)
30 Halted 0 ms 0 KB -