oj.uz

Submission #69240

# Submission time Handle Problem Language Result Execution time Memory
69240 2018-08-20T10:12:58 Z junhopark Game (IOI13_game) C++14
63 / 100
 11230 ms 257024 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)
{
    LL z;
    while (y) {
        z=x;
        x=y;
        y=z%y;
    }
    return x;
}
void make_tree()
{
    tree.push_back(vector<node2>(0));
    tree[tree.size()-1].push_back((node2){0, -1, -1});
}
void init(int R, int C)
{
    n = R, m = C;
    seg.push_back((node){-1, -1});
    make_tree();
}
void updatetree(int si, int ei, int pl, int ind, LL value, int pp)
{
    if (si>pl||ei<pl||ind<0||pp<0) return;
    if (si==ei) {
        tree[pp][ind].val=value;
        return;
    }
    int mi = (si+ei)>>1;
    if (pl>mi) {
        if (tree[pp][ind].r<0) {
            tree[pp][ind].r=tree[pp].size();
            tree[pp].push_back((node2){0, -1, -1});
        }
        updatetree(mi+1, ei, pl, tree[pp][ind].r, value, pp);
        if (tree[pp][ind].l<0) 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<0) {
            tree[pp][ind].l=tree[pp].size();
            tree[pp].push_back((node2){0, -1, -1});
        }
        updatetree(si, mi, pl, tree[pp][ind].l, value, pp);
        if (tree[pp][ind].r<0) 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||ind<0||pp<0) return;
    if (si==ei) {
        if ((ldx<0&&rdx<0)||(lp<0&&rp<0)) tree[pp][ind].val=0;
        else if (ldx<0||lp<0) tree[pp][ind].val=tree[rp][rdx].val;
        else if (rdx<0||rp<0) tree[pp][ind].val=tree[lp][ldx].val;
        else tree[pp][ind].val=gcd2(tree[lp][ldx].val, tree[rp][rdx].val);
        return;
    }
    if (ldx<0&&rdx<0) return;
    if (lp<0&&rp<0) return;
    int mi = (si+ei)>>1;
    if (pl>mi) {
        if (tree[pp][ind].r<0) {
            tree[pp][ind].r=tree[pp].size();
            tree[pp].push_back((node2){0, -1, -1});
        }
        if (ldx<0||lp<0) mergeseg(mi+1, ei, pl, tree[pp][ind].r, pp, lp, rp, -1, tree[rp][rdx].r);
        else if (rdx<0||rp<0) mergeseg(mi+1, ei, pl, tree[pp][ind].r, pp, lp, rp, tree[lp][ldx].r, -1);
        else 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<0) {
            tree[pp][ind].l=tree[pp].size();
            tree[pp].push_back((node2){0, -1, -1});
        }
        if (ldx<0||lp<0) mergeseg(si, mi, pl, tree[pp][ind].l, pp, lp, rp, -1, tree[rp][rdx].l);
        else if (rdx<0||rp<0) mergeseg(si, mi, pl, tree[pp][ind].l, pp, lp, rp, tree[lp][ldx].l, -1);
        else mergeseg(si, mi, pl, tree[pp][ind].l, pp, lp, rp, tree[lp][ldx].l, tree[rp][rdx].l);
    }
    if (ldx<0||lp<0) tree[pp][ind].val=tree[rp][rdx].val;
    else if (rdx<0||rp<0) tree[pp][ind].val=tree[lp][ldx].val;
    else 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||ind<0) return;
    if (si==ei) {
        updatetree(0, n-1, p, 0, value, ind);
        return;
    }
    int mi = (si+ei)>>1;
    if (pl>mi) {
        if (seg[ind].r<0) {
            seg[ind].r=seg.size();
            seg.push_back((node){-1, -1});
            make_tree();
        }
        updateseg(mi+1, ei, pl, seg[ind].r, value);
        mergeseg(0, n-1, p, 0, ind, seg[ind].l, seg[ind].r, 0, 0);
    }
    else {
        if (seg[ind].l<0) {
            seg[ind].l=seg.size();
            seg.push_back((node){-1, -1});
            make_tree();
        }
        updateseg(si, mi, pl, seg[ind].l, value);
        mergeseg(0, n-1, p, 0, ind, seg[ind].l, seg[ind].r, 0, 0);
    }
}
void update(int P, int Q, LL K)
{
    p = P;
    updateseg(0, m-1, Q, 0, K);
}
LL get_gcd2(int si, int ei, int s, int e, int ind, int pl)
{
    if (si>e||ei<s||ind<0||pl<0) 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||ind<0) return 0;
    if (si>=s&&ei<=e) return get_gcd2(0, n-1, p, u, 0, 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, 0);
}
/*int main()
{
    freopen("input.txt", "r", stdin);
    int R, C, N, i, P, Q, K, U, V, tp;
    scanf("%d %d %d", &R, &C, &N);
    init(R, C);
    for (i=1; i<=N; i++) {
        scanf("%d", &tp);
        if (tp==1) {
            scanf("%d %d %d", &P, &Q, &K);
            update(P, Q, K);
        }
        else {
            scanf("%d %d %d %d", &P, &Q, &U, &V);
            printf("%lld\n", calculate(P, Q, U, V));
        }
    }
}*/

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 2 ms 544 KB Output is correct
4 Correct 2 ms 544 KB Output is correct
5 Correct 2 ms 544 KB Output is correct
6 Correct 3 ms 544 KB Output is correct
7 Correct 3 ms 568 KB Output is correct
8 Correct 3 ms 580 KB Output is correct
9 Correct 4 ms 592 KB Output is correct
10 Correct 3 ms 596 KB Output is correct
11 Correct 2 ms 616 KB Output is correct
12 Correct 2 ms 616 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 616 KB Output is correct
2 Correct 2 ms 616 KB Output is correct
3 Correct 2 ms 616 KB Output is correct
4 Correct 977 ms 16788 KB Output is correct
5 Correct 1136 ms 20992 KB Output is correct
6 Correct 1022 ms 22536 KB Output is correct
7 Correct 1246 ms 27152 KB Output is correct
8 Correct 686 ms 28568 KB Output is correct
9 Correct 1131 ms 36004 KB Output is correct
10 Correct 1376 ms 40540 KB Output is correct
11 Correct 2 ms 40540 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 40540 KB Output is correct
2 Correct 4 ms 40540 KB Output is correct
3 Correct 3 ms 40540 KB Output is correct
4 Correct 2 ms 40540 KB Output is correct
5 Correct 3 ms 40540 KB Output is correct
6 Correct 3 ms 40540 KB Output is correct
7 Correct 2 ms 40540 KB Output is correct
8 Correct 3 ms 40540 KB Output is correct
9 Correct 3 ms 40540 KB Output is correct
10 Correct 2 ms 40540 KB Output is correct
11 Correct 2 ms 40540 KB Output is correct
12 Correct 1782 ms 48468 KB Output is correct
13 Correct 3161 ms 48468 KB Output is correct
14 Correct 421 ms 48468 KB Output is correct
15 Correct 3702 ms 48468 KB Output is correct
16 Correct 276 ms 49012 KB Output is correct
17 Correct 1351 ms 49012 KB Output is correct
18 Correct 2215 ms 49452 KB Output is correct
19 Correct 2029 ms 49632 KB Output is correct
20 Correct 1770 ms 49632 KB Output is correct
21 Correct 2 ms 49632 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 49632 KB Output is correct
2 Correct 4 ms 49632 KB Output is correct
3 Correct 3 ms 49632 KB Output is correct
4 Correct 4 ms 49632 KB Output is correct
5 Correct 2 ms 49632 KB Output is correct
6 Correct 6 ms 49632 KB Output is correct
7 Correct 2 ms 49632 KB Output is correct
8 Correct 3 ms 49632 KB Output is correct
9 Correct 3 ms 49632 KB Output is correct
10 Correct 3 ms 49632 KB Output is correct
11 Correct 3 ms 49632 KB Output is correct
12 Correct 1403 ms 50048 KB Output is correct
13 Correct 1237 ms 50384 KB Output is correct
14 Correct 1456 ms 50384 KB Output is correct
15 Correct 1819 ms 50384 KB Output is correct
16 Correct 1065 ms 50384 KB Output is correct
17 Correct 1806 ms 50384 KB Output is correct
18 Correct 1733 ms 50384 KB Output is correct
19 Correct 2198 ms 50788 KB Output is correct
20 Correct 3926 ms 50788 KB Output is correct
21 Correct 545 ms 50788 KB Output is correct
22 Correct 4488 ms 50788 KB Output is correct
23 Correct 410 ms 51524 KB Output is correct
24 Correct 2012 ms 51524 KB Output is correct
25 Correct 3449 ms 51956 KB Output is correct
26 Correct 2931 ms 52112 KB Output is correct
27 Correct 2606 ms 52112 KB Output is correct
28 Correct 1743 ms 195452 KB Output is correct
29 Correct 4253 ms 221748 KB Output is correct
30 Correct 11175 ms 221748 KB Output is correct
31 Correct 11230 ms 221748 KB Output is correct
32 Correct 1163 ms 221748 KB Output is correct
33 Correct 1534 ms 221748 KB Output is correct
34 Runtime error 1112 ms 257024 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
35 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 257024 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
2 Halted 0 ms 0 KB -