oj.uz

Submission #54162

# Submission time Handle Problem Language Result Execution time Memory
54162 2018-07-02T14:36:32 Z KieranHorgan Game (IOI13_game) C++17
37 / 100
 13000 ms 100132 KB 
#include "game.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long

long long gcd2(long long X, long long Y) {
    long long tmp;
    if(X==0&&Y==0) return 0;
    if(X==0) return Y;
    if(Y==0) return X;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}

int R, C;

struct colSegmentTree {
    unordered_map<int, int> st;
    void update(int val, int j, int id=1, int l=0, int r=C) {
        if(l>j || r<=j) return;
        if(r-l==1) {
            st[id] = val;
            return;
        }
        int mid = (l+r)/2;
        if(j < mid) update(val, j, id*2  , l, mid);
        else        update(val, j, id*2+1, mid, r);
        if(st.count(id*2  )&&
           st.count(id*2+1))
            st[id] = gcd2(st[id*2], st[id*2+1]);
        else if(st.count(id*2  ))
            st[id] = st[id*2  ];
        else if(st.count(id*2+1))
            st[id] = st[id*2+1];
    }
    int query(int x, int y, int id=1, int l=0, int r=C) {
        if(l>=y || r<=x) return 0;
        if(l>=x && r<=y) {
            // cerr << " " << l << " " << r-1 << endl;
            if(st.count(id))
                return st[id];
            return 0;
        }
        int mid = (l+r)/2;
        return gcd2(query(x, y, id*2  , l, mid),
                    query(x, y, id*2+1, mid, r));
    }
};

struct rowSegmentTree {
    unordered_map<int, colSegmentTree> st;
    void update(int val, int i, int j, int id=1, int l=0, int r=R) {
        if(l>i || r<=i) return;
        st[id].update(val, j);
        if(l+1==r) return;
        int mid = (l+r)/2;
        if(i < mid) update(val, i, j, id*2  , l, mid);
        else        update(val, i, j, id*2+1, mid, r);
    }
    int query(int x, int y, int nx, int ny, int id=1, int l=0, int r=R) {
        if(l>=y || r<=x) return 0;
        if(l+1==r) {
            // cerr << l << " " << r-1 << endl;
            if(st.count(id))
                return st[id].query(nx, ny);
            return 0;
        }
        int mid = (l+r)/2;
        return gcd2(query(x, y, nx, ny, id*2  , l, mid),
                    query(x, y, nx, ny, id*2+1, mid, r));
    }
};

rowSegmentTree tree;

void init(signed r, signed c) {
    R = r;
    C = c;
//    for(int i = 0; i < R; i++)
//        for(int j = 0; j < C; j++)
//            update(i,j,rand());
    /* ... */
}

void update(signed P, signed Q, long long K) {
    tree.update(K, P, Q);
    /* ... */
}

long long calculate(signed P, signed Q, signed U, signed V) {
    /* ... */
    return tree.query(P, U+1, Q, V+1);
}

void test() {
//    for(int P = 0; P < 1000000000; P++)
//        for(int Q = 0; Q < 1000000000; Q++)
//            for(int U = P; U < 1000000000; U++)
//                for(int V = Q; V < 1000000000; V++)
//                    cerr << tree.query(P, U+1, Q, V+1) << endl;
}

Compilation message

grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  int res;
      ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 4 ms 484 KB Output is correct
3 Correct 5 ms 688 KB Output is correct
4 Correct 2 ms 688 KB Output is correct
5 Correct 3 ms 688 KB Output is correct
6 Correct 4 ms 748 KB Output is correct
7 Correct 2 ms 748 KB Output is correct
8 Correct 2 ms 748 KB Output is correct
9 Correct 4 ms 1016 KB Output is correct
10 Correct 3 ms 1016 KB Output is correct
11 Correct 3 ms 1016 KB Output is correct
12 Correct 2 ms 1016 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1016 KB Output is correct
2 Correct 2 ms 1016 KB Output is correct
3 Correct 3 ms 1016 KB Output is correct
4 Correct 4389 ms 16236 KB Output is correct
5 Correct 2877 ms 16616 KB Output is correct
6 Correct 3018 ms 18520 KB Output is correct
7 Correct 3284 ms 23024 KB Output is correct
8 Correct 1650 ms 23024 KB Output is correct
9 Correct 3124 ms 31920 KB Output is correct
10 Correct 3137 ms 36364 KB Output is correct
11 Correct 2 ms 36364 KB Output is correct

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 36364 KB Output is correct
2 Correct 4 ms 36364 KB Output is correct
3 Correct 5 ms 36364 KB Output is correct
4 Correct 2 ms 36364 KB Output is correct
5 Correct 2 ms 36364 KB Output is correct
6 Correct 4 ms 36364 KB Output is correct
7 Correct 2 ms 36364 KB Output is correct
8 Correct 3 ms 36364 KB Output is correct
9 Correct 5 ms 36364 KB Output is correct
10 Correct 3 ms 36364 KB Output is correct
11 Correct 3 ms 36364 KB Output is correct
12 Execution timed out 13097 ms 36364 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 36364 KB Output is correct
2 Correct 4 ms 36364 KB Output is correct
3 Correct 5 ms 36364 KB Output is correct
4 Correct 2 ms 36364 KB Output is correct
5 Correct 2 ms 36364 KB Output is correct
6 Correct 4 ms 36364 KB Output is correct
7 Correct 2 ms 36364 KB Output is correct
8 Correct 3 ms 36364 KB Output is correct
9 Correct 4 ms 36364 KB Output is correct
10 Correct 3 ms 36364 KB Output is correct
11 Correct 3 ms 36364 KB Output is correct
12 Correct 4557 ms 44188 KB Output is correct
13 Correct 2819 ms 48500 KB Output is correct
14 Correct 2811 ms 50596 KB Output is correct
15 Correct 3077 ms 55052 KB Output is correct
16 Correct 1654 ms 55052 KB Output is correct
17 Correct 3054 ms 63996 KB Output is correct
18 Correct 2848 ms 68304 KB Output is correct
19 Execution timed out 13013 ms 68304 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 68304 KB Output is correct
2 Correct 4 ms 68304 KB Output is correct
3 Correct 4 ms 68304 KB Output is correct
4 Correct 2 ms 68304 KB Output is correct
5 Correct 3 ms 68304 KB Output is correct
6 Correct 4 ms 68304 KB Output is correct
7 Correct 2 ms 68304 KB Output is correct
8 Correct 3 ms 68304 KB Output is correct
9 Correct 4 ms 68304 KB Output is correct
10 Correct 3 ms 68304 KB Output is correct
11 Correct 4 ms 68304 KB Output is correct
12 Correct 5100 ms 76380 KB Output is correct
13 Correct 3222 ms 80584 KB Output is correct
14 Correct 3103 ms 82664 KB Output is correct
15 Correct 3573 ms 86988 KB Output is correct
16 Correct 1643 ms 86988 KB Output is correct
17 Correct 3704 ms 95868 KB Output is correct
18 Correct 2769 ms 100132 KB Output is correct
19 Execution timed out 13043 ms 100132 KB Time limit exceeded
20 Halted 0 ms 0 KB -