oj.uz

Submission #54180

# Submission time Handle Problem Language Result Execution time Memory
54180 2018-07-02T16:35:52 Z KieranHorgan Game (IOI13_game) C++17
63 / 100
 13000 ms 58636 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, 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&&rightChild==NULL) st[id] = val;
            else if(leftChild==NULL) st[id] = rightChild->st[id];
            else if(rightChild==NULL) st[id] = leftChild->st[id];
            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 {
    unordered_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];
        if(!st.count(id*2)&&!st.count(id*2+1)) st[id].update(val, j, NULL, NULL);
        else if(!st.count(id*2)) st[id].update(val, j, NULL, &st[id*2+1]);
        else if(!st.count(id*2+1)) st[id].update(val, j, &st[id*2], NULL);
        else 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 484 KB Output is correct
3 Correct 5 ms 560 KB Output is correct
4 Correct 2 ms 560 KB Output is correct
5 Correct 2 ms 560 KB Output is correct
6 Correct 3 ms 616 KB Output is correct
7 Correct 2 ms 616 KB Output is correct
8 Correct 2 ms 616 KB Output is correct
9 Correct 4 ms 672 KB Output is correct
10 Correct 2 ms 672 KB Output is correct
11 Correct 4 ms 672 KB Output is correct
12 Correct 2 ms 672 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 672 KB Output is correct
2 Correct 3 ms 672 KB Output is correct
3 Correct 2 ms 672 KB Output is correct
4 Correct 3250 ms 17164 KB Output is correct
5 Correct 2724 ms 17592 KB Output is correct
6 Correct 2685 ms 17592 KB Output is correct
7 Correct 3442 ms 17592 KB Output is correct
8 Correct 1627 ms 17592 KB Output is correct
9 Correct 3100 ms 17592 KB Output is correct
10 Correct 3018 ms 17592 KB Output is correct
11 Correct 2 ms 17592 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 17592 KB Output is correct
2 Correct 4 ms 17592 KB Output is correct
3 Correct 4 ms 17592 KB Output is correct
4 Correct 2 ms 17592 KB Output is correct
5 Correct 2 ms 17592 KB Output is correct
6 Correct 4 ms 17592 KB Output is correct
7 Correct 2 ms 17592 KB Output is correct
8 Correct 2 ms 17592 KB Output is correct
9 Correct 3 ms 17592 KB Output is correct
10 Correct 3 ms 17592 KB Output is correct
11 Correct 3 ms 17592 KB Output is correct
12 Correct 5982 ms 23132 KB Output is correct
13 Correct 9684 ms 23132 KB Output is correct
14 Correct 1223 ms 23132 KB Output is correct
15 Correct 12255 ms 23132 KB Output is correct
16 Correct 1041 ms 33728 KB Output is correct
17 Correct 5086 ms 33728 KB Output is correct
18 Correct 10184 ms 44132 KB Output is correct
19 Correct 8201 ms 49740 KB Output is correct
20 Correct 8010 ms 54368 KB Output is correct
21 Correct 2 ms 54368 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 54368 KB Output is correct
2 Correct 4 ms 54368 KB Output is correct
3 Correct 5 ms 54368 KB Output is correct
4 Correct 2 ms 54368 KB Output is correct
5 Correct 2 ms 54368 KB Output is correct
6 Correct 5 ms 54368 KB Output is correct
7 Correct 2 ms 54368 KB Output is correct
8 Correct 2 ms 54368 KB Output is correct
9 Correct 4 ms 54368 KB Output is correct
10 Correct 3 ms 54368 KB Output is correct
11 Correct 3 ms 54368 KB Output is correct
12 Correct 3173 ms 54368 KB Output is correct
13 Correct 2393 ms 54368 KB Output is correct
14 Correct 2827 ms 54368 KB Output is correct
15 Correct 3301 ms 54368 KB Output is correct
16 Correct 1390 ms 54368 KB Output is correct
17 Correct 2725 ms 54368 KB Output is correct
18 Correct 2992 ms 54368 KB Output is correct
19 Correct 5982 ms 54368 KB Output is correct
20 Correct 10154 ms 54368 KB Output is correct
21 Correct 1101 ms 54368 KB Output is correct
22 Execution timed out 13045 ms 54368 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 54368 KB Output is correct
2 Correct 6 ms 54368 KB Output is correct
3 Correct 5 ms 54368 KB Output is correct
4 Correct 2 ms 54368 KB Output is correct
5 Correct 2 ms 54368 KB Output is correct
6 Correct 5 ms 54368 KB Output is correct
7 Correct 2 ms 54368 KB Output is correct
8 Correct 2 ms 54368 KB Output is correct
9 Correct 4 ms 54368 KB Output is correct
10 Correct 3 ms 54368 KB Output is correct
11 Correct 3 ms 54368 KB Output is correct
12 Correct 3387 ms 54368 KB Output is correct
13 Correct 2306 ms 54368 KB Output is correct
14 Correct 2812 ms 54368 KB Output is correct
15 Correct 3408 ms 54368 KB Output is correct
16 Correct 1726 ms 54368 KB Output is correct
17 Correct 3009 ms 54368 KB Output is correct
18 Correct 3291 ms 54368 KB Output is correct
19 Correct 5857 ms 58636 KB Output is correct
20 Correct 9703 ms 58636 KB Output is correct
21 Correct 1323 ms 58636 KB Output is correct
22 Execution timed out 13063 ms 58636 KB Time limit exceeded
23 Halted 0 ms 0 KB -