oj.uz

Submission #943706

# Submission time Handle Problem Language Result Execution time Memory
943706 2024-03-11T18:24:05 Z KG07 Comparing Plants (IOI20_plants) C++14
43 / 100
 795 ms 136620 KB 
#include "plants.h"
#include <bits/stdc++.h>
using namespace std;

struct segment_tree{
    int hmin[800008], lazy[800008], hmax[800008], heights[200002];
    vector<long long> left_child[200002], right_child[200002];
    vector<int> m, H;
    int n, h, k;
    void init(int K, vector<int> M){
        n = M.size();
        h = n-1;
        k = K;
        m.clear();
        for(int i = 0; i < 800008; i++){
            hmin[i] = 0;
            lazy[i] = 0;
            hmax[i] = -1;
        }
        for(int i = 0; i < M.size(); i++){
            m.push_back(M[i]);
            H.push_back(-1);
        }
        init_heights(1, 1, n);
    }
    void lazy_update(int N){
        lazy[2*N] += lazy[N];
        lazy[2*N+1] += lazy[N];
        hmin[2*N] += lazy[N];
        hmin[2*N+1] += lazy[N];
        lazy[N] = 0;
    }
    void update(int N, int l, int r, int s, int t){
        if(l > t || r < s)return;
        if(l <= s && r >= t){
            lazy[N]--;
            hmin[N]--;
            return;
        }
        lazy_update(N);
        update(2*N, l, r, s, (s+t)/2);
        update(2*N+1, l, r, (s+t)/2+1, t);
        hmin[N] = min(hmin[2*N], hmin[2*N+1]);
    }
    void init_heights(int N, int l, int r){
        if(l == r){
            hmin[N] = m[r-1];
            return;
        }
        init_heights(2*N, l, (l+r)/2);
        init_heights(2*N+1, (l+r)/2+1, r);
        hmin[N] = min(hmin[2*N], hmin[2*N+1]);
    }
    int get_min(int N, int l, int r, int s, int t){
        if(l > t || r < s)return 1000000000;
        if(l <= s && r >= t)return hmin[N];
        lazy_update(N);
        return min(get_min(2*N, l, r, s, (s+t)/2), get_min(2*N+1, l, r, (s+t)/2+1, t));
    }
    int get_max(int N, int l, int r, int s, int t){
        if(l > t || r < s)return -1;
        if(l <= s && r >= t)return hmax[N];
        return max(get_max(2*N, l, r, s, (s+t)/2), get_max(2*N+1, l, r, (s+t)/2+1, t));
    }
    int left_zero(int N, int l, int r, int s, int t){
        if(l > t || r < s)return -1;
        if(s == t)return hmin[N] == 0 ? s : -1;
        lazy_update(N);
        if(l <= s && r >= t){
            if(hmin[N]>0)return -1;
            if(hmin[2*N+1]>0)return left_zero(2*N, l, r, s, (s+t)/2);
            return left_zero(2*N+1, l, r, (s+t)/2+1, t);
        }
        int z = left_zero(2*N+1, l, r, (s+t)/2+1, t);
        return z == -1 ? left_zero(2*N, l, r, s, (s+t)/2) : z;
    }
    int right_zero(int N, int l, int r, int s, int t){
        if(l > t || r < s)return -1;
        if(s == t)return hmin[N] == 0 ? t : -1;
        lazy_update(N);
        if(l <= s && r >= t){
            if(hmin[N]>0)return -1;
            if(hmin[2*N]>0)return right_zero(2*N+1, l, r, (s+t)/2+1, t);
            return right_zero(2*N, l, r, s, (s+t)/2);
        }
        int z = right_zero(2*N, l, r, s, (s+t)/2);
        return z == -1 ? right_zero(2*N+1, l, r, (s+t)/2+1, t) : z;
    }
    void point_update(int N, int M, int l, int r){
        if(l > M || r < M)return;
        if(l == r){
            hmin[N] = 1000000;
            return;
        }
        lazy_update(N);
        point_update(2*N, M, l, (l+r)/2);
        point_update(2*N+1, M, (l+r)/2+1, r);
        hmin[N] = min(hmin[2*N], hmin[2*N+1]);
    }
    void extract(int N, int M, int l, int r){
        if(l > M || r < M)return;
        if(l == r){
            while(true)
            if(M > 1 && left_zero(1, max(1, M-k), M-1, 1, n) != -1){
                extract(1, left_zero(1, max(1, M-k), M-1, 1, n), 1, n);
            }
            else if(M-k < 1 && left_zero(1, n+M-k, n, 1, n) != -1){
                extract(1, left_zero(1, n+M-k, n, 1, n), 1, n);
            }
            else break;
            if(k*2+2<=n){
                heights[M-1] = h;
                H[h--] = M-1;
            }
            else H[M-1] = h--;
            point_update(1, M, 1, n);
            if(M > 1)update(1, max(1, M-k), M-1, 1, n);
            if(M-k < 1)update(1, n+M-k, n, 1, n);
            return;
        }
        lazy_update(N);
        extract(2*N, M, l, (l+r)/2);
        extract(2*N+1, M, (l+r)/2+1, r);
        hmin[N] = min(hmin[2*N], hmin[2*N+1]);
    }
    void insert_plant(int N, int M, int z, int l, int r){
        if(l > M || r < M)return;
        if(l == r){
            hmax[N] = z;
            return;
        }
        insert_plant(2*N, M, z, l, (l+r)/2);
        insert_plant(2*N+1, M, z, (l+r)/2+1, r);
        hmax[N] = max(hmax[2*N], hmax[2*N+1]);
    }
    void create_child(){
        for(int i = 0; i < H.size(); i++){
            int M = H[i]+1;
            insert_plant(1, M, i, 1, n);
            int z;
            z = max(M>1?get_max(1, max(1, M-k), M-1, 1, n):-1, M-k<1?get_max(1, n+M-k, n, 1, n):-1);
            if(z>-1){
                left_child[M-1].push_back(M-1-H[z]>0?M-1-H[z]:n+M-1-H[z]);
                while(left_child[M-1].size()<=left_child[(M-1+n-left_child[M-1][left_child[M-1].size()-1])%n].size())
                    left_child[M-1].push_back(left_child[M-1][left_child[M-1].size()-1]+
                        left_child[(M-1+n-left_child[M-1][left_child[M-1].size()-1])%n][left_child[M-1].size()-1]);
            }
            z = max(M<n?get_max(1, M+1, min(M+k, n), 1, n):-1, M+k>n?get_max(1, 1, M+k-n, 1, n):-1);
            if(z>-1){
                right_child[M-1].push_back(H[z]-M+1>0?H[z]-M+1:n-M+1+H[z]);
                while(right_child[M-1].size()<=right_child[(M-1+right_child[M-1][right_child[M-1].size()-1])%n].size())
                    right_child[M-1].push_back(right_child[M-1][right_child[M-1].size()-1]+
                        right_child[(M-1+right_child[M-1][right_child[M-1].size()-1])%n][right_child[M-1].size()-1]);
            }
        }
    }
    bool reach_left(long long x, long long y, int z){
        if(z > left_child[x].size())return reach_left(x, y, left_child[x].size());
        while(z && left_child[x][z-1] > y)z--;
        if(z == 0)return heights[x] == heights[(x+n-y)%n] || (left_child[x].size() > 0 && heights[x] > heights[(x+n-y)%n]);
        return reach_left((x+n-left_child[x][z-1])%n, y-left_child[x][z-1], z-1);
    }
    bool reach_right(long long x, long long y, int z){
        if(z > right_child[x].size())return reach_right(x, y, right_child[x].size());
        while(z && right_child[x][z-1] > y)z--;
        if(z == 0)return heights[x] == heights[(x+y)%n] || (right_child[x].size() > 0 && heights[x] > heights[(x+y)%n]);
        return reach_right((x+right_child[x][z-1])%n, y-right_child[x][z-1], z-1);
    }
} A;

