oj.uz

Submission #943717

# Submission time Handle Problem Language Result Execution time Memory
943717 2024-03-11T18:36:50 Z KG07 Comparing Plants (IOI20_plants) C++14
43 / 100
 753 ms 138296 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 5 ms 19840 KB Output is correct
3 Correct 5 ms 19804 KB Output is correct
4 Correct 4 ms 19848 KB Output is correct
5 Correct 4 ms 19996 KB Output is correct
6 Correct 60 ms 23468 KB Output is correct
7 Correct 118 ms 26120 KB Output is correct
8 Correct 315 ms 37012 KB Output is correct
9 Correct 380 ms 43112 KB Output is correct
10 Correct 534 ms 52172 KB Output is correct
11 Correct 526 ms 55152 KB Output is correct
12 Correct 527 ms 59956 KB Output is correct
13 Correct 646 ms 72284 KB Output is correct
14 Correct 705 ms 72072 KB Output is correct

Subtask #2
14.0 / 14.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 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 20060 KB Output is correct
7 Correct 51 ms 24148 KB Output is correct
8 Correct 5 ms 20056 KB Output is correct
9 Correct 6 ms 20060 KB Output is correct
10 Correct 50 ms 24144 KB Output is correct
11 Correct 49 ms 24124 KB Output is correct
12 Correct 51 ms 24148 KB Output is correct
13 Correct 50 ms 24204 KB Output is correct

Subtask #3
13.0 / 13.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 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 20060 KB Output is correct
7 Correct 51 ms 24148 KB Output is correct
8 Correct 5 ms 20056 KB Output is correct
9 Correct 6 ms 20060 KB Output is correct
10 Correct 50 ms 24144 KB Output is correct
11 Correct 49 ms 24124 KB Output is correct
12 Correct 51 ms 24148 KB Output is correct
13 Correct 50 ms 24204 KB Output is correct
14 Correct 69 ms 24568 KB Output is correct
15 Correct 295 ms 28528 KB Output is correct
16 Correct 68 ms 24660 KB Output is correct
17 Correct 302 ms 28404 KB Output is correct
18 Correct 225 ms 28100 KB Output is correct
19 Correct 223 ms 28360 KB Output is correct
20 Correct 291 ms 28452 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 82 ms 24756 KB Output is correct
4 Correct 753 ms 138296 KB Output is correct
5 Correct 632 ms 86464 KB Output is correct
6 Runtime error 286 ms 58540 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 19804 KB Output is correct
2 Correct 4 ms 19844 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 20108 KB Output is correct
7 Correct 19 ms 20896 KB Output is correct
8 Correct 16 ms 20828 KB Output is correct
9 Correct 19 ms 20828 KB Output is correct
10 Correct 16 ms 20828 KB Output is correct
11 Correct 18 ms 20888 KB Output is correct
12 Correct 19 ms 20828 KB Output is correct
13 Correct 14 ms 20872 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 19804 KB Output is correct
2 Correct 4 ms 19800 KB Output is correct
3 Correct 4 ms 19804 KB Output is correct
4 Correct 4 ms 19804 KB Output is correct
5 Correct 7 ms 20060 KB Output is correct
6 Correct 482 ms 55832 KB Output is correct
7 Runtime error 437 ms 94328 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 5 ms 19840 KB Output is correct
3 Correct 5 ms 19804 KB Output is correct
4 Correct 4 ms 19848 KB Output is correct
5 Correct 4 ms 19996 KB Output is correct
6 Correct 60 ms 23468 KB Output is correct
7 Correct 118 ms 26120 KB Output is correct
8 Correct 315 ms 37012 KB Output is correct
9 Correct 380 ms 43112 KB Output is correct
10 Correct 534 ms 52172 KB Output is correct
11 Correct 526 ms 55152 KB Output is correct
12 Correct 527 ms 59956 KB Output is correct
13 Correct 646 ms 72284 KB Output is correct
14 Correct 705 ms 72072 KB Output is correct
15 Correct 4 ms 19804 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 4 ms 19804 KB Output is correct
20 Correct 6 ms 20060 KB Output is correct
21 Correct 51 ms 24148 KB Output is correct
22 Correct 5 ms 20056 KB Output is correct
23 Correct 6 ms 20060 KB Output is correct
24 Correct 50 ms 24144 KB Output is correct
25 Correct 49 ms 24124 KB Output is correct
26 Correct 51 ms 24148 KB Output is correct
27 Correct 50 ms 24204 KB Output is correct
28 Correct 69 ms 24568 KB Output is correct
29 Correct 295 ms 28528 KB Output is correct
30 Correct 68 ms 24660 KB Output is correct
31 Correct 302 ms 28404 KB Output is correct
32 Correct 225 ms 28100 KB Output is correct
33 Correct 223 ms 28360 KB Output is correct
34 Correct 291 ms 28452 KB Output is correct
35 Correct 4 ms 19804 KB Output is correct
36 Correct 4 ms 19804 KB Output is correct
37 Correct 82 ms 24756 KB Output is correct
38 Correct 753 ms 138296 KB Output is correct
39 Correct 632 ms 86464 KB Output is correct
40 Runtime error 286 ms 58540 KB Execution killed with signal 11
41 Halted 0 ms 0 KB -