oj.uz

Submission #54520

# Submission time Handle Problem Language Result Execution time Memory
54520 2018-07-04T00:04:22 Z KieranHorgan Game (IOI13_game) C++17
80 / 100
 5223 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 colNode {
    int l, r, st;
    colNode *left, *right;
    colNode(int lv, int rv): left(NULL), right(NULL), st(0) {l=lv; r=rv;};
};
set<pair<int, int>> isNew;
int query(int x, int y, colNode *cur) {
    if(cur == NULL) return 0;
    if(x >= cur->r || y <= cur->l) return 0;
    if(y >= cur->r && x <= cur->l) {
        int temp = cur->st;
        // cerr << "  " << cur->l << " " << cur->r << ": " << temp << endl;
        return temp;
    }
    if(cur->right==NULL) return query(x, y, cur->left);
    if(cur->left==NULL) return query(x, y, cur->right);
    return gcd2(query(x, y, cur->left),
                query(x, y, cur->right));
}
void update(int j, int val, colNode *cur, colNode *rowL, colNode *rowR) {
    if(cur == NULL) return;
    if(j < cur->l || j >= cur->r) {
        // cerr << "  " << cur->l << " " << cur->r << ": " << j << endl;
        return;
    }
    if(cur->l + 1 == cur->r) {
        if(rowL == NULL && rowR == NULL) cur->st = val;
        else if(rowL == NULL) cur->st = query(j, j+1, rowR);
        else if(rowR == NULL) cur->st = query(j, j+1, rowL);
        else cur->st = gcd2(query(j, j+1, rowL), query(j, j+1, rowR));
        // cerr << "  " << cur->l << " " << cur->r << ": " << val << endl;
        // cerr << cur->l << " " << cur->r << ":    \t" << cur->st << endl;
        //Check if merging rows
        return;
    }
    int mid = (cur->l + cur->r)/2;
    if(j < mid) {
        if(cur->left == NULL) {
            cur->left = new colNode(j, j+1);
        } else if(cur->left->l != cur->l || cur->left->r != mid) {
            int mid2 = (cur->l+mid)/2;
            if(cur->left->l < mid2) {
                cur->left->left = new colNode(cur->left->l, cur->left->r);
                cur->left->left->st = cur->left->st;
            } else {
                cur->left->right = new colNode(cur->left->l, cur->left->r);
                cur->left->right->st = cur->left->st;
            }
            cur->left->l = cur->l;
            cur->left->r = mid;
        }
        update(j, val, cur->left, rowL, rowR);
    } else {
        if(cur->right == NULL) {
            cur->right = new colNode(mid, cur->r);
        } else if(cur->right->l != mid || cur->right->r != cur->r) {
            int mid2 = (cur->r+mid)/2;
            if(cur->right->l < mid2) {
                cur->right->left = new colNode(cur->right->l, cur->right->r);
                cur->right->left->st = cur->right->st;
            } else {
                cur->right->right = new colNode(cur->right->l, cur->right->r);
                cur->right->right->st = cur->right->st;
            }
            cur->right->l = mid;
            cur->right->r = cur->r;
        }
        update(j, val, cur->right, rowL, rowR);
    }
    if(cur->left==NULL) cur->st = cur->right->st;
    else if(cur->right==NULL) cur->st = cur->left->st;
    else cur->st = gcd2(cur->left->st, cur->right->st);
    // cerr << "  " << cur->l << " " << cur->r << ": " << cur->st << endl;
}
struct rowNode {
    int l, r;
    rowNode *left, *right;
    colNode *col;
    rowNode(int lv, int rv): left(NULL), right(NULL) {l=lv; r=rv; col = new colNode(0, C);};
};
void update(int i, int j, int val, rowNode *cur) {
    if(cur == NULL) return;
    if(i < cur->l || i >= cur->r) return;
    int mid = (cur->l + cur->r)/2;
    
    if(cur->l+1 == cur-> r) {

    } else if(i < mid) {
        if(cur->left == NULL) {
            cur->left = new rowNode(cur->l, mid);
        } else if(cur->left->l != cur->l || cur->left->r != mid) {
            int mid2 = (cur->l+mid)/2;
            if(cur->left->l < mid2) {
                cur->left->left = new rowNode(cur->left->l, cur->left->r);
                cur->left->left->col = cur->left->col;
            } else {
                cur->left->right = new rowNode(cur->left->l, cur->left->r);
                cur->left->right->col = cur->left->col;
            }
            cur->left->l = cur->l;
            cur->left->r = mid;
        }
        update(i, j, val, cur->left);
    } else {
        if(cur->right == NULL) {
            cur->right = new rowNode(mid, cur->r);
        } else if(cur->right->l != mid || cur->right->r != cur->r) {
            int mid2 = (cur->r+mid)/2;
            if(cur->right->l < mid2) {
                cur->right->left = new rowNode(cur->right->l, cur->right->r);
                cur->right->left->col = cur->right->col;
            } else {
                cur->right->right = new rowNode(cur->right->l, cur->right->r);
                cur->right->right->col = cur->right->col;
            }
            cur->right->l = mid;
            cur->right->r = cur->r;
        }
        update(i, j, val, cur->right);
    }
    // cerr << cur->l << " " << cur->r << ": " << endl;
    if(cur->left == NULL && cur->right == NULL) update(j, val, cur->col, NULL, NULL);
    else if(cur->left == NULL) update(j, val, cur->col, NULL, cur->right->col);
    else if(cur->right == NULL) update(j, val, cur->col, cur->left->col, NULL);
    else update(j, val, cur->col, cur->left->col, cur->right->col);
        // cerr << cur->l << " " << cur->r << ":    \t" << cur->st << endl;
}
int query(int x, int y, int nx, int ny, rowNode *cur) {
    if(cur == NULL) return 0;
    if(x >= cur->r || y <= cur->l) return 0;
    if(y >= cur->r && x <= cur->l) {
        int temp = query(nx, ny, cur->col);
        // cerr << cur->l << " " << cur->r << ": " << temp << endl;
        return temp;
    }
    if(cur->right==NULL) return query(x, y, nx, ny, cur->left);
    if(cur->left==NULL) return query(x, y, nx, ny, cur->right);
    return gcd2(query(x, y, nx, ny, cur->left),
                query(x, y, nx, ny, cur->right));
}

rowNode root(0,1);

void init(signed r, signed c) {
    R = r;
    C = c;
    root = *(new rowNode(0, R));
}

void update(signed P, signed Q, long long K) {
    // cerr << "Update:" << endl;
    update(P, Q, K, &root);
    // cerr << endl;
    // update(Q, K, &root);
    // cerr << endl;
}
 
long long calculate(signed P, signed Q, signed U, signed V) {
    // cerr << "Query:" << endl;
    int x = query(P, U+1, Q, V+1, &root);
    // cerr << endl;
    // cerr << endl;
    return x;
}

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;
      ^~~
game.cpp: In constructor 'colNode::colNode(long long int, long long int)':
game.cpp:23:21: warning: 'colNode::right' will be initialized after [-Wreorder]
     colNode *left, *right;
                     ^~~~~
game.cpp:22:15: warning:   'long long int colNode::st' [-Wreorder]
     int l, r, st;
               ^~
game.cpp:24:5: warning:   when initialized here [-Wreorder]
     colNode(int lv, int rv): left(NULL), right(NULL), st(0) {l=lv; r=rv;};
     ^~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 504 KB Output is correct
2 Correct 4 ms 616 KB Output is correct
3 Correct 4 ms 684 KB Output is correct
4 Correct 3 ms 684 KB Output is correct
5 Correct 2 ms 684 KB Output is correct
6 Correct 3 ms 788 KB Output is correct
7 Correct 2 ms 788 KB Output is correct
8 Correct 3 ms 788 KB Output is correct
9 Correct 3 ms 788 KB Output is correct
10 Correct 4 ms 788 KB Output is correct
11 Correct 2 ms 788 KB Output is correct
12 Correct 2 ms 788 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 788 KB Output is correct
2 Correct 3 ms 788 KB Output is correct
3 Correct 2 ms 788 KB Output is correct
4 Correct 703 ms 15244 KB Output is correct
5 Correct 438 ms 19420 KB Output is correct
6 Correct 719 ms 20768 KB Output is correct
7 Correct 831 ms 25352 KB Output is correct
8 Correct 505 ms 25548 KB Output is correct
9 Correct 770 ms 27768 KB Output is correct
10 Correct 625 ms 27768 KB Output is correct
11 Correct 2 ms 27768 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 27768 KB Output is correct
2 Correct 2 ms 27768 KB Output is correct
3 Correct 2 ms 27768 KB Output is correct
4 Correct 2 ms 27768 KB Output is correct
5 Correct 2 ms 27768 KB Output is correct
6 Correct 2 ms 27768 KB Output is correct
7 Correct 3 ms 27768 KB Output is correct
8 Correct 2 ms 27768 KB Output is correct
9 Correct 2 ms 27768 KB Output is correct
10 Correct 2 ms 27768 KB Output is correct
11 Correct 2 ms 27768 KB Output is correct
12 Correct 1066 ms 34696 KB Output is correct
13 Correct 2629 ms 34696 KB Output is correct
14 Correct 390 ms 34696 KB Output is correct
15 Correct 3253 ms 34696 KB Output is correct
16 Correct 341 ms 34696 KB Output is correct
17 Correct 1217 ms 34696 KB Output is correct
18 Correct 2266 ms 34720 KB Output is correct
19 Correct 2056 ms 34720 KB Output is correct
20 Correct 1802 ms 34720 KB Output is correct
21 Correct 2 ms 34720 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 34720 KB Output is correct
2 Correct 3 ms 34720 KB Output is correct
3 Correct 3 ms 34720 KB Output is correct
4 Correct 2 ms 34720 KB Output is correct
5 Correct 2 ms 34720 KB Output is correct
6 Correct 3 ms 34720 KB Output is correct
7 Correct 2 ms 34720 KB Output is correct
8 Correct 3 ms 34720 KB Output is correct
9 Correct 2 ms 34720 KB Output is correct
10 Correct 2 ms 34720 KB Output is correct
11 Correct 4 ms 34720 KB Output is correct
12 Correct 748 ms 34720 KB Output is correct
13 Correct 474 ms 34720 KB Output is correct
14 Correct 774 ms 34720 KB Output is correct
15 Correct 782 ms 34720 KB Output is correct
16 Correct 492 ms 34720 KB Output is correct
17 Correct 745 ms 34720 KB Output is correct
18 Correct 621 ms 34720 KB Output is correct
19 Correct 1043 ms 34720 KB Output is correct
20 Correct 2689 ms 34720 KB Output is correct
21 Correct 350 ms 34720 KB Output is correct
22 Correct 3282 ms 34720 KB Output is correct
23 Correct 303 ms 34720 KB Output is correct
24 Correct 1169 ms 34720 KB Output is correct
25 Correct 2188 ms 34740 KB Output is correct
26 Correct 2306 ms 34740 KB Output is correct
27 Correct 1695 ms 34740 KB Output is correct
28 Correct 832 ms 82772 KB Output is correct
29 Correct 1907 ms 82772 KB Output is correct
30 Correct 5055 ms 122964 KB Output is correct
31 Correct 5035 ms 143796 KB Output is correct
32 Correct 653 ms 143796 KB Output is correct
33 Correct 994 ms 143796 KB Output is correct
34 Correct 465 ms 143796 KB Output is correct
35 Correct 1770 ms 143796 KB Output is correct
36 Correct 3141 ms 143796 KB Output is correct
37 Correct 2532 ms 143796 KB Output is correct
38 Correct 2594 ms 147476 KB Output is correct
39 Correct 2141 ms 147476 KB Output is correct
40 Correct 2 ms 147476 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 147476 KB Output is correct
2 Correct 2 ms 147476 KB Output is correct
3 Correct 2 ms 147476 KB Output is correct
4 Correct 2 ms 147476 KB Output is correct
5 Correct 2 ms 147476 KB Output is correct
6 Correct 3 ms 147476 KB Output is correct
7 Correct 2 ms 147476 KB Output is correct
8 Correct 3 ms 147476 KB Output is correct
9 Correct 2 ms 147476 KB Output is correct
10 Correct 2 ms 147476 KB Output is correct
11 Correct 2 ms 147476 KB Output is correct
12 Correct 658 ms 147476 KB Output is correct
13 Correct 423 ms 147476 KB Output is correct
14 Correct 689 ms 147476 KB Output is correct
15 Correct 882 ms 147476 KB Output is correct
16 Correct 484 ms 147476 KB Output is correct
17 Correct 894 ms 147476 KB Output is correct
18 Correct 800 ms 147476 KB Output is correct
19 Correct 1207 ms 154176 KB Output is correct
20 Correct 2708 ms 154176 KB Output is correct
21 Correct 350 ms 154176 KB Output is correct
22 Correct 3012 ms 162844 KB Output is correct
23 Correct 281 ms 170940 KB Output is correct
24 Correct 1178 ms 170940 KB Output is correct
25 Correct 2156 ms 181520 KB Output is correct
26 Correct 2200 ms 186852 KB Output is correct
27 Correct 1808 ms 191644 KB Output is correct
28 Correct 937 ms 250968 KB Output is correct
29 Correct 1897 ms 254720 KB Output is correct
30 Runtime error 5223 ms 257024 KB Memory limit exceeded
31 Halted 0 ms 0 KB -