void init(int k, vector<int> r) {
    A.init(k-1, r);
    int n = r.size();
    while(A.h >= 0){
        A.extract(1, A.right_zero(1, 1, n, 1, n), 1, n);
    }
    if(k*2<=A.n)A.create_child();
	return;
}

int compare_plants(int x, int y) {
    if(A.k*2+2>A.n)return A.H[x] > A.H[y] ? 1 : -1;
    if(A.reach_left(x, (x+A.n-y)%A.n, 30) || A.reach_right(x, (y+A.n-x)%A.n, 30))return 1;
    if(A.reach_left(y, (y+A.n-x)%A.n, 30) || A.reach_right(y, (x+A.n-y)%A.n, 30))return -1;
    return 0;
}

Compilation message

plants.cpp: In member function 'void segment_tree::init(int, std::vector<int>)':
plants.cpp:20:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |         for(int i = 0; i < M.size(); i++){
      |                        ~~^~~~~~~~~~
plants.cpp: In member function 'void segment_tree::create_child()':
plants.cpp:137:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  137 |         for(int i = 0; i < H.size(); i++){
      |                        ~~^~~~~~~~~~
plants.cpp: In member function 'bool segment_tree::reach_left(long long int, long long int, int)':
plants.cpp:158:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  158 |         if(z > left_child[x].size())return reach_left(x, y, left_child[x].size());
      |            ~~^~~~~~~~~~~~~~~~~~~~~~
plants.cpp: In member function 'bool segment_tree::reach_right(long long int, long long int, int)':
plants.cpp:164:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  164 |         if(z > right_child[x].size())return reach_right(x, y, right_child[x].size());
      |            ~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 19804 KB Output is correct
2 Correct 4 ms 19848 KB Output is correct
3 Correct 4 ms 19804 KB Output is correct
4 Correct 4 ms 19804 KB Output is correct
5 Correct 4 ms 19844 KB Output is correct
6 Correct 52 ms 23676 KB Output is correct
7 Correct 106 ms 26964 KB Output is correct
8 Correct 305 ms 38016 KB Output is correct
9 Correct 355 ms 44332 KB Output is correct
10 Correct 412 ms 53424 KB Output is correct
11 Correct 470 ms 56072 KB Output is correct
12 Correct 490 ms 61396 KB Output is correct
13 Correct 573 ms 73336 KB Output is correct
14 Correct 603 ms 73392 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 19800 KB Output is correct
2 Correct 4 ms 19804 KB Output is correct
3 Correct 4 ms 19804 KB Output is correct
4 Correct 4 ms 19804 KB Output is correct
5 Correct 5 ms 19804 KB Output is correct
6 Correct 6 ms 20084 KB Output is correct
7 Correct 50 ms 22868 KB Output is correct
8 Correct 5 ms 20060 KB Output is correct
9 Correct 6 ms 20060 KB Output is correct
10 Correct 51 ms 22868 KB Output is correct
11 Correct 50 ms 22736 KB Output is correct
12 Correct 48 ms 22868 KB Output is correct
13 Correct 50 ms 22868 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 19800 KB Output is correct
2 Correct 4 ms 19804 KB Output is correct
3 Correct 4 ms 19804 KB Output is correct
4 Correct 4 ms 19804 KB Output is correct
5 Correct 5 ms 19804 KB Output is correct
6 Correct 6 ms 20084 KB Output is correct
7 Correct 50 ms 22868 KB Output is correct
8 Correct 5 ms 20060 KB Output is correct
9 Correct 6 ms 20060 KB Output is correct
10 Correct 51 ms 22868 KB Output is correct
11 Correct 50 ms 22736 KB Output is correct
12 Correct 48 ms 22868 KB Output is correct
13 Correct 50 ms 22868 KB Output is correct
14 Correct 67 ms 23380 KB Output is correct
15 Correct 300 ms 26428 KB Output is correct
16 Correct 67 ms 23296 KB Output is correct
17 Correct 297 ms 26312 KB Output is correct
18 Correct 221 ms 26308 KB Output is correct
19 Correct 223 ms 26312 KB Output is correct
20 Correct 291 ms 26376 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 19804 KB Output is correct
2 Correct 4 ms 19804 KB Output is correct
3 Correct 81 ms 23544 KB Output is correct
4 Correct 795 ms 136620 KB Output is correct
5 Correct 710 ms 84800 KB Output is correct
6 Runtime error 283 ms 56872 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 19800 KB Output is correct
2 Correct 4 ms 19804 KB Output is correct
3 Correct 4 ms 19804 KB Output is correct
4 Correct 4 ms 19804 KB Output is correct
5 Correct 4 ms 19804 KB Output is correct
6 Correct 6 ms 20108 KB Output is correct
7 Correct 18 ms 20828 KB Output is correct
8 Correct 16 ms 20880 KB Output is correct
9 Correct 20 ms 20968 KB Output is correct
10 Correct 17 ms 20828 KB Output is correct
11 Correct 18 ms 20896 KB Output is correct
12 Correct 19 ms 20824 KB Output is correct
13 Correct 14 ms 20828 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 19800 KB Output is correct
2 Correct 4 ms 19804 KB Output is correct
3 Correct 4 ms 19800 KB Output is correct
4 Correct 4 ms 19804 KB Output is correct
5 Correct 6 ms 20128 KB Output is correct
6 Correct 481 ms 56744 KB Output is correct
7 Runtime error 421 ms 95244 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 19804 KB Output is correct
2 Correct 4 ms 19848 KB Output is correct
3 Correct 4 ms 19804 KB Output is correct
4 Correct 4 ms 19804 KB Output is correct
5 Correct 4 ms 19844 KB Output is correct
6 Correct 52 ms 23676 KB Output is correct
7 Correct 106 ms 26964 KB Output is correct
8 Correct 305 ms 38016 KB Output is correct
9 Correct 355 ms 44332 KB Output is correct
10 Correct 412 ms 53424 KB Output is correct
11 Correct 470 ms 56072 KB Output is correct
12 Correct 490 ms 61396 KB Output is correct
13 Correct 573 ms 73336 KB Output is correct
14 Correct 603 ms 73392 KB Output is correct
15 Correct 4 ms 19800 KB Output is correct
16 Correct 4 ms 19804 KB Output is correct
17 Correct 4 ms 19804 KB Output is correct
18 Correct 4 ms 19804 KB Output is correct
19 Correct 5 ms 19804 KB Output is correct
20 Correct 6 ms 20084 KB Output is correct
21 Correct 50 ms 22868 KB Output is correct
22 Correct 5 ms 20060 KB Output is correct
23 Correct 6 ms 20060 KB Output is correct
24 Correct 51 ms 22868 KB Output is correct
25 Correct 50 ms 22736 KB Output is correct
26 Correct 48 ms 22868 KB Output is correct
27 Correct 50 ms 22868 KB Output is correct
28 Correct 67 ms 23380 KB Output is correct
29 Correct 300 ms 26428 KB Output is correct
30 Correct 67 ms 23296 KB Output is correct
31 Correct 297 ms 26312 KB Output is correct
32 Correct 221 ms 26308 KB Output is correct
33 Correct 223 ms 26312 KB Output is correct
34 Correct 291 ms 26376 KB Output is correct
35 Correct 4 ms 19804 KB Output is correct
36 Correct 4 ms 19804 KB Output is correct
37 Correct 81 ms 23544 KB Output is correct
38 Correct 795 ms 136620 KB Output is correct
39 Correct 710 ms 84800 KB Output is correct
40 Runtime error 283 ms 56872 KB Execution killed with signal 11
41 Halted 0 ms 0 KB -