oj.uz

Submission #54165

# Submission time Handle Problem Language Result Execution time Memory
54165 2018-07-02T14:44:55 Z KieranHorgan Game (IOI13_game) C++17
37 / 100
 13000 ms 16412 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(!st.count(id)) return 0;
        if(l>=x && r<=y) {
            // cerr << " " << l << " " << r-1 << endl;
            return st[id];
        }
        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) {
        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(!st.count(id)) return 0;
        if(l+1==r) {
            // cerr << l << " " << r-1 << endl;
            return st[id].query(nx, ny);
        }
        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 376 KB Output is correct
2 Correct 5 ms 488 KB Output is correct
3 Correct 5 ms 692 KB Output is correct
4 Correct 2 ms 692 KB Output is correct
5 Correct 3 ms 692 KB Output is correct
6 Correct 3 ms 692 KB Output is correct
7 Correct 3 ms 692 KB Output is correct
8 Correct 3 ms 692 KB Output is correct
9 Correct 4 ms 692 KB Output is correct
10 Correct 3 ms 692 KB Output is correct
11 Correct 3 ms 692 KB Output is correct
12 Correct 2 ms 692 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 692 KB Output is correct
2 Correct 2 ms 692 KB Output is correct
3 Correct 2 ms 692 KB Output is correct
4 Correct 5868 ms 16196 KB Output is correct
5 Correct 3397 ms 16360 KB Output is correct
6 Correct 3335 ms 16360 KB Output is correct
7 Correct 3970 ms 16360 KB Output is correct
8 Correct 2093 ms 16360 KB Output is correct
9 Correct 3625 ms 16360 KB Output is correct
10 Correct 4107 ms 16360 KB Output is correct
11 Correct 2 ms 16360 KB Output is correct

Subtask #3
0 / 26.0

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

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16360 KB Output is correct
2 Correct 5 ms 16360 KB Output is correct
3 Correct 4 ms 16360 KB Output is correct
4 Correct 2 ms 16360 KB Output is correct
5 Correct 2 ms 16360 KB Output is correct
6 Correct 4 ms 16360 KB Output is correct
7 Correct 2 ms 16360 KB Output is correct
8 Correct 2 ms 16360 KB Output is correct
9 Correct 4 ms 16360 KB Output is correct
10 Correct 3 ms 16360 KB Output is correct
11 Correct 3 ms 16360 KB Output is correct
12 Correct 5248 ms 16360 KB Output is correct
13 Correct 3120 ms 16412 KB Output is correct
14 Correct 3039 ms 16412 KB Output is correct
15 Correct 3318 ms 16412 KB Output is correct
16 Correct 1828 ms 16412 KB Output is correct
17 Correct 3650 ms 16412 KB Output is correct
18 Correct 4281 ms 16412 KB Output is correct
19 Execution timed out 13028 ms 16412 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 16412 KB Output is correct
2 Correct 5 ms 16412 KB Output is correct
3 Correct 5 ms 16412 KB Output is correct
4 Correct 2 ms 16412 KB Output is correct
5 Correct 2 ms 16412 KB Output is correct
6 Correct 5 ms 16412 KB Output is correct
7 Correct 2 ms 16412 KB Output is correct
8 Correct 2 ms 16412 KB Output is correct
9 Correct 4 ms 16412 KB Output is correct
10 Correct 4 ms 16412 KB Output is correct
11 Correct 3 ms 16412 KB Output is correct
12 Correct 5242 ms 16412 KB Output is correct
13 Correct 3391 ms 16412 KB Output is correct
14 Correct 3214 ms 16412 KB Output is correct
15 Correct 3866 ms 16412 KB Output is correct
16 Correct 2009 ms 16412 KB Output is correct
17 Correct 4054 ms 16412 KB Output is correct
18 Correct 3648 ms 16412 KB Output is correct
19 Execution timed out 13057 ms 16412 KB Time limit exceeded
20 Halted 0 ms 0 KB -