oj.uz

Submission #54526

# Submission time Handle Problem Language Result Execution time Memory
54526 2018-07-04T00:31:42 Z KieranHorgan Game (IOI13_game) C++17
80 / 100
 7330 ms 257024 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(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, 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);
        } 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) {
    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 2 ms 484 KB Output is correct
3 Correct 2 ms 484 KB Output is correct
4 Correct 2 ms 484 KB Output is correct
5 Correct 2 ms 484 KB Output is correct
6 Correct 3 ms 484 KB Output is correct
7 Correct 2 ms 484 KB Output is correct
8 Correct 3 ms 484 KB Output is correct
9 Correct 3 ms 508 KB Output is correct
10 Correct 3 ms 636 KB Output is correct
11 Correct 2 ms 636 KB Output is correct
12 Correct 3 ms 636 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 636 KB Output is correct
2 Correct 3 ms 636 KB Output is correct
3 Correct 3 ms 636 KB Output is correct
4 Correct 709 ms 10592 KB Output is correct
5 Correct 464 ms 11104 KB Output is correct
6 Correct 828 ms 11104 KB Output is correct
7 Correct 933 ms 11104 KB Output is correct
8 Correct 573 ms 11104 KB Output is correct
9 Correct 901 ms 11104 KB Output is correct
10 Correct 817 ms 11104 KB Output is correct
11 Correct 2 ms 11104 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11104 KB Output is correct
2 Correct 3 ms 11104 KB Output is correct
3 Correct 2 ms 11104 KB Output is correct
4 Correct 2 ms 11104 KB Output is correct
5 Correct 2 ms 11104 KB Output is correct
6 Correct 3 ms 11104 KB Output is correct
7 Correct 3 ms 11104 KB Output is correct
8 Correct 2 ms 11104 KB Output is correct
9 Correct 4 ms 11104 KB Output is correct
10 Correct 4 ms 11104 KB Output is correct
11 Correct 2 ms 11104 KB Output is correct
12 Correct 1249 ms 14616 KB Output is correct
13 Correct 2785 ms 14616 KB Output is correct
14 Correct 368 ms 14616 KB Output is correct
15 Correct 3362 ms 14616 KB Output is correct
16 Correct 371 ms 14616 KB Output is correct
17 Correct 1755 ms 14616 KB Output is correct
18 Correct 2790 ms 14616 KB Output is correct
19 Correct 2193 ms 14616 KB Output is correct
20 Correct 1777 ms 14616 KB Output is correct
21 Correct 2 ms 14616 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14616 KB Output is correct
2 Correct 3 ms 14616 KB Output is correct
3 Correct 3 ms 14616 KB Output is correct
4 Correct 2 ms 14616 KB Output is correct
5 Correct 2 ms 14616 KB Output is correct
6 Correct 2 ms 14616 KB Output is correct
7 Correct 2 ms 14616 KB Output is correct
8 Correct 2 ms 14616 KB Output is correct
9 Correct 2 ms 14616 KB Output is correct
10 Correct 2 ms 14616 KB Output is correct
11 Correct 2 ms 14616 KB Output is correct
12 Correct 689 ms 14616 KB Output is correct
13 Correct 453 ms 14616 KB Output is correct
14 Correct 729 ms 14616 KB Output is correct
15 Correct 832 ms 14616 KB Output is correct
16 Correct 592 ms 14616 KB Output is correct
17 Correct 862 ms 14616 KB Output is correct
18 Correct 739 ms 14616 KB Output is correct
19 Correct 1141 ms 14616 KB Output is correct
20 Correct 2769 ms 14616 KB Output is correct
21 Correct 413 ms 14616 KB Output is correct
22 Correct 3394 ms 14616 KB Output is correct
23 Correct 298 ms 14616 KB Output is correct
24 Correct 1472 ms 14616 KB Output is correct
25 Correct 2527 ms 14616 KB Output is correct
26 Correct 1982 ms 14616 KB Output is correct
27 Correct 1903 ms 14616 KB Output is correct
28 Correct 845 ms 62516 KB Output is correct
29 Correct 1890 ms 62516 KB Output is correct
30 Correct 5100 ms 102600 KB Output is correct
31 Correct 5201 ms 116780 KB Output is correct
32 Correct 584 ms 116780 KB Output is correct
33 Correct 1042 ms 116780 KB Output is correct
34 Correct 421 ms 116780 KB Output is correct
35 Correct 1663 ms 116780 KB Output is correct
36 Correct 3343 ms 116780 KB Output is correct
37 Correct 2665 ms 116780 KB Output is correct
38 Correct 2994 ms 116780 KB Output is correct
39 Correct 2454 ms 116780 KB Output is correct
40 Correct 2 ms 116780 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 116780 KB Output is correct
2 Correct 4 ms 116780 KB Output is correct
3 Correct 3 ms 116780 KB Output is correct
4 Correct 2 ms 116780 KB Output is correct
5 Correct 2 ms 116780 KB Output is correct
6 Correct 3 ms 116780 KB Output is correct
7 Correct 3 ms 116780 KB Output is correct
8 Correct 2 ms 116780 KB Output is correct
9 Correct 3 ms 116780 KB Output is correct
10 Correct 3 ms 116780 KB Output is correct
11 Correct 3 ms 116780 KB Output is correct
12 Correct 753 ms 116780 KB Output is correct
13 Correct 489 ms 116780 KB Output is correct
14 Correct 732 ms 116780 KB Output is correct
15 Correct 837 ms 116780 KB Output is correct
16 Correct 698 ms 116780 KB Output is correct
17 Correct 889 ms 116780 KB Output is correct
18 Correct 690 ms 116780 KB Output is correct
19 Correct 1275 ms 116780 KB Output is correct
20 Correct 2880 ms 116780 KB Output is correct
21 Correct 352 ms 116780 KB Output is correct
22 Correct 3146 ms 116780 KB Output is correct
23 Correct 290 ms 116780 KB Output is correct
24 Correct 1406 ms 116780 KB Output is correct
25 Correct 2299 ms 116780 KB Output is correct
26 Correct 2005 ms 116780 KB Output is correct
27 Correct 1816 ms 116780 KB Output is correct
28 Correct 867 ms 116780 KB Output is correct
29 Correct 1917 ms 116780 KB Output is correct
30 Correct 5421 ms 116780 KB Output is correct
31 Correct 5107 ms 116780 KB Output is correct
32 Correct 635 ms 116780 KB Output is correct
33 Correct 1028 ms 116780 KB Output is correct
34 Correct 442 ms 116780 KB Output is correct
35 Correct 1814 ms 116780 KB Output is correct
36 Correct 3684 ms 116780 KB Output is correct
37 Correct 2702 ms 116780 KB Output is correct
38 Correct 2394 ms 116780 KB Output is correct
39 Correct 1314 ms 137856 KB Output is correct
40 Correct 3266 ms 137856 KB Output is correct
41 Correct 7249 ms 232344 KB Output is correct
42 Runtime error 7330 ms 257024 KB Memory limit exceeded
43 Halted 0 ms 0 KB -