oj.uz

Submission #54471

# Submission time Handle Problem Language Result Execution time Memory
54471 2018-07-03T14:51:19 Z KieranHorgan Game (IOI13_game) C++17
63 / 100
 11703 ms 257024 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) {
            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];
    }
    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);
        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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 5 ms 484 KB Output is correct
3 Correct 4 ms 524 KB Output is correct
4 Correct 2 ms 524 KB Output is correct
5 Correct 2 ms 556 KB Output is correct
6 Correct 4 ms 604 KB Output is correct
7 Correct 2 ms 604 KB Output is correct
8 Correct 2 ms 604 KB Output is correct
9 Correct 5 ms 668 KB Output is correct
10 Correct 3 ms 760 KB Output is correct
11 Correct 5 ms 812 KB Output is correct
12 Correct 3 ms 812 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 812 KB Output is correct
2 Correct 2 ms 812 KB Output is correct
3 Correct 2 ms 812 KB Output is correct
4 Correct 3027 ms 21616 KB Output is correct
5 Correct 2218 ms 26096 KB Output is correct
6 Correct 2153 ms 27748 KB Output is correct
7 Correct 2628 ms 32440 KB Output is correct
8 Correct 1631 ms 32440 KB Output is correct
9 Correct 2429 ms 41168 KB Output is correct
10 Correct 2716 ms 45520 KB Output is correct
11 Correct 2 ms 45520 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 45520 KB Output is correct
2 Correct 4 ms 45520 KB Output is correct
3 Correct 6 ms 45520 KB Output is correct
4 Correct 2 ms 45520 KB Output is correct
5 Correct 2 ms 45520 KB Output is correct
6 Correct 4 ms 45520 KB Output is correct
7 Correct 2 ms 45520 KB Output is correct
8 Correct 2 ms 45520 KB Output is correct
9 Correct 3 ms 45520 KB Output is correct
10 Correct 3 ms 45520 KB Output is correct
11 Correct 3 ms 45520 KB Output is correct
12 Correct 5018 ms 58712 KB Output is correct
13 Correct 8398 ms 58712 KB Output is correct
14 Correct 986 ms 58712 KB Output is correct
15 Correct 11703 ms 62400 KB Output is correct
16 Correct 975 ms 81324 KB Output is correct
17 Correct 4986 ms 81324 KB Output is correct
18 Correct 9368 ms 91784 KB Output is correct
19 Correct 7284 ms 97168 KB Output is correct
20 Correct 6715 ms 101880 KB Output is correct
21 Correct 2 ms 101880 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 101880 KB Output is correct
2 Correct 4 ms 101880 KB Output is correct
3 Correct 4 ms 101880 KB Output is correct
4 Correct 2 ms 101880 KB Output is correct
5 Correct 2 ms 101880 KB Output is correct
6 Correct 3 ms 101880 KB Output is correct
7 Correct 2 ms 101880 KB Output is correct
8 Correct 2 ms 101880 KB Output is correct
9 Correct 4 ms 101880 KB Output is correct
10 Correct 3 ms 101880 KB Output is correct
11 Correct 4 ms 101880 KB Output is correct
12 Correct 3264 ms 101880 KB Output is correct
13 Correct 1979 ms 101880 KB Output is correct
14 Correct 2032 ms 101880 KB Output is correct
15 Correct 2974 ms 105660 KB Output is correct
16 Correct 1417 ms 105660 KB Output is correct
17 Correct 3044 ms 114952 KB Output is correct
18 Correct 2730 ms 119056 KB Output is correct
19 Correct 5230 ms 132168 KB Output is correct
20 Correct 8710 ms 132168 KB Output is correct
21 Correct 1145 ms 132168 KB Output is correct
22 Correct 11500 ms 135956 KB Output is correct
23 Correct 818 ms 154672 KB Output is correct
24 Correct 4678 ms 154672 KB Output is correct
25 Correct 9355 ms 165208 KB Output is correct
26 Correct 7624 ms 170680 KB Output is correct
27 Correct 7577 ms 175440 KB Output is correct
28 Execution timed out 8135 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 -