oj.uz

Submission #256424

# Submission time Handle Problem Language Result Execution time Memory
256424 2020-08-02T16:29:02 Z Sorting Game (IOI13_game) C++17
100 / 100
 6050 ms 256000 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;
    vector<pair<int, long long>> updates;
    int sz;
 
    void get_new_node(){
        nodes.push_back(0);
        left.push_back(-1);
        right.push_back(-1);
    }
 
    SegmentTree(){
        get_new_node();
        sz = 0;
    }
 
    int update(int idx, int l, int r, int s, long long new_val){
        if(idx == 0){
            if(sz < 1){
                updates.push_back({s, new_val});
                sz++;
                return idx;
            }
            else if(sz != k_Inf){
                sz = k_Inf;
                for(auto [s, new_val]: updates)
                    update(0, 0, k_Inf, s, new_val);
                updates.clear();
            }
        }
        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 == 0){
            if(!updates.empty()){
                long long ans = 0;
                for(auto [s, new_val]: updates)
                    if(sl <= s && s <= sr)
                        ans = gcd2(new_val, ans); 
                return ans;
            }
        }
        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 7 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 4 ms 640 KB Output is correct
10 Correct 2 ms 384 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 2 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 1120 ms 32668 KB Output is correct
5 Correct 988 ms 33184 KB Output is correct
6 Correct 1293 ms 29900 KB Output is correct
7 Correct 1293 ms 29528 KB Output is correct
8 Correct 781 ms 19096 KB Output is correct
9 Correct 1202 ms 29860 KB Output is correct
10 Correct 1124 ms 28992 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 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 4 ms 544 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 1572 ms 16888 KB Output is correct
13 Correct 1949 ms 8440 KB Output is correct
14 Correct 777 ms 2552 KB Output is correct
15 Correct 2199 ms 11384 KB Output is correct
16 Correct 892 ms 19136 KB Output is correct
17 Correct 1365 ms 13624 KB Output is correct
18 Correct 2287 ms 19712 KB Output is correct
19 Correct 1931 ms 19704 KB Output is correct
20 Correct 1852 ms 19112 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 5 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 4 ms 640 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 1179 ms 32676 KB Output is correct
13 Correct 1050 ms 33184 KB Output is correct
14 Correct 1176 ms 29604 KB Output is correct
15 Correct 1150 ms 29476 KB Output is correct
16 Correct 736 ms 18968 KB Output is correct
17 Correct 1171 ms 29864 KB Output is correct
18 Correct 1119 ms 29064 KB Output is correct
19 Correct 1481 ms 16760 KB Output is correct
20 Correct 1876 ms 8312 KB Output is correct
21 Correct 791 ms 2680 KB Output is correct
22 Correct 2096 ms 11660 KB Output is correct
23 Correct 828 ms 19064 KB Output is correct
24 Correct 1324 ms 13716 KB Output is correct
25 Correct 2206 ms 20064 KB Output is correct
26 Correct 1989 ms 20088 KB Output is correct
27 Correct 1884 ms 19448 KB Output is correct
28 Correct 938 ms 104520 KB Output is correct
29 Correct 2084 ms 119156 KB Output is correct
30 Correct 4480 ms 96192 KB Output is correct
31 Correct 4310 ms 86668 KB Output is correct
32 Correct 788 ms 4212 KB Output is correct
33 Correct 995 ms 7032 KB Output is correct
34 Correct 1161 ms 117460 KB Output is correct
35 Correct 1645 ms 60224 KB Output is correct
36 Correct 3196 ms 116884 KB Output is correct
37 Correct 2645 ms 117008 KB Output is correct
38 Correct 2352 ms 116520 KB Output is correct
39 Correct 2055 ms 90812 KB Output is correct
40 Correct 1 ms 384 KB Output is correct

Subtask #5
20.0 / 20.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 0 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 512 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 1182 ms 33316 KB Output is correct
13 Correct 1038 ms 33340 KB Output is correct
14 Correct 1198 ms 30660 KB Output is correct
15 Correct 1148 ms 30628 KB Output is correct
16 Correct 750 ms 19264 KB Output is correct
17 Correct 1222 ms 30760 KB Output is correct
18 Correct 1252 ms 30244 KB Output is correct
19 Correct 1628 ms 17144 KB Output is correct
20 Correct 1961 ms 8296 KB Output is correct
21 Correct 788 ms 3704 KB Output is correct
22 Correct 2232 ms 12184 KB Output is correct
23 Correct 873 ms 19608 KB Output is correct
24 Correct 1576 ms 14712 KB Output is correct
25 Correct 2590 ms 20960 KB Output is correct
26 Correct 2370 ms 20984 KB Output is correct
27 Correct 2045 ms 20472 KB Output is correct
28 Correct 956 ms 104440 KB Output is correct
29 Correct 1972 ms 119356 KB Output is correct
30 Correct 4669 ms 96428 KB Output is correct
31 Correct 4528 ms 86648 KB Output is correct
32 Correct 800 ms 4216 KB Output is correct
33 Correct 991 ms 6904 KB Output is correct
34 Correct 1150 ms 117456 KB Output is correct
35 Correct 1745 ms 59968 KB Output is correct
36 Correct 3403 ms 116948 KB Output is correct
37 Correct 3004 ms 116660 KB Output is correct
38 Correct 2818 ms 116476 KB Output is correct
39 Correct 1557 ms 226212 KB Output is correct
40 Correct 3419 ms 256000 KB Output is correct
41 Correct 6050 ms 199964 KB Output is correct
42 Correct 5856 ms 179644 KB Output is correct
43 Correct 1955 ms 256000 KB Output is correct
44 Correct 1142 ms 10796 KB Output is correct
45 Correct 2292 ms 98472 KB Output is correct
46 Correct 4193 ms 256000 KB Output is correct
47 Correct 4371 ms 256000 KB Output is correct
48 Correct 4129 ms 256000 KB Output is correct
49 Correct 1 ms 384 KB Output is correct