oj.uz

Submission #54158

# Submission time Handle Problem Language Result Execution time Memory
54158 2018-07-02T13:42:35 Z KieranHorgan Game (IOI13_game) C++17
0 / 100
 7020 ms 73272 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;
}

struct colSegmentTree {
    unordered_map<int, int> st;
    void update(int val, int j, int id=1, int l=0, int r=1000000000) {
        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=1000000000) {
        if(l>=y || r<=x) return 0;
        if(l>=x && r<=y) {
            // cerr << " " << l << " " << r-1 << endl;
            if(st.count(id))
                return st[id];
            return 0;
        }
        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=1000000000) {
        if(l>i || r<=i) return;
        st[id].update(val, j);
        int mid = (l+r)/2;
        if(l+1==r) return;
        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=1000000000) {
        if(l>=y || r<=x) return 0;
        if(l>=x && r<=y) {
            // cerr << l << " " << r-1 << endl;
            if(st.count(id))
                return st[id].query(nx, ny);
            return 0;
        }
        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) {
    /* ... */
}

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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 376 KB Output is correct
2 Incorrect 18 ms 1000 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1000 KB Output is correct
2 Correct 3 ms 1000 KB Output is correct
3 Correct 4 ms 1000 KB Output is correct
4 Correct 7020 ms 69112 KB Output is correct
5 Incorrect 6375 ms 73272 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 73272 KB Output is correct
2 Incorrect 22 ms 73272 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 73272 KB Output is correct
2 Incorrect 15 ms 73272 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 73272 KB Output is correct
2 Incorrect 15 ms 73272 KB Output isn't correct
3 Halted 0 ms 0 KB -