oj.uz

Submission #942910

# Submission time Handle Problem Language Result Execution time Memory
942910 2024-03-11T06:51:38 Z KG07 Comparing Plants (IOI20_plants) C++14
44 / 100
 326 ms 85420 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);
        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 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;
            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);
        hmin[N] = min(hmin[2*N], hmin[2*N+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);
    }
	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 6492 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 2 ms 6488 KB Output is correct
4 Incorrect 2 ms 6492 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6744 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 2 ms 6488 KB Output is correct
4 Correct 2 ms 6492 KB Output is correct
5 Correct 2 ms 6492 KB Output is correct
6 Correct 4 ms 6748 KB Output is correct
7 Correct 45 ms 11384 KB Output is correct
8 Correct 3 ms 6744 KB Output is correct
9 Correct 3 ms 7000 KB Output is correct
10 Correct 44 ms 11456 KB Output is correct
11 Correct 42 ms 11348 KB Output is correct
12 Correct 42 ms 11348 KB Output is correct
13 Correct 45 ms 11344 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6744 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 2 ms 6488 KB Output is correct
4 Correct 2 ms 6492 KB Output is correct
5 Correct 2 ms 6492 KB Output is correct
6 Correct 4 ms 6748 KB Output is correct
7 Correct 45 ms 11384 KB Output is correct
8 Correct 3 ms 6744 KB Output is correct
9 Correct 3 ms 7000 KB Output is correct
10 Correct 44 ms 11456 KB Output is correct
11 Correct 42 ms 11348 KB Output is correct
12 Correct 42 ms 11348 KB Output is correct
13 Correct 45 ms 11344 KB Output is correct
14 Correct 62 ms 12064 KB Output is correct
15 Correct 292 ms 16068 KB Output is correct
16 Correct 63 ms 12068 KB Output is correct
17 Correct 326 ms 16716 KB Output is correct
18 Correct 220 ms 16324 KB Output is correct
19 Correct 226 ms 16944 KB Output is correct
20 Correct 295 ms 16832 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Correct 2 ms 6488 KB Output is correct
3 Correct 41 ms 11504 KB Output is correct
4 Correct 244 ms 85420 KB Output is correct
5 Correct 231 ms 32176 KB Output is correct
6 Correct 276 ms 17916 KB Output is correct
7 Correct 325 ms 16580 KB Output is correct
8 Correct 307 ms 16808 KB Output is correct
9 Correct 216 ms 30124 KB Output is correct
10 Correct 198 ms 16072 KB Output is correct
11 Correct 170 ms 16072 KB Output is correct
12 Correct 198 ms 16288 KB Output is correct
13 Correct 228 ms 16320 KB Output is correct

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6488 KB Output is correct
2 Correct 2 ms 6488 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 6516 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 6492 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 2 ms 6488 KB Output is correct
4 Incorrect 2 ms 6492 KB Output isn't correct
5 Halted 0 ms 0 KB -