oj.uz

Submission #54469

# Submission time Handle Problem Language Result Execution time Memory
54469 2018-07-03T14:45:36 Z KieranHorgan Game (IOI13_game) C++17
63 / 100
 12490 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 2 ms 248 KB Output is correct
2 Correct 4 ms 612 KB Output is correct
3 Correct 5 ms 612 KB Output is correct
4 Correct 3 ms 612 KB Output is correct
5 Correct 2 ms 616 KB Output is correct
6 Correct 6 ms 764 KB Output is correct
7 Correct 2 ms 764 KB Output is correct
8 Correct 3 ms 772 KB Output is correct
9 Correct 3 ms 820 KB Output is correct
10 Correct 3 ms 820 KB Output is correct
11 Correct 3 ms 820 KB Output is correct
12 Correct 2 ms 820 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 820 KB Output is correct
2 Correct 2 ms 820 KB Output is correct
3 Correct 2 ms 820 KB Output is correct
4 Correct 3306 ms 21704 KB Output is correct
5 Correct 2277 ms 26084 KB Output is correct
6 Correct 2294 ms 27800 KB Output is correct
7 Correct 2988 ms 32176 KB Output is correct
8 Correct 1493 ms 32176 KB Output is correct
9 Correct 2874 ms 41380 KB Output is correct
10 Correct 3655 ms 45620 KB Output is correct
11 Correct 3 ms 45620 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 45620 KB Output is correct
2 Correct 6 ms 45620 KB Output is correct
3 Correct 4 ms 45620 KB Output is correct
4 Correct 2 ms 45620 KB Output is correct
5 Correct 2 ms 45620 KB Output is correct
6 Correct 4 ms 45620 KB Output is correct
7 Correct 3 ms 45620 KB Output is correct
8 Correct 2 ms 45620 KB Output is correct
9 Correct 4 ms 45620 KB Output is correct
10 Correct 3 ms 45620 KB Output is correct
11 Correct 4 ms 45620 KB Output is correct
12 Correct 4987 ms 58556 KB Output is correct
13 Correct 9198 ms 58556 KB Output is correct
14 Correct 1249 ms 58556 KB Output is correct
15 Correct 12490 ms 62544 KB Output is correct
16 Correct 896 ms 81100 KB Output is correct
17 Correct 5625 ms 81100 KB Output is correct
18 Correct 9449 ms 91556 KB Output is correct
19 Correct 7531 ms 97072 KB Output is correct
20 Correct 6990 ms 101860 KB Output is correct
21 Correct 2 ms 101860 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 101860 KB Output is correct
2 Correct 4 ms 101860 KB Output is correct
3 Correct 5 ms 101860 KB Output is correct
4 Correct 2 ms 101860 KB Output is correct
5 Correct 2 ms 101860 KB Output is correct
6 Correct 4 ms 101860 KB Output is correct
7 Correct 2 ms 101860 KB Output is correct
8 Correct 2 ms 101860 KB Output is correct
9 Correct 4 ms 101860 KB Output is correct
10 Correct 3 ms 101860 KB Output is correct
11 Correct 3 ms 101860 KB Output is correct
12 Correct 3350 ms 101860 KB Output is correct
13 Correct 1873 ms 101860 KB Output is correct
14 Correct 2126 ms 101860 KB Output is correct
15 Correct 2661 ms 105812 KB Output is correct
16 Correct 1391 ms 105812 KB Output is correct
17 Correct 2723 ms 114896 KB Output is correct
18 Correct 2331 ms 119048 KB Output is correct
19 Correct 5728 ms 132104 KB Output is correct
20 Correct 8968 ms 132104 KB Output is correct
21 Correct 1130 ms 132104 KB Output is correct
22 Correct 11130 ms 135868 KB Output is correct
23 Correct 737 ms 154476 KB Output is correct
24 Correct 4495 ms 154476 KB Output is correct
25 Correct 9441 ms 165164 KB Output is correct
26 Correct 7745 ms 170700 KB Output is correct
27 Correct 7749 ms 175392 KB Output is correct
28 Execution timed out 8539 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 3 ms 257024 KB Memory limit exceeded
2 Halted 0 ms 0 KB -