oj.uz

Submission #943704

# Submission time Handle Problem Language Result Execution time Memory
943704 2024-03-11T18:20:08 Z KG07 Comparing Plants (IOI20_plants) C++14
27 / 100
 296 ms 26480 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 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 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
0 / 5.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 Incorrect 4 ms 19804 KB Output isn't correct
4 Halted 0 ms 0 KB -

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 46 ms 22728 KB Output is correct
8 Correct 5 ms 20060 KB Output is correct
9 Correct 6 ms 20060 KB Output is correct
10 Correct 47 ms 22976 KB Output is correct
11 Correct 44 ms 22824 KB Output is correct
12 Correct 45 ms 22868 KB Output is correct
13 Correct 47 ms 22876 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 46 ms 22728 KB Output is correct
8 Correct 5 ms 20060 KB Output is correct
9 Correct 6 ms 20060 KB Output is correct
10 Correct 47 ms 22976 KB Output is correct
11 Correct 44 ms 22824 KB Output is correct
12 Correct 45 ms 22868 KB Output is correct
13 Correct 47 ms 22876 KB Output is correct
14 Correct 63 ms 23376 KB Output is correct
15 Correct 294 ms 26480 KB Output is correct
16 Correct 70 ms 23144 KB Output is correct
17 Correct 293 ms 26432 KB Output is correct
18 Correct 223 ms 26432 KB Output is correct
19 Correct 218 ms 26420 KB Output is correct
20 Correct 296 ms 26312 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 19804 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 19800 KB Output is correct
2 Correct 4 ms 19800 KB Output is correct
3 Incorrect 4 ms 19804 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 15.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 Incorrect 4 ms 19804 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 25.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 Incorrect 4 ms 19804 KB Output isn't correct
4 Halted 0 ms 0 KB -