oj.uz

답안 #54528

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
54528 2018-07-04T01:03:11 Z KieranHorgan 게임 (IOI13_game) C++17
100 / 100
 6721 ms 177636 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);
        } 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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 476 KB Output is correct
3 Correct 3 ms 476 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 536 KB Output is correct
7 Correct 2 ms 536 KB Output is correct
8 Correct 2 ms 576 KB Output is correct
9 Correct 2 ms 580 KB Output is correct
10 Correct 3 ms 600 KB Output is correct
11 Correct 2 ms 708 KB Output is correct
12 Correct 2 ms 708 KB Output is correct

Subtask #2
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 708 KB Output is correct
2 Correct 2 ms 708 KB Output is correct
3 Correct 2 ms 708 KB Output is correct
4 Correct 685 ms 11216 KB Output is correct
5 Correct 470 ms 11420 KB Output is correct
6 Correct 775 ms 11420 KB Output is correct
7 Correct 813 ms 11420 KB Output is correct
8 Correct 485 ms 11420 KB Output is correct
9 Correct 816 ms 11420 KB Output is correct
10 Correct 643 ms 11420 KB Output is correct
11 Correct 2 ms 11420 KB Output is correct

Subtask #3
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 11420 KB Output is correct
2 Correct 3 ms 11420 KB Output is correct
3 Correct 2 ms 11420 KB Output is correct
4 Correct 2 ms 11420 KB Output is correct
5 Correct 2 ms 11420 KB Output is correct
6 Correct 3 ms 11420 KB Output is correct
7 Correct 2 ms 11420 KB Output is correct
8 Correct 3 ms 11420 KB Output is correct
9 Correct 3 ms 11420 KB Output is correct
10 Correct 3 ms 11420 KB Output is correct
11 Correct 2 ms 11420 KB Output is correct
12 Correct 1148 ms 14820 KB Output is correct
13 Correct 2916 ms 14820 KB Output is correct
14 Correct 390 ms 14820 KB Output is correct
15 Correct 3136 ms 14820 KB Output is correct
16 Correct 279 ms 14820 KB Output is correct
17 Correct 1315 ms 14820 KB Output is correct
18 Correct 2563 ms 14820 KB Output is correct
19 Correct 1918 ms 14820 KB Output is correct
20 Correct 1755 ms 14820 KB Output is correct
21 Correct 3 ms 14820 KB Output is correct

Subtask #4
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 14820 KB Output is correct
2 Correct 3 ms 14820 KB Output is correct
3 Correct 3 ms 14820 KB Output is correct
4 Correct 2 ms 14820 KB Output is correct
5 Correct 2 ms 14820 KB Output is correct
6 Correct 3 ms 14820 KB Output is correct
7 Correct 2 ms 14820 KB Output is correct
8 Correct 2 ms 14820 KB Output is correct
9 Correct 3 ms 14820 KB Output is correct
10 Correct 2 ms 14820 KB Output is correct
11 Correct 3 ms 14820 KB Output is correct
12 Correct 682 ms 14820 KB Output is correct
13 Correct 535 ms 14820 KB Output is correct
14 Correct 745 ms 14820 KB Output is correct
15 Correct 954 ms 14820 KB Output is correct
16 Correct 551 ms 14820 KB Output is correct
17 Correct 889 ms 14820 KB Output is correct
18 Correct 659 ms 14820 KB Output is correct
19 Correct 1122 ms 14860 KB Output is correct
20 Correct 2976 ms 14860 KB Output is correct
21 Correct 361 ms 14860 KB Output is correct
22 Correct 3084 ms 14860 KB Output is correct
23 Correct 304 ms 14860 KB Output is correct
24 Correct 1283 ms 14860 KB Output is correct
25 Correct 2700 ms 14860 KB Output is correct
26 Correct 1926 ms 14860 KB Output is correct
27 Correct 1880 ms 14860 KB Output is correct
28 Correct 856 ms 50228 KB Output is correct
29 Correct 1980 ms 50228 KB Output is correct
30 Correct 5078 ms 50228 KB Output is correct
31 Correct 4500 ms 83648 KB Output is correct
32 Correct 688 ms 83648 KB Output is correct
33 Correct 1051 ms 83648 KB Output is correct
34 Correct 390 ms 83648 KB Output is correct
35 Correct 1958 ms 83648 KB Output is correct
36 Correct 3708 ms 83648 KB Output is correct
37 Correct 2692 ms 83648 KB Output is correct
38 Correct 2426 ms 83648 KB Output is correct
39 Correct 2263 ms 83648 KB Output is correct
40 Correct 2 ms 83648 KB Output is correct

Subtask #5
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 83648 KB Output is correct
2 Correct 3 ms 83648 KB Output is correct
3 Correct 3 ms 83648 KB Output is correct
4 Correct 2 ms 83648 KB Output is correct
5 Correct 2 ms 83648 KB Output is correct
6 Correct 2 ms 83648 KB Output is correct
7 Correct 2 ms 83648 KB Output is correct
8 Correct 3 ms 83648 KB Output is correct
9 Correct 2 ms 83648 KB Output is correct
10 Correct 3 ms 83648 KB Output is correct
11 Correct 2 ms 83648 KB Output is correct
12 Correct 711 ms 83648 KB Output is correct
13 Correct 438 ms 83648 KB Output is correct
14 Correct 687 ms 83648 KB Output is correct
15 Correct 793 ms 83648 KB Output is correct
16 Correct 538 ms 83648 KB Output is correct
17 Correct 910 ms 83648 KB Output is correct
18 Correct 797 ms 83648 KB Output is correct
19 Correct 1306 ms 83648 KB Output is correct
20 Correct 2894 ms 83648 KB Output is correct
21 Correct 397 ms 83648 KB Output is correct
22 Correct 3363 ms 83648 KB Output is correct
23 Correct 304 ms 83648 KB Output is correct
24 Correct 1248 ms 83648 KB Output is correct
25 Correct 2355 ms 83648 KB Output is correct
26 Correct 2059 ms 83648 KB Output is correct
27 Correct 1528 ms 83648 KB Output is correct
28 Correct 788 ms 83648 KB Output is correct
29 Correct 1784 ms 83648 KB Output is correct
30 Correct 5187 ms 83648 KB Output is correct
31 Correct 4686 ms 83668 KB Output is correct
32 Correct 598 ms 83668 KB Output is correct
33 Correct 993 ms 83668 KB Output is correct
34 Correct 403 ms 83668 KB Output is correct
35 Correct 1799 ms 83668 KB Output is correct
36 Correct 3245 ms 83668 KB Output is correct
37 Correct 2564 ms 83668 KB Output is correct
38 Correct 2284 ms 83668 KB Output is correct
39 Correct 1069 ms 108348 KB Output is correct
40 Correct 2937 ms 108348 KB Output is correct
41 Correct 6524 ms 108348 KB Output is correct
42 Correct 6721 ms 177636 KB Output is correct
43 Correct 870 ms 177636 KB Output is correct
44 Correct 903 ms 177636 KB Output is correct
45 Correct 1977 ms 177636 KB Output is correct
46 Correct 3861 ms 177636 KB Output is correct
47 Correct 4428 ms 177636 KB Output is correct
48 Correct 3513 ms 177636 KB Output is correct
49 Correct 2 ms 177636 KB Output is correct