oj.uz

Submission #200107

# Submission time Handle Problem Language Result Execution time Memory
200107 2020-02-05T11:20:43 Z johutha Game (IOI13_game) C++14
37 / 100
 13000 ms 40184 KB 
#include "game.h"
#include <vector>
#include <iostream>
#include <array>
#include <cassert>

#define int long long
#define par array<int,2>

using namespace std;

int gcd(int a, int b)
{
    if (a > b) swap(a, b);
    if (a == 0) return b;
    return gcd(b % a, a);
}

struct segtree
{
    vector<int> table;

    int query(int ql, int qr, int l, int r, int pos)
    {
        if (ql <= l && r <= qr) return table[pos];
        if (r < ql || qr < l) return 0;
        return gcd(query(ql, qr, l, (l + r)/2, 2*pos + 1), query(ql, qr, (l + r)/2 + 1, r, 2*pos + 2));
    }

    void update(int k, int v, int l, int r, int pos)
    {
        if (l == r)
        {
            table[pos] = v;
            return;
        }
        if (k <= (l + r)/2) update(k, v, l, (l + r)/2, 2*pos + 1);
        else update(k, v, (l + r)/2 + 1, r, 2*pos + 2);
        table[pos] = gcd(table[2*pos + 1], table[2*pos + 2]);
    }
};

vector<segtree> sts;
int r, c;

void init(signed R, signed C)
{
    r = R;
    c = C;
    sts.resize(R);
    for (int i = 0; i < R; i++) sts[i].table.resize(4*C);
}

void update(signed P, signed Q, int K)
{
    // cout << "\n";
    sts[P].update(Q, K, 0, c - 1, 0);
}
 
int calculate(signed P, signed Q, signed U, signed V) 
{
    // cout << "\n";
    if (U < P) swap(U, P);
    if (V < Q) swap(Q, V);
    
    int ret = 0;

    for (int i = P; i <= U; i++)
    {
        ret = gcd(ret, sts[i].query(Q, V, 0, c - 1, 0));
        // cout << i << " " << sts[i].query(Q, V, 0, c - 1, 0) << "\n";
    }

    return ret;
}

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 5 ms 376 KB Output is correct
2 Correct 6 ms 632 KB Output is correct
3 Correct 6 ms 604 KB Output is correct
4 Correct 5 ms 256 KB Output is correct
5 Correct 5 ms 632 KB Output is correct
6 Correct 5 ms 636 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 380 KB Output is correct
9 Correct 6 ms 632 KB Output is correct
10 Correct 5 ms 632 KB Output is correct
11 Correct 5 ms 632 KB Output is correct
12 Correct 5 ms 256 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 908 ms 38128 KB Output is correct
5 Correct 620 ms 40088 KB Output is correct
6 Correct 835 ms 37356 KB Output is correct
7 Correct 849 ms 37144 KB Output is correct
8 Correct 754 ms 37496 KB Output is correct
9 Correct 808 ms 37240 KB Output is correct
10 Correct 745 ms 36908 KB Output is correct
11 Correct 5 ms 256 KB Output is correct

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 256 KB Output is correct
2 Correct 6 ms 632 KB Output is correct
3 Correct 7 ms 632 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 7 ms 632 KB Output is correct
6 Correct 5 ms 632 KB Output is correct
7 Correct 5 ms 256 KB Output is correct
8 Correct 5 ms 428 KB Output is correct
9 Correct 5 ms 632 KB Output is correct
10 Correct 5 ms 632 KB Output is correct
11 Correct 5 ms 636 KB Output is correct
12 Execution timed out 13043 ms 33304 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 632 KB Output is correct
3 Correct 5 ms 632 KB Output is correct
4 Correct 5 ms 256 KB Output is correct
5 Correct 5 ms 632 KB Output is correct
6 Correct 5 ms 632 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 5 ms 632 KB Output is correct
10 Correct 5 ms 632 KB Output is correct
11 Correct 5 ms 632 KB Output is correct
12 Correct 1503 ms 38008 KB Output is correct
13 Correct 1134 ms 39976 KB Output is correct
14 Correct 794 ms 37672 KB Output is correct
15 Correct 825 ms 37112 KB Output is correct
16 Correct 864 ms 37624 KB Output is correct
17 Correct 956 ms 37368 KB Output is correct
18 Correct 729 ms 36804 KB Output is correct
19 Execution timed out 13059 ms 34332 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 5 ms 632 KB Output is correct
3 Correct 5 ms 632 KB Output is correct
4 Correct 5 ms 256 KB Output is correct
5 Correct 5 ms 632 KB Output is correct
6 Correct 5 ms 632 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 5 ms 628 KB Output is correct
10 Correct 5 ms 632 KB Output is correct
11 Correct 5 ms 632 KB Output is correct
12 Correct 842 ms 38112 KB Output is correct
13 Correct 590 ms 40184 KB Output is correct
14 Correct 808 ms 37440 KB Output is correct
15 Correct 809 ms 37112 KB Output is correct
16 Correct 699 ms 37752 KB Output is correct
17 Correct 817 ms 37368 KB Output is correct
18 Correct 742 ms 36984 KB Output is correct
19 Execution timed out 13099 ms 34528 KB Time limit exceeded
20 Halted 0 ms 0 KB -