oj.uz

Submission #54464

# Submission time Handle Problem Language Result Execution time Memory
54464 2018-07-03T14:42:06 Z KieranHorgan Game (IOI13_game) C++17
63 / 100
 11914 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) {
            // 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) {
            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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 5 ms 624 KB Output is correct
3 Correct 4 ms 680 KB Output is correct
4 Correct 2 ms 680 KB Output is correct
5 Correct 3 ms 680 KB Output is correct
6 Correct 4 ms 756 KB Output is correct
7 Correct 2 ms 756 KB Output is correct
8 Correct 2 ms 756 KB Output is correct
9 Correct 4 ms 876 KB Output is correct
10 Correct 3 ms 876 KB Output is correct
11 Correct 3 ms 876 KB Output is correct
12 Correct 2 ms 876 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 876 KB Output is correct
2 Correct 2 ms 876 KB Output is correct
3 Correct 3 ms 876 KB Output is correct
4 Correct 3139 ms 21912 KB Output is correct
5 Correct 2118 ms 26264 KB Output is correct
6 Correct 2458 ms 28068 KB Output is correct
7 Correct 3250 ms 32268 KB Output is correct
8 Correct 1417 ms 32268 KB Output is correct
9 Correct 2493 ms 41248 KB Output is correct
10 Correct 2773 ms 45468 KB Output is correct
11 Correct 2 ms 45468 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 45468 KB Output is correct
2 Correct 4 ms 45468 KB Output is correct
3 Correct 4 ms 45468 KB Output is correct
4 Correct 2 ms 45468 KB Output is correct
5 Correct 2 ms 45468 KB Output is correct
6 Correct 4 ms 45468 KB Output is correct
7 Correct 3 ms 45468 KB Output is correct
8 Correct 2 ms 45468 KB Output is correct
9 Correct 3 ms 45468 KB Output is correct
10 Correct 4 ms 45468 KB Output is correct
11 Correct 4 ms 45468 KB Output is correct
12 Correct 5596 ms 58720 KB Output is correct
13 Correct 8156 ms 58720 KB Output is correct
14 Correct 967 ms 58720 KB Output is correct
15 Correct 10623 ms 62604 KB Output is correct
16 Correct 809 ms 81092 KB Output is correct
17 Correct 4858 ms 81092 KB Output is correct
18 Correct 9401 ms 91660 KB Output is correct
19 Correct 7770 ms 97256 KB Output is correct
20 Correct 7681 ms 101928 KB Output is correct
21 Correct 2 ms 101928 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 101928 KB Output is correct
2 Correct 5 ms 101928 KB Output is correct
3 Correct 4 ms 101928 KB Output is correct
4 Correct 2 ms 101928 KB Output is correct
5 Correct 3 ms 101928 KB Output is correct
6 Correct 5 ms 101928 KB Output is correct
7 Correct 2 ms 101928 KB Output is correct
8 Correct 3 ms 101928 KB Output is correct
9 Correct 3 ms 101928 KB Output is correct
10 Correct 3 ms 101928 KB Output is correct
11 Correct 3 ms 101928 KB Output is correct
12 Correct 2951 ms 101928 KB Output is correct
13 Correct 1951 ms 101928 KB Output is correct
14 Correct 2421 ms 101928 KB Output is correct
15 Correct 2762 ms 105712 KB Output is correct
16 Correct 1630 ms 105712 KB Output is correct
17 Correct 2657 ms 115020 KB Output is correct
18 Correct 3070 ms 119232 KB Output is correct
19 Correct 5583 ms 132076 KB Output is correct
20 Correct 9185 ms 132076 KB Output is correct
21 Correct 1033 ms 132076 KB Output is correct
22 Correct 11914 ms 135836 KB Output is correct
23 Correct 884 ms 154448 KB Output is correct
24 Correct 5390 ms 154448 KB Output is correct
25 Correct 9737 ms 164996 KB Output is correct
26 Correct 7342 ms 170556 KB Output is correct
27 Correct 6991 ms 175100 KB Output is correct
28 Execution timed out 8717 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 -