oj.uz

Submission #69244

# Submission time Handle Problem Language Result Execution time Memory
69244 2018-08-20T10:17:24 Z junhopark Game (IOI13_game) C++14
63 / 100
 13000 ms 200660 KB 
#include <bits/stdc++.h>
#include "game.h"
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
int n, m, p, u;
struct node {int l, r; };
struct node2
{
    LL val;
    int l, r;
};
vector<node> seg;
vector<vector<node2> > tree;
LL gcd2(LL x, LL y)
{
    if (!y) return x;
    return gcd2(y, x%y);
}
void make_tree()
{
    tree.push_back(vector<node2>(0));
    tree[tree.size()-1].push_back((node2){0, 0, 0});
    tree[tree.size()-1].push_back((node2){0, 0, 0});
}
void init(int R, int C)
{
    n = R, m = C;
    seg.push_back((node){0, 0});
    seg.push_back((node){0, 0});
    make_tree();
    make_tree();
}
void updatetree(int si, int ei, int pl, int ind, LL value, int pp)
{
    if (si>pl||ei<pl) return;
    if (si==ei) {
        tree[pp][ind].val=value;
        return;
    }
    int mi = (si+ei)>>1;
    if (pl>mi) {
        if (!tree[pp][ind].r) {
            tree[pp][ind].r=tree[pp].size();
            tree[pp].push_back((node2){0, 0, 0});
        }
        updatetree(mi+1, ei, pl, tree[pp][ind].r, value, pp);
        if (!tree[pp][ind].l) tree[pp][ind].val=tree[pp][tree[pp][ind].r].val;
        else tree[pp][ind].val=__gcd(tree[pp][tree[pp][ind].r].val, tree[pp][tree[pp][ind].l].val);
    }
    else {
        if (!tree[pp][ind].l) {
            tree[pp][ind].l=tree[pp].size();
            tree[pp].push_back((node2){0, 0, 0});
        }
        updatetree(si, mi, pl, tree[pp][ind].l, value, pp);
        if (!tree[pp][ind].r) tree[pp][ind].val=tree[pp][tree[pp][ind].l].val;
        else tree[pp][ind].val=gcd2(tree[pp][tree[pp][ind].r].val, tree[pp][tree[pp][ind].l].val);
    }
}
void mergeseg(int si, int ei, int pl, int ind, int pp, int lp, int rp, int ldx, int rdx)
{
    if (si>pl||ei<pl) return;
    if (si==ei) {
        if (!ldx&&!rdx) tree[pp][ind].val=0;
        else if (!ldx) tree[pp][ind].val=tree[rp][rdx].val;
        else if (!rdx) tree[pp][ind].val=tree[lp][ldx].val;
        else tree[pp][ind].val=gcd2(tree[lp][ldx].val, tree[rp][rdx].val);
        return;
    }
    int mi = (si+ei)>>1;
    if (pl>mi) {
        if (!tree[pp][ind].r) {
            tree[pp][ind].r=tree[pp].size();
            tree[pp].push_back((node2){0, 0, 0});
        }
        mergeseg(mi+1, ei, pl, tree[pp][ind].r, pp, lp, rp, tree[lp][ldx].r, tree[rp][rdx].r);
    }
    else {
        if (!tree[pp][ind].l) {
            tree[pp][ind].l=tree[pp].size();
            tree[pp].push_back((node2){0, 0, 0});
        }
        mergeseg(si, mi, pl, tree[pp][ind].l, pp, lp, rp, tree[lp][ldx].l, tree[rp][rdx].l);
    }
    tree[pp][ind].val=gcd2(tree[lp][ldx].val, tree[rp][rdx].val);
}
void updateseg(int si, int ei, int pl, int ind, LL value)
{
    if (si>pl||ei<pl) return;
    if (si==ei) {
        updatetree(0, n-1, p, 1, value, ind);
        return;
    }
    int mi = (si+ei)>>1;
    if (pl>mi) {
        if (!seg[ind].r) {
            seg[ind].r=seg.size();
            seg.push_back((node){0, 0});
            make_tree();
        }
        updateseg(mi+1, ei, pl, seg[ind].r, value);
        mergeseg(0, n-1, p, 1, ind, seg[ind].l, seg[ind].r, 1, 1);
    }
    else {
        if (!seg[ind].l) {
            seg[ind].l=seg.size();
            seg.push_back((node){0, 0});
            make_tree();
        }
        updateseg(si, mi, pl, seg[ind].l, value);
        mergeseg(0, n-1, p, 1, ind, seg[ind].l, seg[ind].r, 1, 1);
    }
}
void update(int P, int Q, LL K)
{
    p = P;
    updateseg(0, m-1, Q, 1, K);
}
LL get_gcd2(int si, int ei, int s, int e, int ind, int pl)
{
    if (si>e||ei<s) return 0;
    if (si>=s&&ei<=e) return tree[pl][ind].val;
    int mi = (si+ei)>>1;
    return gcd2(get_gcd2(si, mi, s, e, tree[pl][ind].l, pl), get_gcd2(mi+1, ei, s, e, tree[pl][ind].r, pl));
}
LL get_gcd(int si, int ei, int s, int e, int ind)
{
    if (si>e||ei<s) return 0;
    if (si>=s&&ei<=e) return get_gcd2(0, n-1, p, u, 1, ind);
    int mi = (si+ei)>>1;
    return gcd2(get_gcd(si, mi, s, e, seg[ind].l), get_gcd(mi+1, ei, s, e, seg[ind].r));
}
LL calculate(int P, int Q, int U, int V)
{
    p = P, u = U;
    return get_gcd(0, m-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 3 ms 376 KB Output is correct
2 Correct 3 ms 492 KB Output is correct
3 Correct 4 ms 492 KB Output is correct
4 Correct 3 ms 492 KB Output is correct
5 Correct 2 ms 588 KB Output is correct
6 Correct 4 ms 588 KB Output is correct
7 Correct 2 ms 588 KB Output is correct
8 Correct 3 ms 588 KB Output is correct
9 Correct 4 ms 588 KB Output is correct
10 Correct 3 ms 588 KB Output is correct
11 Correct 3 ms 588 KB Output is correct
12 Correct 2 ms 624 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 624 KB Output is correct
2 Correct 2 ms 624 KB Output is correct
3 Correct 3 ms 656 KB Output is correct
4 Correct 1266 ms 14868 KB Output is correct
5 Correct 1234 ms 15048 KB Output is correct
6 Correct 1431 ms 15048 KB Output is correct
7 Correct 1311 ms 15048 KB Output is correct
8 Correct 788 ms 15048 KB Output is correct
9 Correct 1286 ms 15048 KB Output is correct
10 Correct 1294 ms 15048 KB Output is correct
11 Correct 2 ms 15048 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 15048 KB Output is correct
2 Correct 3 ms 15048 KB Output is correct
3 Correct 3 ms 15048 KB Output is correct
4 Correct 2 ms 15048 KB Output is correct
5 Correct 2 ms 15048 KB Output is correct
6 Correct 3 ms 15048 KB Output is correct
7 Correct 3 ms 15048 KB Output is correct
8 Correct 3 ms 15048 KB Output is correct
9 Correct 4 ms 15048 KB Output is correct
10 Correct 3 ms 15048 KB Output is correct
11 Correct 3 ms 15048 KB Output is correct
12 Correct 1758 ms 15048 KB Output is correct
13 Correct 2929 ms 15048 KB Output is correct
14 Correct 1000 ms 15048 KB Output is correct
15 Correct 3431 ms 15048 KB Output is correct
16 Correct 301 ms 15048 KB Output is correct
17 Correct 1707 ms 15048 KB Output is correct
18 Correct 2815 ms 15244 KB Output is correct
19 Correct 2254 ms 15352 KB Output is correct
20 Correct 2230 ms 15352 KB Output is correct
21 Correct 3 ms 15352 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 15352 KB Output is correct
2 Correct 4 ms 15352 KB Output is correct
3 Correct 3 ms 15352 KB Output is correct
4 Correct 2 ms 15352 KB Output is correct
5 Correct 2 ms 15352 KB Output is correct
6 Correct 3 ms 15352 KB Output is correct
7 Correct 2 ms 15352 KB Output is correct
8 Correct 2 ms 15352 KB Output is correct
9 Correct 2 ms 15352 KB Output is correct
10 Correct 3 ms 15352 KB Output is correct
11 Correct 4 ms 15352 KB Output is correct
12 Correct 1086 ms 15352 KB Output is correct
13 Correct 1185 ms 15352 KB Output is correct
14 Correct 1168 ms 15352 KB Output is correct
15 Correct 1453 ms 15352 KB Output is correct
16 Correct 897 ms 15352 KB Output is correct
17 Correct 1237 ms 15352 KB Output is correct
18 Correct 1116 ms 15352 KB Output is correct
19 Correct 1765 ms 15352 KB Output is correct
20 Correct 2946 ms 15352 KB Output is correct
21 Correct 952 ms 15352 KB Output is correct
22 Correct 3409 ms 15352 KB Output is correct
23 Correct 335 ms 15352 KB Output is correct
24 Correct 1866 ms 15352 KB Output is correct
25 Correct 2756 ms 15352 KB Output is correct
26 Correct 2293 ms 15352 KB Output is correct
27 Correct 2191 ms 15352 KB Output is correct
28 Correct 6849 ms 147880 KB Output is correct
29 Correct 8897 ms 164108 KB Output is correct
30 Execution timed out 13050 ms 164108 KB Time limit exceeded
31 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 164108 KB Output is correct
2 Correct 4 ms 164108 KB Output is correct
3 Correct 3 ms 164108 KB Output is correct
4 Correct 3 ms 164108 KB Output is correct
5 Correct 2 ms 164108 KB Output is correct
6 Correct 3 ms 164108 KB Output is correct
7 Correct 3 ms 164108 KB Output is correct
8 Correct 2 ms 164108 KB Output is correct
9 Correct 3 ms 164108 KB Output is correct
10 Correct 3 ms 164108 KB Output is correct
11 Correct 2 ms 164108 KB Output is correct
12 Correct 1085 ms 164108 KB Output is correct
13 Correct 1179 ms 164108 KB Output is correct
14 Correct 1162 ms 164108 KB Output is correct
15 Correct 1543 ms 164108 KB Output is correct
16 Correct 864 ms 164108 KB Output is correct
17 Correct 1519 ms 164108 KB Output is correct
18 Correct 1453 ms 164108 KB Output is correct
19 Correct 1932 ms 164108 KB Output is correct
20 Correct 3031 ms 164108 KB Output is correct
21 Correct 883 ms 164108 KB Output is correct
22 Correct 3502 ms 164108 KB Output is correct
23 Correct 265 ms 164108 KB Output is correct
24 Correct 1590 ms 164108 KB Output is correct
25 Correct 2645 ms 164108 KB Output is correct
26 Correct 2246 ms 164108 KB Output is correct
27 Correct 2569 ms 164108 KB Output is correct
28 Correct 7688 ms 174508 KB Output is correct
29 Correct 9059 ms 200660 KB Output is correct
30 Execution timed out 13043 ms 200660 KB Time limit exceeded
31 Halted 0 ms 0 KB -