oj.uz

Submission #54164

# Submission time Handle Problem Language Result Execution time Memory
54164 2018-07-02T14:41:05 Z KieranHorgan Game (IOI13_game) C++17
37 / 100
 13000 ms 16720 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) {
        if(l>i || r<=i) return;
        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 3 ms 376 KB Output is correct
2 Correct 5 ms 488 KB Output is correct
3 Correct 5 ms 584 KB Output is correct
4 Correct 2 ms 584 KB Output is correct
5 Correct 2 ms 584 KB Output is correct
6 Correct 4 ms 656 KB Output is correct
7 Correct 3 ms 656 KB Output is correct
8 Correct 2 ms 656 KB Output is correct
9 Correct 3 ms 748 KB Output is correct
10 Correct 3 ms 748 KB Output is correct
11 Correct 3 ms 748 KB Output is correct
12 Correct 3 ms 748 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 748 KB Output is correct
2 Correct 2 ms 748 KB Output is correct
3 Correct 2 ms 748 KB Output is correct
4 Correct 5374 ms 16268 KB Output is correct
5 Correct 3346 ms 16504 KB Output is correct
6 Correct 3544 ms 16504 KB Output is correct
7 Correct 3543 ms 16504 KB Output is correct
8 Correct 2367 ms 16504 KB Output is correct
9 Correct 3298 ms 16504 KB Output is correct
10 Correct 4335 ms 16504 KB Output is correct
11 Correct 2 ms 16504 KB Output is correct

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16504 KB Output is correct
2 Correct 4 ms 16504 KB Output is correct
3 Correct 4 ms 16504 KB Output is correct
4 Correct 2 ms 16504 KB Output is correct
5 Correct 2 ms 16504 KB Output is correct
6 Correct 4 ms 16504 KB Output is correct
7 Correct 3 ms 16504 KB Output is correct
8 Correct 3 ms 16504 KB Output is correct
9 Correct 3 ms 16504 KB Output is correct
10 Correct 3 ms 16504 KB Output is correct
11 Correct 3 ms 16504 KB Output is correct
12 Execution timed out 13018 ms 16504 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 16504 KB Output is correct
2 Correct 4 ms 16504 KB Output is correct
3 Correct 4 ms 16504 KB Output is correct
4 Correct 2 ms 16504 KB Output is correct
5 Correct 3 ms 16504 KB Output is correct
6 Correct 5 ms 16504 KB Output is correct
7 Correct 4 ms 16504 KB Output is correct
8 Correct 2 ms 16504 KB Output is correct
9 Correct 4 ms 16504 KB Output is correct
10 Correct 3 ms 16504 KB Output is correct
11 Correct 3 ms 16504 KB Output is correct
12 Correct 5499 ms 16504 KB Output is correct
13 Correct 3464 ms 16720 KB Output is correct
14 Correct 3613 ms 16720 KB Output is correct
15 Correct 4127 ms 16720 KB Output is correct
16 Correct 1822 ms 16720 KB Output is correct
17 Correct 3749 ms 16720 KB Output is correct
18 Correct 3554 ms 16720 KB Output is correct
19 Execution timed out 13079 ms 16720 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 16720 KB Output is correct
2 Correct 6 ms 16720 KB Output is correct
3 Correct 4 ms 16720 KB Output is correct
4 Correct 2 ms 16720 KB Output is correct
5 Correct 2 ms 16720 KB Output is correct
6 Correct 4 ms 16720 KB Output is correct
7 Correct 2 ms 16720 KB Output is correct
8 Correct 2 ms 16720 KB Output is correct
9 Correct 3 ms 16720 KB Output is correct
10 Correct 3 ms 16720 KB Output is correct
11 Correct 4 ms 16720 KB Output is correct
12 Correct 5515 ms 16720 KB Output is correct
13 Correct 3230 ms 16720 KB Output is correct
14 Correct 3262 ms 16720 KB Output is correct
15 Correct 3967 ms 16720 KB Output is correct
16 Correct 2503 ms 16720 KB Output is correct
17 Correct 3784 ms 16720 KB Output is correct
18 Correct 3810 ms 16720 KB Output is correct
19 Execution timed out 13011 ms 16720 KB Time limit exceeded
20 Halted 0 ms 0 KB -