oj.uz

Submission #54187

# Submission time Handle Problem Language Result Execution time Memory
54187 2018-07-02T16:49:19 Z KieranHorgan Game (IOI13_game) C++17
63 / 100
 11163 ms 257024 KB 
#pragma GCC optimize("Ofast")
#include "game.h"
#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define ll 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<ll, ll> st;
    void update(ll val, int j, colSegmentTree *leftChild=NULL, colSegmentTree *rightChild=NULL, ll 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];
    }
    ll query(int x, int y, ll 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<ll, colSegmentTree> st;
    void update(ll val, int i, int j, ll 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]);
    }
    ll query(int x, int y, int nx, int ny, ll 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 4 ms 612 KB Output is correct
4 Correct 2 ms 612 KB Output is correct
5 Correct 3 ms 612 KB Output is correct
6 Correct 5 ms 644 KB Output is correct
7 Correct 3 ms 644 KB Output is correct
8 Correct 3 ms 644 KB Output is correct
9 Correct 4 ms 672 KB Output is correct
10 Correct 3 ms 672 KB Output is correct
11 Correct 3 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 2 ms 672 KB Output is correct
3 Correct 3 ms 672 KB Output is correct
4 Correct 2845 ms 17208 KB Output is correct
5 Correct 1962 ms 17848 KB Output is correct
6 Correct 2338 ms 17848 KB Output is correct
7 Correct 2734 ms 17848 KB Output is correct
8 Correct 1933 ms 17848 KB Output is correct
9 Correct 2755 ms 17848 KB Output is correct
10 Correct 2864 ms 17848 KB Output is correct
11 Correct 2 ms 17848 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 17848 KB Output is correct
2 Correct 6 ms 17848 KB Output is correct
3 Correct 4 ms 17848 KB Output is correct
4 Correct 2 ms 17848 KB Output is correct
5 Correct 2 ms 17848 KB Output is correct
6 Correct 4 ms 17848 KB Output is correct
7 Correct 2 ms 17848 KB Output is correct
8 Correct 2 ms 17848 KB Output is correct
9 Correct 4 ms 17848 KB Output is correct
10 Correct 3 ms 17848 KB Output is correct
11 Correct 3 ms 17848 KB Output is correct
12 Correct 5141 ms 23300 KB Output is correct
13 Correct 8388 ms 23300 KB Output is correct
14 Correct 1082 ms 23300 KB Output is correct
15 Correct 11163 ms 23300 KB Output is correct
16 Correct 834 ms 28388 KB Output is correct
17 Correct 4535 ms 28388 KB Output is correct
18 Correct 9462 ms 28892 KB Output is correct
19 Correct 7334 ms 28892 KB Output is correct
20 Correct 6871 ms 28892 KB Output is correct
21 Correct 2 ms 28892 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 28892 KB Output is correct
2 Correct 4 ms 28892 KB Output is correct
3 Correct 5 ms 28892 KB Output is correct
4 Correct 2 ms 28892 KB Output is correct
5 Correct 2 ms 28892 KB Output is correct
6 Correct 4 ms 28892 KB Output is correct
7 Correct 2 ms 28892 KB Output is correct
8 Correct 3 ms 28892 KB Output is correct
9 Correct 4 ms 28892 KB Output is correct
10 Correct 4 ms 28892 KB Output is correct
11 Correct 4 ms 28892 KB Output is correct
12 Correct 2958 ms 28892 KB Output is correct
13 Correct 2081 ms 28892 KB Output is correct
14 Correct 2433 ms 28892 KB Output is correct
15 Correct 3091 ms 28892 KB Output is correct
16 Correct 1497 ms 28892 KB Output is correct
17 Correct 2536 ms 28892 KB Output is correct
18 Correct 2568 ms 28892 KB Output is correct
19 Correct 5589 ms 28892 KB Output is correct
20 Correct 8772 ms 28892 KB Output is correct
21 Correct 1002 ms 28892 KB Output is correct
22 Correct 10712 ms 28892 KB Output is correct
23 Correct 835 ms 32572 KB Output is correct
24 Correct 5022 ms 32572 KB Output is correct
25 Correct 10481 ms 43288 KB Output is correct
26 Correct 8119 ms 48668 KB Output is correct
27 Correct 7199 ms 53508 KB Output is correct
28 Execution timed out 8541 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 -