oj.uz

Submission #256324

# Submission time Handle Problem Language Result Execution time Memory
256324 2020-08-02T14:28:51 Z Sorting Game (IOI13_game) C++17
63 / 100
 2827 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);
    }
 
    void build_kids(int idx){
        if(left[idx] == -1){
            get_new_node();
            left[idx] = nodes.size() - 1;
            get_new_node();
            right[idx] = nodes.size() - 1;
        }
    }
 
    SegmentTree(){
        get_new_node();
    }
 
    void clear(){
        nodes.clear();
        left.clear();
        right.clear();
        get_new_node();
    }
 
    void update(int idx, int l, int r, int s, long long new_val){
        if(s < l || r < s) return;
        if(l == r){
            nodes[idx] = new_val;
            return;
        }
 
        build_kids(idx);
 
        int mid = (l + r) >> 1;
        update(left[idx], l, mid, s, new_val);
        update(right[idx], mid + 1, r, s, new_val);
 
        nodes[idx] = gcd2(nodes[left[idx]], nodes[right[idx]]);
    }
 
    long long query(int idx, int l, int r, int sl, int sr){
        if(sl > r || sr < l) return 0;
        if(sl <= l && r <= sr) return nodes[idx];
 
        if(left[idx] == -1)
            return 0;
 
        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);
    }
 
    friend void merge(SegmentTree &st1, SegmentTree &st2, SegmentTree &ans, int idx1, int idx2, int idx3){
        if((idx1 == -1 || st1.left[idx1] == -1) && (idx2 == -1 || st2.left[idx2] == -1)){
            if(idx1 == -1) ans.nodes[idx3] = st2.nodes[idx2]; 
            else if(idx2 == -1) ans.nodes[idx3] = st1.nodes[idx1];
            else ans.nodes[idx3] = gcd2(st1.nodes[idx1], st2.nodes[idx2]);
            return;
        }
 
        ans.build_kids(idx3);
 
        if(idx1 == -1 || st1.left[idx1] == -1){
            merge(st1, st2, ans, -1, st2.left[idx2], ans.left[idx3]);
            merge(st1, st2, ans, -1, st2.right[idx2], ans.right[idx3]);
        }
        else if(idx2 == -1 || st2.left[idx2] == -1){
            merge(st1, st2, ans, st1.left[idx1], -1, ans.left[idx3]);
            merge(st1, st2, ans, st1.right[idx1], -1, ans.right[idx3]);
        }
        else{
            merge(st1, st2, ans, st1.left[idx1], st2.left[idx2], ans.left[idx3]);
            merge(st1, st2, ans, st1.right[idx1], st2.right[idx2], ans.right[idx3]);
        }
 
        ans.nodes[idx3] = gcd2(ans.nodes[ans.left[idx3]], ans.nodes[ans.right[idx3]]);
    }
};
 
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);
    }
 
    void build_kids(int idx){
        if(left[idx] == -1){
            get_new_node();
            left[idx] = nodes.size() - 1;
            get_new_node();
            right[idx] = nodes.size() - 1;
        }
    }
 
    SegmentTree2D(){
        get_new_node();
    }
 
    void update(int idx, int l, int r, int x, int y, long long new_val){
        if(x < l || r < x) return;
        if(l == r){
            nodes[idx]->update(0, 0, k_Inf, y, new_val);
            return;
        }
 
        build_kids(idx);
 
        int mid = (l + r) >> 1;
        update(left[idx], l, mid, x, y, new_val);
        update(right[idx], mid + 1, r, x, y, new_val);
    
        long long t = gcd2(nodes[left[idx]]->query(0, 0, k_Inf, y, y), nodes[right[idx]]->query(0, 0, k_Inf, y, y));
        nodes[idx]->update(0, 0, k_Inf, y, t);
    }
 
    long long query(int idx, int l1, int r1, int sl1, int sr1, int sl2, int sr2){
        if(sl1 > r1 || sr1 < l1) return 0;
        if(sl1 <= l1 && r1 <= sr1) return nodes[idx]->query(0, 0, k_Inf, sl2, sr2);
 
        if(left[idx] == -1)
            return 0;
 
        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 768 KB Output is correct
3 Correct 4 ms 768 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 768 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 768 KB Output is correct
10 Correct 2 ms 640 KB Output is correct
11 Correct 2 ms 512 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 1203 ms 53648 KB Output is correct
5 Correct 1117 ms 54444 KB Output is correct
6 Correct 1358 ms 52104 KB Output is correct
7 Correct 1355 ms 52428 KB Output is correct
8 Correct 856 ms 32296 KB Output is correct
9 Correct 1318 ms 52880 KB Output is correct
10 Correct 1112 ms 51764 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 4 ms 768 KB Output is correct
3 Correct 3 ms 768 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 768 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 768 KB Output is correct
10 Correct 2 ms 640 KB Output is correct
11 Correct 2 ms 512 KB Output is correct
12 Correct 1643 ms 25312 KB Output is correct
13 Correct 2021 ms 14220 KB Output is correct
14 Correct 763 ms 6008 KB Output is correct
15 Correct 2403 ms 19016 KB Output is correct
16 Correct 872 ms 31736 KB Output is correct
17 Correct 1600 ms 23800 KB Output is correct
18 Correct 2670 ms 33268 KB Output is correct
19 Correct 2327 ms 33400 KB Output is correct
20 Correct 2514 ms 32872 KB Output is correct
21 Correct 1 ms 384 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 4 ms 768 KB Output is correct
3 Correct 5 ms 768 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 768 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 768 KB Output is correct
10 Correct 2 ms 640 KB Output is correct
11 Correct 2 ms 512 KB Output is correct
12 Correct 1356 ms 53856 KB Output is correct
13 Correct 1146 ms 54204 KB Output is correct
14 Correct 1335 ms 52032 KB Output is correct
15 Correct 1250 ms 52404 KB Output is correct
16 Correct 925 ms 32164 KB Output is correct
17 Correct 1348 ms 52860 KB Output is correct
18 Correct 1462 ms 51808 KB Output is correct
19 Correct 1889 ms 25564 KB Output is correct
20 Correct 2150 ms 13964 KB Output is correct
21 Correct 821 ms 6004 KB Output is correct
22 Correct 2342 ms 18948 KB Output is correct
23 Correct 873 ms 31844 KB Output is correct
24 Correct 1817 ms 23760 KB Output is correct
25 Correct 2593 ms 33416 KB Output is correct
26 Correct 2734 ms 33540 KB Output is correct
27 Correct 2827 ms 32820 KB Output is correct
28 Runtime error 1477 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 4 ms 768 KB Output is correct
3 Correct 4 ms 768 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 768 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Correct 3 ms 768 KB Output is correct
10 Correct 2 ms 640 KB Output is correct
11 Correct 2 ms 512 KB Output is correct
12 Correct 1242 ms 54212 KB Output is correct
13 Correct 1097 ms 54244 KB Output is correct
14 Correct 1365 ms 52016 KB Output is correct
15 Correct 1239 ms 52396 KB Output is correct
16 Correct 771 ms 32324 KB Output is correct
17 Correct 1279 ms 53096 KB Output is correct
18 Correct 1245 ms 51876 KB Output is correct
19 Correct 1630 ms 25720 KB Output is correct
20 Correct 2088 ms 13816 KB Output is correct
21 Correct 801 ms 5996 KB Output is correct
22 Correct 2395 ms 19208 KB Output is correct
23 Correct 906 ms 31864 KB Output is correct
24 Correct 1556 ms 23928 KB Output is correct
25 Correct 2542 ms 33680 KB Output is correct
26 Correct 2395 ms 33784 KB Output is correct
27 Correct 2229 ms 33016 KB Output is correct
28 Runtime error 1148 ms 256000 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -