oj.uz

Submission #54524

# Submission time Handle Problem Language Result Execution time Memory
54524 2018-07-04T00:30:07 Z KieranHorgan Game (IOI13_game) C++17
80 / 100
 7760 ms 257024 KB 
#pragma GCC optimize("Ofast")
#include "game.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll 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;
    ll st;
    colNode *left, *right;
    colNode(int lv, int rv): left(NULL), right(NULL), st(0) {l=lv; r=rv;};
};
set<pair<int, int>> isNew;
ll 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) return cur->st;
    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) 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));
        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);
}
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);
    }
    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);
}
ll 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) return query(nx, ny, cur->col);
    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;
    
    // cerr << endl;
    // cerr << endl;
    return query(P, U+1, Q, V+1, &root);;
}

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:25:21: warning: 'colNode::right' will be initialized after [-Wreorder]
     colNode *left, *right;
                     ^~~~~
game.cpp:24:8: warning:   'long long int colNode::st' [-Wreorder]
     ll st;
        ^~
game.cpp:26: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 2 ms 248 KB Output is correct
2 Correct 3 ms 484 KB Output is correct
3 Correct 3 ms 544 KB Output is correct
4 Correct 2 ms 544 KB Output is correct
5 Correct 2 ms 544 KB Output is correct
6 Correct 3 ms 544 KB Output is correct
7 Correct 2 ms 544 KB Output is correct
8 Correct 2 ms 548 KB Output is correct
9 Correct 3 ms 632 KB Output is correct
10 Correct 3 ms 692 KB Output is correct
11 Correct 2 ms 692 KB Output is correct
12 Correct 2 ms 692 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 692 KB Output is correct
2 Correct 3 ms 692 KB Output is correct
3 Correct 2 ms 692 KB Output is correct
4 Correct 698 ms 15112 KB Output is correct
5 Correct 465 ms 19412 KB Output is correct
6 Correct 900 ms 20956 KB Output is correct
7 Correct 886 ms 23940 KB Output is correct
8 Correct 509 ms 23940 KB Output is correct
9 Correct 963 ms 24088 KB Output is correct
10 Correct 698 ms 24088 KB Output is correct
11 Correct 2 ms 24088 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 24088 KB Output is correct
2 Correct 3 ms 24088 KB Output is correct
3 Correct 3 ms 24088 KB Output is correct
4 Correct 2 ms 24088 KB Output is correct
5 Correct 2 ms 24088 KB Output is correct
6 Correct 3 ms 24088 KB Output is correct
7 Correct 2 ms 24088 KB Output is correct
8 Correct 2 ms 24088 KB Output is correct
9 Correct 3 ms 24088 KB Output is correct
10 Correct 3 ms 24088 KB Output is correct
11 Correct 3 ms 24088 KB Output is correct
12 Correct 1287 ms 30880 KB Output is correct
13 Correct 3034 ms 30880 KB Output is correct
14 Correct 361 ms 30880 KB Output is correct
15 Correct 3153 ms 30880 KB Output is correct
16 Correct 349 ms 30880 KB Output is correct
17 Correct 1423 ms 30880 KB Output is correct
18 Correct 2401 ms 30880 KB Output is correct
19 Correct 2296 ms 30880 KB Output is correct
20 Correct 1915 ms 30880 KB Output is correct
21 Correct 2 ms 30880 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 30880 KB Output is correct
2 Correct 3 ms 30880 KB Output is correct
3 Correct 3 ms 30880 KB Output is correct
4 Correct 2 ms 30880 KB Output is correct
5 Correct 2 ms 30880 KB Output is correct
6 Correct 3 ms 30880 KB Output is correct
7 Correct 2 ms 30880 KB Output is correct
8 Correct 2 ms 30880 KB Output is correct
9 Correct 2 ms 30880 KB Output is correct
10 Correct 2 ms 30880 KB Output is correct
11 Correct 2 ms 30880 KB Output is correct
12 Correct 755 ms 30880 KB Output is correct
13 Correct 436 ms 30880 KB Output is correct
14 Correct 807 ms 30880 KB Output is correct
15 Correct 951 ms 30880 KB Output is correct
16 Correct 554 ms 30880 KB Output is correct
17 Correct 905 ms 30880 KB Output is correct
18 Correct 808 ms 30880 KB Output is correct
19 Correct 1142 ms 31068 KB Output is correct
20 Correct 2732 ms 31068 KB Output is correct
21 Correct 459 ms 31068 KB Output is correct
22 Correct 3208 ms 31068 KB Output is correct
23 Correct 307 ms 31068 KB Output is correct
24 Correct 1351 ms 31068 KB Output is correct
25 Correct 2432 ms 31068 KB Output is correct
26 Correct 1961 ms 31068 KB Output is correct
27 Correct 1772 ms 31068 KB Output is correct
28 Correct 1016 ms 78732 KB Output is correct
29 Correct 1911 ms 78732 KB Output is correct
30 Correct 5350 ms 118972 KB Output is correct
31 Correct 5131 ms 132760 KB Output is correct
32 Correct 622 ms 132760 KB Output is correct
33 Correct 1059 ms 132760 KB Output is correct
34 Correct 477 ms 132760 KB Output is correct
35 Correct 1962 ms 132760 KB Output is correct
36 Correct 3646 ms 132760 KB Output is correct
37 Correct 2874 ms 132760 KB Output is correct
38 Correct 2715 ms 132760 KB Output is correct
39 Correct 2671 ms 132760 KB Output is correct
40 Correct 4 ms 132760 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 132760 KB Output is correct
2 Correct 3 ms 132760 KB Output is correct
3 Correct 3 ms 132760 KB Output is correct
4 Correct 2 ms 132760 KB Output is correct
5 Correct 2 ms 132760 KB Output is correct
6 Correct 3 ms 132760 KB Output is correct
7 Correct 3 ms 132760 KB Output is correct
8 Correct 2 ms 132760 KB Output is correct
9 Correct 2 ms 132760 KB Output is correct
10 Correct 2 ms 132760 KB Output is correct
11 Correct 2 ms 132760 KB Output is correct
12 Correct 722 ms 132760 KB Output is correct
13 Correct 486 ms 132760 KB Output is correct
14 Correct 857 ms 132760 KB Output is correct
15 Correct 1002 ms 132760 KB Output is correct
16 Correct 592 ms 132760 KB Output is correct
17 Correct 957 ms 132760 KB Output is correct
18 Correct 712 ms 132760 KB Output is correct
19 Correct 1146 ms 132760 KB Output is correct
20 Correct 2913 ms 132760 KB Output is correct
21 Correct 436 ms 132760 KB Output is correct
22 Correct 3523 ms 132760 KB Output is correct
23 Correct 332 ms 132760 KB Output is correct
24 Correct 1355 ms 132760 KB Output is correct
25 Correct 2641 ms 132760 KB Output is correct
26 Correct 2070 ms 132760 KB Output is correct
27 Correct 1957 ms 132760 KB Output is correct
28 Correct 892 ms 132760 KB Output is correct
29 Correct 2005 ms 132760 KB Output is correct
30 Correct 5454 ms 132760 KB Output is correct
31 Correct 5084 ms 132804 KB Output is correct
32 Correct 650 ms 132804 KB Output is correct
33 Correct 1026 ms 132804 KB Output is correct
34 Correct 480 ms 132804 KB Output is correct
35 Correct 1855 ms 132804 KB Output is correct
36 Correct 3457 ms 132804 KB Output is correct
37 Correct 2817 ms 132804 KB Output is correct
38 Correct 2919 ms 132804 KB Output is correct
39 Correct 1414 ms 154052 KB Output is correct
40 Correct 3338 ms 154052 KB Output is correct
41 Correct 7760 ms 248768 KB Output is correct
42 Runtime error 6845 ms 257024 KB Memory limit exceeded
43 Halted 0 ms 0 KB -