oj.uz

Submission #54178

# Submission time Handle Problem Language Result Execution time Memory
54178 2018-07-02T16:25:54 Z KieranHorgan Game (IOI13_game) C++17
37 / 100
 13000 ms 42104 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 {
    map<int, int> st;
    void update(int val, int j, colSegmentTree *leftChild=NULL, colSegmentTree *rightChild=NULL, int id=1, int l=0, int r=C) {
        if(l>j || r<=j) return;
        if(r-l==1) {
            if(leftChild==NULL) st[id] = val;
            else st[id] = gcd2(leftChild->st[id], rightChild->st[id]);
            return;
        }
        int mid = (l+r)/2;
        if(j < mid) update(val, j, leftChild, rightChild, id*2  , l, mid);
        else        update(val, j, leftChild, rightChild, 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 {
    map<int, colSegmentTree> st;
    void update(int val, int i, int j, int id=1, int l=0, int r=R) {
        if(l+1==r) {
            // leftChild = NULL; rightChild = NULL;
            st[id].update(val, j);
            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);
        // leftChild = &st[id*2  ];
        // rightChild = &st[id*2+1];
        st[id].update(val, j, &st[id*2], &st[id*2+1]);
    }
    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>=x && r<=y) {
            // 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 248 KB Output is correct
2 Correct 4 ms 616 KB Output is correct
3 Correct 4 ms 668 KB Output is correct
4 Correct 2 ms 668 KB Output is correct
5 Correct 2 ms 668 KB Output is correct
6 Correct 4 ms 720 KB Output is correct
7 Correct 2 ms 720 KB Output is correct
8 Correct 2 ms 720 KB Output is correct
9 Correct 4 ms 720 KB Output is correct
10 Correct 3 ms 720 KB Output is correct
11 Correct 3 ms 720 KB Output is correct
12 Correct 2 ms 720 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 720 KB Output is correct
2 Correct 2 ms 720 KB Output is correct
3 Correct 2 ms 720 KB Output is correct
4 Correct 5144 ms 23180 KB Output is correct
5 Correct 3024 ms 23496 KB Output is correct
6 Correct 4098 ms 23496 KB Output is correct
7 Correct 4851 ms 23496 KB Output is correct
8 Correct 2468 ms 23496 KB Output is correct
9 Correct 4865 ms 23496 KB Output is correct
10 Correct 5360 ms 23496 KB Output is correct
11 Correct 2 ms 23496 KB Output is correct

Subtask #3
0 / 26.0

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

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 31188 KB Output is correct
2 Correct 4 ms 31188 KB Output is correct
3 Correct 4 ms 31188 KB Output is correct
4 Correct 2 ms 31188 KB Output is correct
5 Correct 2 ms 31188 KB Output is correct
6 Correct 4 ms 31188 KB Output is correct
7 Correct 2 ms 31188 KB Output is correct
8 Correct 2 ms 31188 KB Output is correct
9 Correct 4 ms 31188 KB Output is correct
10 Correct 3 ms 31188 KB Output is correct
11 Correct 3 ms 31188 KB Output is correct
12 Correct 5128 ms 31188 KB Output is correct
13 Correct 2971 ms 31188 KB Output is correct
14 Correct 4183 ms 31188 KB Output is correct
15 Correct 4735 ms 31188 KB Output is correct
16 Correct 2471 ms 31188 KB Output is correct
17 Correct 4893 ms 31188 KB Output is correct
18 Correct 4875 ms 31188 KB Output is correct
19 Correct 8426 ms 34536 KB Output is correct
20 Execution timed out 13090 ms 34536 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 34536 KB Output is correct
2 Correct 5 ms 34536 KB Output is correct
3 Correct 4 ms 34536 KB Output is correct
4 Correct 2 ms 34536 KB Output is correct
5 Correct 2 ms 34536 KB Output is correct
6 Correct 6 ms 34536 KB Output is correct
7 Correct 2 ms 34536 KB Output is correct
8 Correct 2 ms 34536 KB Output is correct
9 Correct 4 ms 34536 KB Output is correct
10 Correct 3 ms 34536 KB Output is correct
11 Correct 3 ms 34536 KB Output is correct
12 Correct 5359 ms 34536 KB Output is correct
13 Correct 3203 ms 34536 KB Output is correct
14 Correct 4303 ms 34536 KB Output is correct
15 Correct 5284 ms 34536 KB Output is correct
16 Correct 2375 ms 34536 KB Output is correct
17 Correct 4522 ms 34536 KB Output is correct
18 Correct 4773 ms 34536 KB Output is correct
19 Correct 8227 ms 41844 KB Output is correct
20 Correct 12440 ms 41844 KB Output is correct
21 Correct 991 ms 41844 KB Output is correct
22 Execution timed out 13095 ms 42104 KB Time limit exceeded
23 Halted 0 ms 0 KB -