oj.uz

Submission #54182

# Submission time Handle Problem Language Result Execution time Memory
54182 2018-07-02T16:39:28 Z KieranHorgan Game (IOI13_game) C++17
63 / 100
 11941 ms 257024 KB 
#pragma GCC optimize("Ofast")
#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 612 KB Output is correct
3 Correct 6 ms 676 KB Output is correct
4 Correct 2 ms 676 KB Output is correct
5 Correct 3 ms 676 KB Output is correct
6 Correct 5 ms 692 KB Output is correct
7 Correct 3 ms 692 KB Output is correct
8 Correct 2 ms 692 KB Output is correct
9 Correct 4 ms 736 KB Output is correct
10 Correct 4 ms 736 KB Output is correct
11 Correct 4 ms 736 KB Output is correct
12 Correct 2 ms 736 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 736 KB Output is correct
2 Correct 3 ms 736 KB Output is correct
3 Correct 2 ms 736 KB Output is correct
4 Correct 3279 ms 17224 KB Output is correct
5 Correct 2144 ms 17736 KB Output is correct
6 Correct 2549 ms 17736 KB Output is correct
7 Correct 3026 ms 17736 KB Output is correct
8 Correct 1882 ms 17736 KB Output is correct
9 Correct 2822 ms 17736 KB Output is correct
10 Correct 2741 ms 17736 KB Output is correct
11 Correct 3 ms 17736 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 17736 KB Output is correct
2 Correct 4 ms 17736 KB Output is correct
3 Correct 4 ms 17736 KB Output is correct
4 Correct 2 ms 17736 KB Output is correct
5 Correct 3 ms 17736 KB Output is correct
6 Correct 4 ms 17736 KB Output is correct
7 Correct 2 ms 17736 KB Output is correct
8 Correct 3 ms 17736 KB Output is correct
9 Correct 4 ms 17736 KB Output is correct
10 Correct 3 ms 17736 KB Output is correct
11 Correct 4 ms 17736 KB Output is correct
12 Correct 5273 ms 23448 KB Output is correct
13 Correct 8763 ms 23448 KB Output is correct
14 Correct 1124 ms 23448 KB Output is correct
15 Correct 11941 ms 23448 KB Output is correct
16 Correct 894 ms 28392 KB Output is correct
17 Correct 5070 ms 28392 KB Output is correct
18 Correct 10502 ms 28820 KB Output is correct
19 Correct 7493 ms 28820 KB Output is correct
20 Correct 6545 ms 28820 KB Output is correct
21 Correct 2 ms 28820 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 28820 KB Output is correct
2 Correct 4 ms 28820 KB Output is correct
3 Correct 4 ms 28820 KB Output is correct
4 Correct 2 ms 28820 KB Output is correct
5 Correct 2 ms 28820 KB Output is correct
6 Correct 3 ms 28820 KB Output is correct
7 Correct 3 ms 28820 KB Output is correct
8 Correct 2 ms 28820 KB Output is correct
9 Correct 4 ms 28820 KB Output is correct
10 Correct 3 ms 28820 KB Output is correct
11 Correct 3 ms 28820 KB Output is correct
12 Correct 2817 ms 28820 KB Output is correct
13 Correct 2008 ms 28820 KB Output is correct
14 Correct 2970 ms 28820 KB Output is correct
15 Correct 3807 ms 28820 KB Output is correct
16 Correct 1519 ms 28820 KB Output is correct
17 Correct 3208 ms 28820 KB Output is correct
18 Correct 2669 ms 28820 KB Output is correct
19 Correct 5123 ms 28820 KB Output is correct
20 Correct 8737 ms 28820 KB Output is correct
21 Correct 973 ms 28820 KB Output is correct
22 Correct 10714 ms 28820 KB Output is correct
23 Correct 788 ms 32760 KB Output is correct
24 Correct 4241 ms 32760 KB Output is correct
25 Correct 9245 ms 43236 KB Output is correct
26 Correct 7638 ms 48660 KB Output is correct
27 Correct 7254 ms 53348 KB Output is correct
28 Execution timed out 8767 ms 257024 KB Time limit exceeded (wall clock)
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 257024 KB Memory limit exceeded
2 Halted 0 ms 0 KB -