oj.uz

Submission #942772

# Submission time Handle Problem Language Result Execution time Memory
942772 2024-03-11T04:26:16 Z KG07 Comparing Plants (IOI20_plants) C++14
0 / 100
 4000 ms 9308 KB 
#include "plants.h"
#include <bits/stdc++.h>
using namespace std;

struct segment_tree{
    int hmin[800008], lazy[800008];
    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;
        }
        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);
    }
    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 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);
        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);
        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){
            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);
            }
            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);
            H[M-1] = h--;
            return;
        }
        lazy_update(N);
        extract(2*N, M, l, (l+r)/2);
        extract(2*N+1, M, (l+r)/2+1, r);
    }
} 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);
    }
	return;
}

int compare_plants(int x, int y) {
    return A.H[x] > A.H[y] ? 1 : -1;
}

Compilation message

plants.cpp: In member function 'void segment_tree::init(int, std::vector<int>)':
plants.cpp:18:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |         for(int i = 0; i < M.size(); i++){
      |                        ~~^~~~~~~~~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 2 ms 6492 KB Output is correct
4 Correct 2 ms 6492 KB Output is correct
5 Correct 3 ms 6488 KB Output is correct
6 Correct 9 ms 6744 KB Output is correct
7 Execution timed out 4051 ms 8976 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 2 ms 6492 KB Output is correct
4 Correct 2 ms 6492 KB Output is correct
5 Correct 3 ms 6488 KB Output is correct
6 Correct 9 ms 6744 KB Output is correct
7 Execution timed out 4051 ms 8976 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6488 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Execution timed out 4046 ms 9308 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

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

Subtask #6
0 / 15.0

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

Subtask #7
0 / 25.0

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