oj.uz

Submission #256427

# Submission time Handle Problem Language Result Execution time Memory
256427 2020-08-02T16:43:51 Z A02 Game (IOI13_game) C++14
63 / 100
 1154 ms 256004 KB 
#include "game.h"
#include <vector>
#include <algorithm>
#include <set>
#include <utility>
#include <iostream>

using namespace std;

long long gcd2(long long X, long long Y) {
    long long tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}


void update_seg_tree(vector<long long> &tree, long long p, long long t){

    long long N = tree.size() / 2;

    tree[p + N] = t;

    for (p = (p + N) / 2; 0 < p; p /= 2){

        tree[p] = gcd2(tree[2 * p], tree[2 * p + 1]);

    }

}

long long query_seg_tree(vector<long long> &tree, long long l, long long r){

    long long N = tree.size() / 2;
    long long total = 0;

    for (l += N, r += N; l < r; l /= 2, r /= 2){

        if (l % 2 == 1){
            total = gcd2(total, tree[l++]);
        }
        if (r % 2 == 1){
            total = gcd2(total, tree[--r]);
        }

    }

    return total;
}

void update_2Dseg_tree(vector<vector<long long> > &tree, long long r, long long c, long long t){

    long long N = tree.size() / 2;

    update_seg_tree(tree[r + N], c, t);

    for (r = (r + N) / 2; 0 < r; r /= 2){

        update_seg_tree(tree[r], c, gcd2(query_seg_tree(tree[2 * r], c, c + 1), query_seg_tree(tree[2 * r + 1], c, c + 1)));

    }

}

long long query_2Dseg_tree(vector<vector<long long> > &tree, long long lr, long long rr, long long lc, long long rc){

    long long N = tree.size() / 2;
    long long total = 0;

    for (lr += N, rr += N; lr < rr; lr /= 2, rr /= 2){

        if (lr % 2 == 1){
            total = gcd2(total, query_seg_tree(tree[lr++], lc, rc));
        }
        if (rr % 2 == 1){
            total = gcd2(total, query_seg_tree(tree[--rr], lc, rc));
        }

    }

    return total;
}

vector<vector<long long> > seg_tree;

void init(int R, int C) {

    seg_tree = vector<vector<long long> > (2 * R, vector<long long> (2 * C, 0));

}

void update(int P, int Q, long long K) {
    //cout << "update: " << P << ' ' << Q << ' ' << K << endl;
    update_2Dseg_tree(seg_tree, P, Q, K);
    //cout << ' ' << query_2Dseg_tree(seg_tree, 0, 1, 0, 3) << endl;
}

long long calculate(int P, int Q, int U, int V) {
    //cout << "calculate: " << P << ' ' << Q << ' '<< U << ' ' << V << endl;
    return query_2Dseg_tree(seg_tree, P, U + 1, Q, V + 1);
}

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;
      ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 1 ms 640 KB Output is correct
3 Correct 1 ms 640 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 1 ms 640 KB Output is correct
6 Correct 1 ms 640 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 640 KB Output is correct
10 Correct 1 ms 640 KB Output is correct
11 Correct 1 ms 640 KB Output is correct
12 Correct 0 ms 256 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 457 ms 35676 KB Output is correct
5 Correct 346 ms 36056 KB Output is correct
6 Correct 513 ms 33272 KB Output is correct
7 Correct 483 ms 33272 KB Output is correct
8 Correct 389 ms 33436 KB Output is correct
9 Correct 507 ms 33280 KB Output is correct
10 Correct 470 ms 33280 KB Output is correct
11 Correct 1 ms 256 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 2 ms 640 KB Output is correct
3 Correct 1 ms 640 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 1 ms 640 KB Output is correct
6 Correct 1 ms 640 KB Output is correct
7 Correct 0 ms 256 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 640 KB Output is correct
10 Correct 1 ms 640 KB Output is correct
11 Correct 1 ms 640 KB Output is correct
12 Correct 616 ms 36088 KB Output is correct
13 Correct 777 ms 32444 KB Output is correct
14 Correct 495 ms 126328 KB Output is correct
15 Correct 945 ms 126584 KB Output is correct
16 Correct 368 ms 126560 KB Output is correct
17 Correct 862 ms 127224 KB Output is correct
18 Correct 1040 ms 126844 KB Output is correct
19 Correct 978 ms 126968 KB Output is correct
20 Correct 935 ms 126492 KB Output is correct
21 Correct 0 ms 256 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 1 ms 640 KB Output is correct
3 Correct 1 ms 640 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 1 ms 640 KB Output is correct
6 Correct 1 ms 640 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 1 ms 640 KB Output is correct
10 Correct 1 ms 640 KB Output is correct
11 Correct 1 ms 640 KB Output is correct
12 Correct 445 ms 35928 KB Output is correct
13 Correct 342 ms 36060 KB Output is correct
14 Correct 489 ms 33280 KB Output is correct
15 Correct 479 ms 33280 KB Output is correct
16 Correct 395 ms 33280 KB Output is correct
17 Correct 485 ms 33272 KB Output is correct
18 Correct 438 ms 33272 KB Output is correct
19 Correct 602 ms 35832 KB Output is correct
20 Correct 772 ms 32460 KB Output is correct
21 Correct 485 ms 126456 KB Output is correct
22 Correct 974 ms 126456 KB Output is correct
23 Correct 365 ms 126456 KB Output is correct
24 Correct 883 ms 127480 KB Output is correct
25 Correct 1081 ms 127140 KB Output is correct
26 Correct 1030 ms 127224 KB Output is correct
27 Correct 947 ms 126420 KB Output is correct
28 Runtime error 122 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 1 ms 640 KB Output is correct
3 Correct 1 ms 640 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 1 ms 640 KB Output is correct
6 Correct 1 ms 640 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 1 ms 640 KB Output is correct
10 Correct 1 ms 640 KB Output is correct
11 Correct 1 ms 640 KB Output is correct
12 Correct 448 ms 35928 KB Output is correct
13 Correct 364 ms 36056 KB Output is correct
14 Correct 491 ms 33152 KB Output is correct
15 Correct 506 ms 33276 KB Output is correct
16 Correct 390 ms 33368 KB Output is correct
17 Correct 504 ms 33280 KB Output is correct
18 Correct 458 ms 33272 KB Output is correct
19 Correct 602 ms 35960 KB Output is correct
20 Correct 769 ms 32504 KB Output is correct
21 Correct 505 ms 126456 KB Output is correct
22 Correct 970 ms 126712 KB Output is correct
23 Correct 394 ms 126584 KB Output is correct
24 Correct 980 ms 127224 KB Output is correct
25 Correct 1154 ms 126888 KB Output is correct
26 Correct 1098 ms 127096 KB Output is correct
27 Correct 943 ms 126584 KB Output is correct
28 Runtime error 131 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -