oj.uz

Submission #54470

# Submission time Handle Problem Language Result Execution time Memory
54470 2018-07-03T14:50:19 Z KieranHorgan Game (IOI13_game) C++17
0 / 100
 3 ms 792 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) {
            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);
        st[id] = gcd2(st[id*2], 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) 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) {
            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);
        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) {
            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;
}
 
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);
}

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 Runtime error 3 ms 376 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 500 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 536 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 676 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 792 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -