oj.uz

Submission #739658

# Submission time Handle Problem Language Result Execution time Memory
739658 2023-05-11T00:23:22 Z Skywk Game (IOI13_game) C++11
63 / 100
 1308 ms 256000 KB 
#include "game.h"
#include <algorithm>

using namespace std;

int N;
struct STUpdate{
    int i; long long x;
    STUpdate(int _i = -1, long long _x = -1) : i(_i), x(_x){};
};
struct STTUpdate{
    int i; STUpdate u;
    STTUpdate(int _i = -1, int _j = -1, long long _x = -1) : i(_i){
        u = {_j, _x};
    }
};
struct STQuery{
    int l, r;
    STQuery(int _l = -1, int _r = -1) : l(_l), r(_r){};
};
struct STTQuery{
    int l, r; STQuery q;
    STTQuery(int l1 = -1, int r1 = -1, int l2 = -1, int r2 = -1) : l(l1), r(r1){
        q = {l2, r2};
    }
};
template<typename T, typename UT, typename QT>
class SegmentTree{
private:
    void update(T *curr, int l, int r, const UT &u){
        if(l == r){
            curr->update(u);
            return;
        }
        int mit = (l + r) >> 1;
        if(curr->ls == NULL){
            curr->create_child();
        }
        if(u.i <= mit) update(curr->ls, l, mit, u);
        else update(curr->rs, mit+1, r, u);
        curr->merge(u);
    }
    long long query(T *curr, int l, int r, const QT &q){
        if(l > q.r || r < q.l) return 0;
        if(q.l <= l && r <= q.r) return curr->query(q);
        int mit = (l + r) >> 1;
        long long res = 0;
        if(curr -> ls != NULL) res = __gcd(res, query(curr->ls, l, mit, q));
        if(curr -> rs != NULL) res = __gcd(res, query(curr->rs, mit+1, r, q));
        return res; 
    }
public:
    T root;
    void update(UT u){update(&root, 0, N-1, u);}
    long long query(QT q){return query(&root, 0, N-1, q);}
};

struct STNode{
    long long v;
    STNode *ls, *rs;
    STNode() : v(0), ls(NULL), rs(NULL){};
    void create_child(){
        ls = new STNode;
        rs = new STNode;
    }
    void update(const STUpdate &u){v = u.x;}
    long long query(const STQuery &q){return v;}
    void merge(const STUpdate &u){v = __gcd(ls->v, rs->v);}
};

struct STTNode{
    SegmentTree<STNode, STUpdate, STQuery> st;
    STTNode *ls, *rs;
    STTNode() : ls(NULL), rs(NULL){}
    void create_child(){
        ls = new STTNode;
        rs = new STTNode;
    }
    void update(const STTUpdate &u){st.update(u.u);}
    long long query(const STTQuery &q){return st.query(q.q);}
    void merge(const STTUpdate &u){
        long long q1 = ls->st.query({u.u.i, u.u.i});
        long long q2 = rs->st.query({u.u.i, u.u.i});
        st.update({u.u.i, __gcd(q1, q2)});
    }
};

SegmentTree<STTNode, STTUpdate, STTQuery> ST;

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

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

long long calculate(int P, int Q, int U, int V) {
    return ST.query({P, U, Q, V});
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 284 KB Output is correct
2 Correct 1 ms 416 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 416 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 416 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 288 KB Output is correct
4 Correct 523 ms 50016 KB Output is correct
5 Correct 394 ms 50460 KB Output is correct
6 Correct 563 ms 47368 KB Output is correct
7 Correct 605 ms 47048 KB Output is correct
8 Correct 405 ms 29872 KB Output is correct
9 Correct 579 ms 47308 KB Output is correct
10 Correct 525 ms 46728 KB Output is correct
11 Correct 0 ms 212 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 416 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 663 ms 23684 KB Output is correct
13 Correct 1035 ms 9864 KB Output is correct
14 Correct 253 ms 2228 KB Output is correct
15 Correct 1229 ms 14124 KB Output is correct
16 Correct 212 ms 30680 KB Output is correct
17 Correct 714 ms 19472 KB Output is correct
18 Correct 1239 ms 30928 KB Output is correct
19 Correct 1058 ms 31364 KB Output is correct
20 Correct 989 ms 30380 KB Output is correct
21 Correct 1 ms 212 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 420 KB Output is correct
4 Correct 0 ms 280 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 284 KB Output is correct
12 Correct 529 ms 50028 KB Output is correct
13 Correct 403 ms 50352 KB Output is correct
14 Correct 558 ms 47260 KB Output is correct
15 Correct 608 ms 47116 KB Output is correct
16 Correct 382 ms 29916 KB Output is correct
17 Correct 580 ms 47288 KB Output is correct
18 Correct 550 ms 46676 KB Output is correct
19 Correct 655 ms 23816 KB Output is correct
20 Correct 1044 ms 9996 KB Output is correct
21 Correct 261 ms 2224 KB Output is correct
22 Correct 1217 ms 14480 KB Output is correct
23 Correct 218 ms 30796 KB Output is correct
24 Correct 693 ms 19496 KB Output is correct
25 Correct 1245 ms 31076 KB Output is correct
26 Correct 1041 ms 31256 KB Output is correct
27 Correct 1000 ms 30544 KB Output is correct
28 Runtime error 496 ms 256000 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 412 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 288 KB Output is correct
12 Correct 551 ms 50416 KB Output is correct
13 Correct 398 ms 50612 KB Output is correct
14 Correct 564 ms 47584 KB Output is correct
15 Correct 593 ms 47292 KB Output is correct
16 Correct 398 ms 30304 KB Output is correct
17 Correct 599 ms 47644 KB Output is correct
18 Correct 539 ms 46924 KB Output is correct
19 Correct 681 ms 24096 KB Output is correct
20 Correct 1024 ms 10424 KB Output is correct
21 Correct 255 ms 2672 KB Output is correct
22 Correct 1251 ms 14504 KB Output is correct
23 Correct 232 ms 30988 KB Output is correct
24 Correct 706 ms 19812 KB Output is correct
25 Correct 1308 ms 31228 KB Output is correct
26 Correct 1100 ms 31612 KB Output is correct
27 Correct 1016 ms 30676 KB Output is correct
28 Runtime error 487 ms 256000 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -