oj.uz

Submission #256392

# Submission time Handle Problem Language Result Execution time Memory
256392 2020-08-02T16:06:13 Z Sorting Game (IOI13_game) C++17
80 / 100
 4604 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();
    }

    void check(){
        if(nodes.empty())
            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]->check();
            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){
            nodes[left[idx]]->check();
            t = gcd2(t, nodes[left[idx]]->query(0, 0, k_Inf, y, y));
        }
        if(right[idx] != -1){
            nodes[right[idx]]->check();
            t = gcd2(t, nodes[right[idx]]->query(0, 0, k_Inf, y, y));
        }
        nodes[idx]->check();
        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){
            nodes[idx]->check();
            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 1 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 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 2 ms 512 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 1132 ms 35756 KB Output is correct
5 Correct 1083 ms 35528 KB Output is correct
6 Correct 1283 ms 32896 KB Output is correct
7 Correct 1276 ms 32584 KB Output is correct
8 Correct 787 ms 21272 KB Output is correct
9 Correct 1327 ms 32740 KB Output is correct
10 Correct 1306 ms 32400 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 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 4 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 1536 ms 19176 KB Output is correct
13 Correct 2013 ms 10876 KB Output is correct
14 Correct 721 ms 5872 KB Output is correct
15 Correct 2209 ms 14420 KB Output is correct
16 Correct 836 ms 21868 KB Output is correct
17 Correct 1542 ms 17256 KB Output is correct
18 Correct 2261 ms 22696 KB Output is correct
19 Correct 2005 ms 22956 KB Output is correct
20 Correct 1921 ms 22080 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 1 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 1 ms 256 KB Output is correct
6 Correct 4 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 3 ms 384 KB Output is correct
12 Correct 1265 ms 35528 KB Output is correct
13 Correct 1108 ms 35636 KB Output is correct
14 Correct 1285 ms 32816 KB Output is correct
15 Correct 1301 ms 32692 KB Output is correct
16 Correct 818 ms 21272 KB Output is correct
17 Correct 1343 ms 32544 KB Output is correct
18 Correct 1240 ms 32552 KB Output is correct
19 Correct 1473 ms 19248 KB Output is correct
20 Correct 2109 ms 10660 KB Output is correct
21 Correct 788 ms 5804 KB Output is correct
22 Correct 2178 ms 14328 KB Output is correct
23 Correct 944 ms 21848 KB Output is correct
24 Correct 1597 ms 16836 KB Output is correct
25 Correct 2373 ms 22644 KB Output is correct
26 Correct 2177 ms 22880 KB Output is correct
27 Correct 2117 ms 22136 KB Output is correct
28 Correct 1603 ms 168772 KB Output is correct
29 Correct 2534 ms 183916 KB Output is correct
30 Correct 4604 ms 132356 KB Output is correct
31 Correct 4429 ms 106636 KB Output is correct
32 Correct 661 ms 5112 KB Output is correct
33 Correct 880 ms 7676 KB Output is correct
34 Correct 1366 ms 182512 KB Output is correct
35 Correct 1785 ms 94304 KB Output is correct
36 Correct 3411 ms 181784 KB Output is correct
37 Correct 2908 ms 181468 KB Output is correct
38 Correct 2828 ms 181256 KB Output is correct
39 Correct 2393 ms 141596 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 4 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 2 ms 512 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 1081 ms 35096 KB Output is correct
13 Correct 942 ms 35620 KB Output is correct
14 Correct 1149 ms 32160 KB Output is correct
15 Correct 1121 ms 31908 KB Output is correct
16 Correct 724 ms 21000 KB Output is correct
17 Correct 1120 ms 31900 KB Output is correct
18 Correct 1149 ms 31660 KB Output is correct
19 Correct 1459 ms 18984 KB Output is correct
20 Correct 1851 ms 10488 KB Output is correct
21 Correct 745 ms 4984 KB Output is correct
22 Correct 2124 ms 13816 KB Output is correct
23 Correct 709 ms 21368 KB Output is correct
24 Correct 1288 ms 15992 KB Output is correct
25 Correct 2049 ms 21624 KB Output is correct
26 Correct 1946 ms 21688 KB Output is correct
27 Correct 1998 ms 21112 KB Output is correct
28 Correct 1352 ms 168968 KB Output is correct
29 Correct 2201 ms 183488 KB Output is correct
30 Correct 4517 ms 132304 KB Output is correct
31 Correct 4305 ms 106664 KB Output is correct
32 Correct 654 ms 4984 KB Output is correct
33 Correct 888 ms 7800 KB Output is correct
34 Correct 1446 ms 182220 KB Output is correct
35 Correct 1778 ms 94316 KB Output is correct
36 Correct 3344 ms 181508 KB Output is correct
37 Correct 2848 ms 181428 KB Output is correct
38 Correct 2752 ms 180944 KB Output is correct
39 Runtime error 1370 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
40 Halted 0 ms 0 KB -