oj.uz

Submission #54529

# Submission time Handle Problem Language Result Execution time Memory
54529 2018-07-04T01:08:35 Z KieranHorgan Game (IOI13_game) C++17
100 / 100
 6897 ms 168812 KB 
#pragma GCC optimize("Ofast")
#include "game.h"
#include <bits/stdc++.h>
using namespace std;
#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, ll 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(j, j+1);
        } 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, ll 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);
        update(i, j, val, cur->left);
    } else {
        if(cur->right == NULL)
            cur->right = new rowNode(mid, 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) {
    update(P, Q, K, &root);
}
 
long long calculate(signed P, signed Q, signed U, signed V) {
    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(int, int)':
game.cpp:24:21: warning: 'colNode::right' will be initialized after [-Wreorder]
     colNode *left, *right;
                     ^~~~~
game.cpp:23:8: warning:   'long long int colNode::st' [-Wreorder]
     ll st;
        ^~
game.cpp:25: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 4 ms 484 KB Output is correct
3 Correct 2 ms 568 KB Output is correct
4 Correct 2 ms 628 KB Output is correct
5 Correct 2 ms 628 KB Output is correct
6 Correct 3 ms 676 KB Output is correct
7 Correct 2 ms 676 KB Output is correct
8 Correct 2 ms 676 KB Output is correct
9 Correct 3 ms 700 KB Output is correct
10 Correct 2 ms 700 KB Output is correct
11 Correct 2 ms 848 KB Output is correct
12 Correct 2 ms 848 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 848 KB Output is correct
2 Correct 2 ms 848 KB Output is correct
3 Correct 2 ms 848 KB Output is correct
4 Correct 691 ms 9600 KB Output is correct
5 Correct 618 ms 9900 KB Output is correct
6 Correct 807 ms 9900 KB Output is correct
7 Correct 862 ms 9900 KB Output is correct
8 Correct 485 ms 9900 KB Output is correct
9 Correct 764 ms 9900 KB Output is correct
10 Correct 648 ms 9900 KB Output is correct
11 Correct 2 ms 9900 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9900 KB Output is correct
2 Correct 3 ms 9900 KB Output is correct
3 Correct 3 ms 9900 KB Output is correct
4 Correct 2 ms 9900 KB Output is correct
5 Correct 2 ms 9900 KB Output is correct
6 Correct 3 ms 9900 KB Output is correct
7 Correct 2 ms 9900 KB Output is correct
8 Correct 2 ms 9900 KB Output is correct
9 Correct 3 ms 9900 KB Output is correct
10 Correct 3 ms 9900 KB Output is correct
11 Correct 2 ms 9900 KB Output is correct
12 Correct 1051 ms 13160 KB Output is correct
13 Correct 2729 ms 13160 KB Output is correct
14 Correct 351 ms 13160 KB Output is correct
15 Correct 3200 ms 13160 KB Output is correct
16 Correct 319 ms 13160 KB Output is correct
17 Correct 1132 ms 13160 KB Output is correct
18 Correct 2163 ms 13160 KB Output is correct
19 Correct 1738 ms 13160 KB Output is correct
20 Correct 1703 ms 13160 KB Output is correct
21 Correct 3 ms 13160 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 13160 KB Output is correct
2 Correct 3 ms 13160 KB Output is correct
3 Correct 3 ms 13160 KB Output is correct
4 Correct 2 ms 13160 KB Output is correct
5 Correct 3 ms 13160 KB Output is correct
6 Correct 3 ms 13160 KB Output is correct
7 Correct 2 ms 13160 KB Output is correct
8 Correct 2 ms 13160 KB Output is correct
9 Correct 2 ms 13160 KB Output is correct
10 Correct 2 ms 13160 KB Output is correct
11 Correct 2 ms 13160 KB Output is correct
12 Correct 693 ms 13160 KB Output is correct
13 Correct 463 ms 13160 KB Output is correct
14 Correct 725 ms 13160 KB Output is correct
15 Correct 799 ms 13160 KB Output is correct
16 Correct 487 ms 13160 KB Output is correct
17 Correct 776 ms 13160 KB Output is correct
18 Correct 662 ms 13160 KB Output is correct
19 Correct 1134 ms 13160 KB Output is correct
20 Correct 2940 ms 13160 KB Output is correct
21 Correct 368 ms 13160 KB Output is correct
22 Correct 3470 ms 13160 KB Output is correct
23 Correct 332 ms 13160 KB Output is correct
24 Correct 1381 ms 13160 KB Output is correct
25 Correct 2275 ms 13160 KB Output is correct
26 Correct 1889 ms 13160 KB Output is correct
27 Correct 1830 ms 13160 KB Output is correct
28 Correct 817 ms 48700 KB Output is correct
29 Correct 2019 ms 48700 KB Output is correct
30 Correct 5085 ms 48700 KB Output is correct
31 Correct 4823 ms 81984 KB Output is correct
32 Correct 606 ms 81984 KB Output is correct
33 Correct 908 ms 81984 KB Output is correct
34 Correct 418 ms 81984 KB Output is correct
35 Correct 1459 ms 81984 KB Output is correct
36 Correct 3372 ms 81984 KB Output is correct
37 Correct 2786 ms 81984 KB Output is correct
38 Correct 2521 ms 81984 KB Output is correct
39 Correct 1881 ms 81984 KB Output is correct
40 Correct 3 ms 81984 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 81984 KB Output is correct
2 Correct 3 ms 81984 KB Output is correct
3 Correct 3 ms 81984 KB Output is correct
4 Correct 2 ms 81984 KB Output is correct
5 Correct 3 ms 81984 KB Output is correct
6 Correct 2 ms 81984 KB Output is correct
7 Correct 2 ms 81984 KB Output is correct
8 Correct 2 ms 81984 KB Output is correct
9 Correct 3 ms 81984 KB Output is correct
10 Correct 2 ms 81984 KB Output is correct
11 Correct 2 ms 81984 KB Output is correct
12 Correct 639 ms 81984 KB Output is correct
13 Correct 437 ms 81984 KB Output is correct
14 Correct 747 ms 81984 KB Output is correct
15 Correct 824 ms 81984 KB Output is correct
16 Correct 520 ms 81984 KB Output is correct
17 Correct 753 ms 81984 KB Output is correct
18 Correct 629 ms 81984 KB Output is correct
19 Correct 1069 ms 81984 KB Output is correct
20 Correct 2841 ms 81984 KB Output is correct
21 Correct 381 ms 81984 KB Output is correct
22 Correct 3217 ms 81984 KB Output is correct
23 Correct 293 ms 81984 KB Output is correct
24 Correct 1164 ms 81984 KB Output is correct
25 Correct 2685 ms 81984 KB Output is correct
26 Correct 2045 ms 81984 KB Output is correct
27 Correct 2239 ms 81984 KB Output is correct
28 Correct 835 ms 81984 KB Output is correct
29 Correct 1810 ms 81984 KB Output is correct
30 Correct 5028 ms 81984 KB Output is correct
31 Correct 4730 ms 82100 KB Output is correct
32 Correct 571 ms 82100 KB Output is correct
33 Correct 903 ms 82100 KB Output is correct
34 Correct 452 ms 82100 KB Output is correct
35 Correct 1553 ms 82100 KB Output is correct
36 Correct 3069 ms 82100 KB Output is correct
37 Correct 2784 ms 82100 KB Output is correct
38 Correct 2700 ms 82100 KB Output is correct
39 Correct 1106 ms 106348 KB Output is correct
40 Correct 2908 ms 106348 KB Output is correct
41 Correct 6897 ms 106348 KB Output is correct
42 Correct 6574 ms 168812 KB Output is correct
43 Correct 801 ms 168812 KB Output is correct
44 Correct 885 ms 168812 KB Output is correct
45 Correct 2058 ms 168812 KB Output is correct
46 Correct 4043 ms 168812 KB Output is correct
47 Correct 4439 ms 168812 KB Output is correct
48 Correct 3882 ms 168812 KB Output is correct
49 Correct 2 ms 168812 KB Output is correct