oj.uz

Submission #256341

# Submission time Handle Problem Language Result Execution time Memory
256341 2020-08-02T14:47:13 Z Sorting Game (IOI13_game) C++17
80 / 100
 4538 ms 256004 KB 
#include "game.h"
#include <bits/stdc++.h>
 
using namespace std;
 
const int k_Inf = 1e9;
 
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 SegmentTree{
    vector<long long> nodes;
    vector<int> left, right;
 
    void get_new_node(){
        nodes.push_back(0);
        left.push_back(-1);
        right.push_back(-1);
    }
 
    SegmentTree(){
        get_new_node();
    }
 
    void clear(){
        nodes.clear();
        left.clear();
        right.clear();
        get_new_node();
    }
 
    int update(int idx, int l, int r, int s, long long new_val){
        if(s < l || r < s) return idx;
        if(idx == -1){
            get_new_node();
            idx = nodes.size() - 1;
        }
        if(l == r){
            nodes[idx] = new_val;
            return idx;
        }
 
        int mid = (l + r) >> 1;
        int new_l = update(left[idx], l, mid, s, new_val);
        int new_r = update(right[idx], mid + 1, r, s, new_val);

        left[idx] = new_l;
        right[idx] = new_r;
    
        if(left[idx] == -1) nodes[idx] = nodes[right[idx]];
        else if(right[idx] == -1) nodes[idx] = nodes[left[idx]];
        else nodes[idx] = gcd2(nodes[left[idx]], nodes[right[idx]]);

        return idx;
    }
 
    long long query(int idx, int l, int r, int sl, int sr){
        if(idx == -1) return 0;
        if(sl > r || sr < l) return 0;
        if(sl <= l && r <= sr) return nodes[idx];
 
        int mid = (l + r) >> 1;
        long long lvalue = query(left[idx], l, mid, sl, sr);
        long long rvalue = query(right[idx], mid + 1, r, sl, sr);
        return gcd2(lvalue, rvalue);
    }
};
 
struct SegmentTree2D{
    vector<SegmentTree*> nodes;
    vector<int> left, right;
 
    void get_new_node(){
        nodes.push_back(new SegmentTree());
        left.push_back(-1);
        right.push_back(-1);
    }

    SegmentTree2D(){
        get_new_node();
    }
 
    int update(int idx, int l, int r, int x, int y, long long new_val){
        if(x < l || r < x) return idx;
        if(idx == -1){
            get_new_node();
            idx = nodes.size() - 1;
        }
        if(l == r){
            nodes[idx]->update(0, 0, k_Inf, y, new_val);
            return idx;
        }
 
        int mid = (l + r) >> 1;
        int new_l = update(left[idx], l, mid, x, y, new_val);
        int new_r = update(right[idx], mid + 1, r, x, y, new_val);

        left[idx] = new_l;
        right[idx] = new_r;
    
        long long t = 0;
        if(left[idx] != -1) t = gcd2(t, nodes[left[idx]]->query(0, 0, k_Inf, y, y));
        if(right[idx] != -1)t = gcd2(t, nodes[right[idx]]->query(0, 0, k_Inf, y, y));
        nodes[idx]->update(0, 0, k_Inf, y, t);
        return idx;
    }
 
    long long query(int idx, int l1, int r1, int sl1, int sr1, int sl2, int sr2){
        if(idx == -1) return 0;
        if(sl1 > r1 || sr1 < l1) return 0;
        if(sl1 <= l1 && r1 <= sr1) return nodes[idx]->query(0, 0, k_Inf, sl2, sr2);
 
        int mid = (l1 + r1) >> 1;
        long long lvalue = query(left[idx], l1, mid, sl1, sr1, sl2, sr2);
        long long rvalue = query(right[idx], mid + 1, r1, sl1, sr1, sl2, sr2);
        return gcd2(lvalue, rvalue);
    }
};
 
 
int r, c;
SegmentTree2D st;
 
void init(int _r, int _c) {
    r = _r, c = _c;
}
 
void update(int p, int q, long long k) {
    st.update(0, 0, k_Inf, p, q, k);
}
 
long long calculate(int p, int q, int u, int v) {
    return st.query(0, 0, k_Inf, p, u, q, 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 2 ms 384 KB Output is correct
2 Correct 4 ms 640 KB Output is correct
3 Correct 4 ms 640 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 3 ms 640 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 4 ms 640 KB Output is correct
10 Correct 2 ms 504 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1079 ms 33556 KB Output is correct
5 Correct 966 ms 33368 KB Output is correct
6 Correct 1189 ms 30240 KB Output is correct
7 Correct 1198 ms 30112 KB Output is correct
8 Correct 745 ms 19096 KB Output is correct
9 Correct 1177 ms 29988 KB Output is correct
10 Correct 1109 ms 29740 KB Output is correct
11 Correct 1 ms 384 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 5 ms 640 KB Output is correct
3 Correct 6 ms 640 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 8 ms 640 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 3 ms 640 KB Output is correct
10 Correct 2 ms 512 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 1464 ms 17640 KB Output is correct
13 Correct 1843 ms 8568 KB Output is correct
14 Correct 710 ms 3064 KB Output is correct
15 Correct 2128 ms 11896 KB Output is correct
16 Correct 782 ms 19448 KB Output is correct
17 Correct 1543 ms 14072 KB Output is correct
18 Correct 2477 ms 19836 KB Output is correct
19 Correct 2035 ms 19792 KB Output is correct
20 Correct 2105 ms 19156 KB Output is correct
21 Correct 1 ms 384 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 4 ms 640 KB Output is correct
3 Correct 6 ms 640 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 3 ms 640 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 6 ms 640 KB Output is correct
10 Correct 4 ms 512 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 1091 ms 33232 KB Output is correct
13 Correct 1044 ms 33520 KB Output is correct
14 Correct 1163 ms 30368 KB Output is correct
15 Correct 1129 ms 30064 KB Output is correct
16 Correct 744 ms 18968 KB Output is correct
17 Correct 1194 ms 29732 KB Output is correct
18 Correct 1117 ms 29484 KB Output is correct
19 Correct 1553 ms 16736 KB Output is correct
20 Correct 1893 ms 8312 KB Output is correct
21 Correct 702 ms 2808 KB Output is correct
22 Correct 2100 ms 11640 KB Output is correct
23 Correct 757 ms 19192 KB Output is correct
24 Correct 1495 ms 13944 KB Output is correct
25 Correct 2382 ms 19756 KB Output is correct
26 Correct 2164 ms 19584 KB Output is correct
27 Correct 2033 ms 19124 KB Output is correct
28 Correct 1335 ms 175432 KB Output is correct
29 Correct 2630 ms 190052 KB Output is correct
30 Correct 4461 ms 135104 KB Output is correct
31 Correct 4538 ms 109656 KB Output is correct
32 Correct 678 ms 10616 KB Output is correct
33 Correct 907 ms 13048 KB Output is correct
34 Correct 1445 ms 184908 KB Output is correct
35 Correct 1981 ms 100224 KB Output is correct
36 Correct 3480 ms 188352 KB Output is correct
37 Correct 3040 ms 188188 KB Output is correct
38 Correct 2868 ms 187876 KB Output is correct
39 Correct 2430 ms 147832 KB Output is correct
40 Correct 1 ms 384 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 4 ms 640 KB Output is correct
3 Correct 3 ms 640 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 3 ms 640 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 3 ms 640 KB Output is correct
10 Correct 1 ms 512 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 1042 ms 31988 KB Output is correct
13 Correct 922 ms 32288 KB Output is correct
14 Correct 1140 ms 29212 KB Output is correct
15 Correct 1167 ms 29092 KB Output is correct
16 Correct 706 ms 17940 KB Output is correct
17 Correct 1112 ms 28964 KB Output is correct
18 Correct 1016 ms 28720 KB Output is correct
19 Correct 1377 ms 16248 KB Output is correct
20 Correct 1872 ms 7528 KB Output is correct
21 Correct 702 ms 2164 KB Output is correct
22 Correct 2061 ms 10884 KB Output is correct
23 Correct 749 ms 18424 KB Output is correct
24 Correct 1313 ms 13204 KB Output is correct
25 Correct 2081 ms 18920 KB Output is correct
26 Correct 1902 ms 18928 KB Output is correct
27 Correct 1917 ms 18180 KB Output is correct
28 Correct 1289 ms 175556 KB Output is correct
29 Correct 2414 ms 190236 KB Output is correct
30 Correct 4410 ms 135260 KB Output is correct
31 Correct 4165 ms 109872 KB Output is correct
32 Correct 624 ms 10616 KB Output is correct
33 Correct 870 ms 13076 KB Output is correct
34 Correct 1369 ms 184872 KB Output is correct
35 Correct 1792 ms 100308 KB Output is correct
36 Correct 3275 ms 188440 KB Output is correct
37 Correct 3206 ms 188328 KB Output is correct
38 Correct 3647 ms 187788 KB Output is correct
39 Runtime error 1484 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
40 Halted 0 ms 0 KB -