oj.uz

Submission #54177

# Submission time Handle Problem Language Result Execution time Memory
54177 2018-07-02T16:24:45 Z KieranHorgan Game (IOI13_game) C++17
37 / 100
 13000 ms 257024 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) 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 {
    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];
        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 612 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 688 KB Output is correct
7 Correct 2 ms 688 KB Output is correct
8 Correct 2 ms 688 KB Output is correct
9 Correct 4 ms 828 KB Output is correct
10 Correct 4 ms 828 KB Output is correct
11 Correct 3 ms 828 KB Output is correct
12 Correct 3 ms 828 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 828 KB Output is correct
2 Correct 2 ms 828 KB Output is correct
3 Correct 2 ms 828 KB Output is correct
4 Correct 3157 ms 17332 KB Output is correct
5 Correct 2284 ms 17616 KB Output is correct
6 Correct 2475 ms 17616 KB Output is correct
7 Correct 3404 ms 17616 KB Output is correct
8 Correct 1530 ms 17616 KB Output is correct
9 Correct 2601 ms 17616 KB Output is correct
10 Correct 2801 ms 17616 KB Output is correct
11 Correct 2 ms 17616 KB Output is correct

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 17616 KB Output is correct
2 Correct 4 ms 17616 KB Output is correct
3 Correct 5 ms 17616 KB Output is correct
4 Correct 2 ms 17616 KB Output is correct
5 Correct 2 ms 17616 KB Output is correct
6 Correct 4 ms 17616 KB Output is correct
7 Correct 2 ms 17616 KB Output is correct
8 Correct 2 ms 17616 KB Output is correct
9 Correct 3 ms 17616 KB Output is correct
10 Correct 3 ms 17616 KB Output is correct
11 Correct 3 ms 17616 KB Output is correct
12 Correct 5754 ms 26636 KB Output is correct
13 Correct 10237 ms 26636 KB Output is correct
14 Correct 1267 ms 26636 KB Output is correct
15 Execution timed out 13048 ms 30244 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 30244 KB Output is correct
2 Correct 4 ms 30244 KB Output is correct
3 Correct 4 ms 30244 KB Output is correct
4 Correct 2 ms 30244 KB Output is correct
5 Correct 2 ms 30244 KB Output is correct
6 Correct 3 ms 30244 KB Output is correct
7 Correct 2 ms 30244 KB Output is correct
8 Correct 2 ms 30244 KB Output is correct
9 Correct 4 ms 30244 KB Output is correct
10 Correct 3 ms 30244 KB Output is correct
11 Correct 3 ms 30244 KB Output is correct
12 Correct 2999 ms 33532 KB Output is correct
13 Correct 2271 ms 34040 KB Output is correct
14 Correct 2191 ms 34040 KB Output is correct
15 Correct 2955 ms 34040 KB Output is correct
16 Correct 1465 ms 34040 KB Output is correct
17 Correct 2658 ms 34040 KB Output is correct
18 Correct 2907 ms 34040 KB Output is correct
19 Correct 5820 ms 42764 KB Output is correct
20 Correct 9537 ms 42764 KB Output is correct
21 Correct 1098 ms 42764 KB Output is correct
22 Correct 12338 ms 46672 KB Output is correct
23 Correct 873 ms 65424 KB Output is correct
24 Correct 4836 ms 65424 KB Output is correct
25 Correct 9661 ms 75924 KB Output is correct
26 Correct 7299 ms 81404 KB Output is correct
27 Correct 7196 ms 86024 KB Output is correct
28 Execution timed out 8212 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 -