oj.uz

Submission #54179

# Submission time Handle Problem Language Result Execution time Memory
54179 2018-07-02T16:34:52 Z KieranHorgan Game (IOI13_game) C++17
37 / 100
 13000 ms 46576 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&&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 {
    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 504 KB Output is correct
2 Correct 4 ms 616 KB Output is correct
3 Correct 4 ms 616 KB Output is correct
4 Correct 2 ms 616 KB Output is correct
5 Correct 2 ms 616 KB Output is correct
6 Correct 4 ms 664 KB Output is correct
7 Correct 2 ms 664 KB Output is correct
8 Correct 2 ms 664 KB Output is correct
9 Correct 4 ms 708 KB Output is correct
10 Correct 3 ms 708 KB Output is correct
11 Correct 4 ms 708 KB Output is correct
12 Correct 2 ms 708 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 708 KB Output is correct
2 Correct 3 ms 708 KB Output is correct
3 Correct 2 ms 708 KB Output is correct
4 Correct 5586 ms 23364 KB Output is correct
5 Correct 3168 ms 23664 KB Output is correct
6 Correct 4489 ms 23664 KB Output is correct
7 Correct 5756 ms 23664 KB Output is correct
8 Correct 2582 ms 23664 KB Output is correct
9 Correct 5367 ms 23664 KB Output is correct
10 Correct 5090 ms 23664 KB Output is correct
11 Correct 2 ms 23664 KB Output is correct

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 23664 KB Output is correct
2 Correct 4 ms 23664 KB Output is correct
3 Correct 6 ms 23664 KB Output is correct
4 Correct 2 ms 23664 KB Output is correct
5 Correct 3 ms 23664 KB Output is correct
6 Correct 5 ms 23664 KB Output is correct
7 Correct 3 ms 23664 KB Output is correct
8 Correct 2 ms 23664 KB Output is correct
9 Correct 5 ms 23664 KB Output is correct
10 Correct 3 ms 23664 KB Output is correct
11 Correct 4 ms 23664 KB Output is correct
12 Correct 8604 ms 34668 KB Output is correct
13 Correct 12764 ms 34668 KB Output is correct
14 Correct 956 ms 34668 KB Output is correct
15 Execution timed out 13029 ms 34668 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 34668 KB Output is correct
2 Correct 5 ms 34668 KB Output is correct
3 Correct 5 ms 34668 KB Output is correct
4 Correct 3 ms 34668 KB Output is correct
5 Correct 2 ms 34668 KB Output is correct
6 Correct 5 ms 34668 KB Output is correct
7 Correct 2 ms 34668 KB Output is correct
8 Correct 2 ms 34668 KB Output is correct
9 Correct 4 ms 34668 KB Output is correct
10 Correct 4 ms 34668 KB Output is correct
11 Correct 4 ms 34668 KB Output is correct
12 Correct 5450 ms 38744 KB Output is correct
13 Correct 3014 ms 38904 KB Output is correct
14 Correct 4356 ms 38904 KB Output is correct
15 Correct 5191 ms 38904 KB Output is correct
16 Correct 2522 ms 38904 KB Output is correct
17 Correct 4942 ms 38904 KB Output is correct
18 Correct 5000 ms 38904 KB Output is correct
19 Correct 8490 ms 46428 KB Output is correct
20 Execution timed out 13042 ms 46428 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 46428 KB Output is correct
2 Correct 4 ms 46428 KB Output is correct
3 Correct 5 ms 46428 KB Output is correct
4 Correct 2 ms 46428 KB Output is correct
5 Correct 3 ms 46428 KB Output is correct
6 Correct 4 ms 46428 KB Output is correct
7 Correct 2 ms 46428 KB Output is correct
8 Correct 2 ms 46428 KB Output is correct
9 Correct 4 ms 46428 KB Output is correct
10 Correct 3 ms 46428 KB Output is correct
11 Correct 3 ms 46428 KB Output is correct
12 Correct 5373 ms 46428 KB Output is correct
13 Correct 2926 ms 46428 KB Output is correct
14 Correct 4366 ms 46428 KB Output is correct
15 Correct 5834 ms 46428 KB Output is correct
16 Correct 2522 ms 46428 KB Output is correct
17 Correct 4874 ms 46428 KB Output is correct
18 Correct 5342 ms 46428 KB Output is correct
19 Correct 8380 ms 46576 KB Output is correct
20 Execution timed out 13068 ms 46576 KB Time limit exceeded
21 Halted 0 ms 0 KB -