oj.uz

Submission #136857

# Submission time Handle Problem Language Result Execution time Memory
136857 2019-07-26T11:19:21 Z Juney Game (IOI13_game) C++14
63 / 100
 3339 ms 256004 KB 
#include "game.h"
#include <bits/stdc++.h>
using namespace std;

#define MAX_RANGE 1000000000
#define QUERY_SIZE 22000
#define gcd(x, y) gcd2(x, y)

typedef long long ll;

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;
}

struct CNODE {
    int l, r; ll val;
    CNODE() : l(0), r(0), val(0) {}
};

vector<CNODE> CT;

struct CDST {
    void update(int y, ll val, int l, int r, int n) {
        if(l == r) {
            CT[n].val = val;
            return;
        }
        int mid = (l + r) >> 1;
        if(y <= mid) {
            if(CT[n].l == 0) CT[n].l = CT.size(), CT.push_back(CNODE());
            update(y, val, l, mid , CT[n].l);
        }
        else {
            if(CT[n].r == 0) CT[n].r = CT.size(), CT.push_back(CNODE());
            update(y, val, mid+1, r, CT[n].r);
        }
        CT[n].val = gcd(CT[CT[n].l].val, CT[CT[n].r].val);
    }
    void update(int y, ll val, int n) {
        update(y, val, 1, MAX_RANGE, n);
    }
    ll query(int c1, int c2, int l, int r, int n) {
        if(n == 0 || r < c1 || c2 < l) return 0;
        if(c1 <= l && r <= c2) return CT[n].val;
        int mid = (l + r) >> 1;
        return gcd(query(c1, c2, l, mid, CT[n].l), query(c1, c2, mid+1, r, CT[n].r));
    }
    ll query(int c1, int c2, int n) {
        return query(c1, c2, 1, MAX_RANGE, n);
    }
} cdst;

struct RNODE {
    int l, r, croot;
    int get_root() {
        if(croot == 0) croot = CT.size(), CT.push_back(CNODE());
        return croot;
    }
    RNODE() : l(0), r(0), croot(0) {}
};

vector<RNODE> RT;

struct RDST {
    void mrg(int y, int n, int ln, int rn, int l=1, int r=MAX_RANGE) {
        if(ln == 0 && rn == 0) return;
        CT[n].val = gcd(CT[ln].val, CT[rn].val);
        if(l == r) return;
        int mid = (l + r) >> 1;
        if(y <= mid) {
            if(CT[n].l == 0) CT[n].l = CT.size(), CT.push_back(CNODE());
            mrg(y, CT[n].l, CT[ln].l, CT[rn].l, l, mid);
        }
        else {
            if(CT[n].r == 0) CT[n].r = CT.size(), CT.push_back(CNODE());
            mrg(y, CT[n].r, CT[ln].r, CT[rn].r, mid+1, r);
        }
    }
    void update(int x, int y, ll val, int l=1, int r=MAX_RANGE, int n=1) {
        if(l == r) {
            cdst.update(y, val, RT[n].get_root());
            return;
        }
        int mid = (l + r) >> 1;
        if(x <= mid) {
            if(RT[n].l == 0) RT[n].l = RT.size(), RT.push_back(RNODE());
            update(x, y, val, l, mid, RT[n].l);
        }
        else {
            if(RT[n].r == 0) RT[n].r = RT.size(), RT.push_back(RNODE());
            update(x, y, val, mid+1, r, RT[n].r);
        }
        mrg(y, RT[n].get_root(), RT[RT[n].l].get_root(), RT[RT[n].r].get_root());
    }
    ll query(int r1, int c1, int r2, int c2, int l=1, int r=MAX_RANGE, int n=1) {
        if(n == 0 || r < r1 || r2 < l) return 0;
        if(r1 <= l && r <= r2) return cdst.query(c1, c2, RT[n].get_root());
        int mid = (l + r) >> 1;
        return gcd(query(r1, c1, r2, c2, l, mid, RT[n].l), query(r1, c1, r2, c2, mid+1, r, RT[n].r));
    }
} dst;

void init(int R, int C) {
    CT.push_back(CNODE());
    RT.push_back(RNODE()); RT.push_back(RNODE());
}

void update(int P, int Q, long long K) {
    dst.update(P+1, Q+1, K);
}

long long calculate(int P, int Q, int U, int V) {
    return dst.query(P+1, Q+1, U+1, 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 5 ms 760 KB Output is correct
3 Correct 4 ms 632 KB Output is correct
4 Correct 2 ms 372 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 4 ms 760 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 4 ms 760 KB Output is correct
10 Correct 3 ms 504 KB Output is correct
11 Correct 3 ms 504 KB Output is correct
12 Correct 2 ms 376 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 424 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 1164 ms 36200 KB Output is correct
5 Correct 833 ms 36148 KB Output is correct
6 Correct 1313 ms 34080 KB Output is correct
7 Correct 1214 ms 33416 KB Output is correct
8 Correct 839 ms 17792 KB Output is correct
9 Correct 1216 ms 33720 KB Output is correct
10 Correct 1064 ms 33340 KB Output is correct
11 Correct 2 ms 376 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 5 ms 764 KB Output is correct
3 Correct 4 ms 636 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 380 KB Output is correct
6 Correct 4 ms 632 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 5 ms 760 KB Output is correct
10 Correct 3 ms 632 KB Output is correct
11 Correct 3 ms 504 KB Output is correct
12 Correct 1672 ms 11676 KB Output is correct
13 Correct 2937 ms 5296 KB Output is correct
14 Correct 786 ms 1268 KB Output is correct
15 Correct 3309 ms 8668 KB Output is correct
16 Correct 883 ms 16900 KB Output is correct
17 Correct 2029 ms 9280 KB Output is correct
18 Correct 2822 ms 17260 KB Output is correct
19 Correct 2606 ms 17872 KB Output is correct
20 Correct 2344 ms 17288 KB Output is correct
21 Correct 2 ms 376 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 5 ms 760 KB Output is correct
3 Correct 5 ms 760 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 4 ms 760 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 4 ms 760 KB Output is correct
10 Correct 3 ms 524 KB Output is correct
11 Correct 3 ms 504 KB Output is correct
12 Correct 1107 ms 35900 KB Output is correct
13 Correct 853 ms 36156 KB Output is correct
14 Correct 1149 ms 34108 KB Output is correct
15 Correct 1258 ms 33340 KB Output is correct
16 Correct 850 ms 18008 KB Output is correct
17 Correct 1245 ms 33616 KB Output is correct
18 Correct 1090 ms 33468 KB Output is correct
19 Correct 1668 ms 11816 KB Output is correct
20 Correct 2912 ms 5408 KB Output is correct
21 Correct 789 ms 1268 KB Output is correct
22 Correct 3339 ms 8680 KB Output is correct
23 Correct 781 ms 16848 KB Output is correct
24 Correct 1908 ms 9368 KB Output is correct
25 Correct 2932 ms 17232 KB Output is correct
26 Correct 2843 ms 17756 KB Output is correct
27 Correct 2328 ms 17304 KB Output is correct
28 Correct 1064 ms 134920 KB Output is correct
29 Runtime error 2166 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
30 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 5 ms 760 KB Output is correct
3 Correct 5 ms 760 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 4 ms 632 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 4 ms 632 KB Output is correct
10 Correct 3 ms 504 KB Output is correct
11 Correct 3 ms 504 KB Output is correct
12 Correct 1167 ms 36040 KB Output is correct
13 Correct 842 ms 36340 KB Output is correct
14 Correct 1161 ms 34108 KB Output is correct
15 Correct 1223 ms 33340 KB Output is correct
16 Correct 846 ms 17980 KB Output is correct
17 Correct 1215 ms 33596 KB Output is correct
18 Correct 1072 ms 33340 KB Output is correct
19 Correct 1666 ms 11800 KB Output is correct
20 Correct 2952 ms 5212 KB Output is correct
21 Correct 796 ms 1268 KB Output is correct
22 Correct 3322 ms 8668 KB Output is correct
23 Correct 781 ms 16852 KB Output is correct
24 Correct 1870 ms 9308 KB Output is correct
25 Correct 2919 ms 17332 KB Output is correct
26 Correct 2591 ms 17572 KB Output is correct
27 Correct 2449 ms 17424 KB Output is correct
28 Correct 1048 ms 134760 KB Output is correct
29 Runtime error 2193 ms 256000 KB Execution killed with signal 9 (could be triggered by violating memory limits)
30 Halted 0 ms 0 KB -