oj.uz

답안 #1015847

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1015847 2024-07-06T22:17:32 Z u_suck_o 식물 비교 (IOI20_plants) C++17
27 / 100
 4000 ms 14248 KB 
#include "bits/stdc++.h"
#include "plants.h"
#define MAXN 200005
#define SZ 524290

using namespace std;

pair<int, int> seg[SZ];
int lazy[SZ];
int h[MAXN];
int n, newn;

void prop(int node) {
    seg[2*node].first += lazy[node];
    seg[2*node+1].first += lazy[node];
    lazy[2*node] += lazy[node];
    lazy[2*node+1] += lazy[node];
    lazy[node] = 0;
}

void upd(int node, int l, int r, int ql, int qr, int val) {
    if (l > qr || r < ql)
        return;
    if (ql <= l && r <= qr) {
        seg[node].first += val;
        lazy[node] += val;
        return;
    }
    prop(node);
    int mid = (l+r)/2;
    upd(2*node, l, mid, ql, qr, val);
    upd(2*node+1, mid+1, r, ql, qr, val);
    seg[node] = min(seg[2*node], seg[2*node+1]);
}

pair<int, int> query(int node, int l, int r, int ql, int qr) {
    if (l > qr || r < ql)
        return {1e9, -1};
    if (ql <= l && r <= qr)
        return seg[node];
    prop(node);
    int mid = (l+r)/2;
    return min(query(2*node, l, mid, ql, qr), query(2*node+1, mid+1, r, ql, qr));
}

void init(int k, vector<int> r) {
    n = r.size();
    newn = pow(2, ceil(log2(n)));
    r.insert(r.begin() + 0, -1);
    for (int i = 1; i <= n; i++)
        seg[newn+i-1].second = i;
    for (int i = 1; i <= n; i++)
        upd(1, 1, newn, i, i, r[i]);
    
    for (int height = n; height >= 1; height--) {
        //find zeroes
        int z = query(1, 1, newn, 1, n).second;
        while (true) {
            if (z-k+1 >= 1) {
                auto p = query(1, 1, newn, z-k+1, z-1);
                if (p.first > 0)
                    break;
                else
                    z = p.second;
            } else {
                auto p1 = query(1, 1, newn, z-k+1+n, n);
                if (p1.first == 0)
                    z = p1.second;
                else {
                    auto p2 = query(1, 1, newn, 1, z-1);
                    if (p2.first == 0)
                        z = p2.second;
                    else
                        break;
                }
            }
        }
        upd(1, 1, newn, z, z, 1e9);
        h[z] = height;
        if (z-k+1 >= 1)
            upd(1, 1, newn, z-k+1, z-1, -1);
        else {
            upd(1, 1, newn, z-k+1+n, n, -1);
            upd(1, 1, newn, 1, z-1, -1);
        }
    }
    return;
}

int compare_plants(int x, int y) {
    if (h[x+1] > h[y+1]) return 1;
    else return -1;
    return 0;
}

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Incorrect 0 ms 2396 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 1 ms 2392 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 3 ms 2396 KB Output is correct
7 Correct 39 ms 7236 KB Output is correct
8 Correct 1 ms 2392 KB Output is correct
9 Correct 2 ms 2632 KB Output is correct
10 Correct 39 ms 7252 KB Output is correct
11 Correct 36 ms 7248 KB Output is correct
12 Correct 43 ms 7252 KB Output is correct
13 Correct 39 ms 7156 KB Output is correct

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 1 ms 2392 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 3 ms 2396 KB Output is correct
7 Correct 39 ms 7236 KB Output is correct
8 Correct 1 ms 2392 KB Output is correct
9 Correct 2 ms 2632 KB Output is correct
10 Correct 39 ms 7252 KB Output is correct
11 Correct 36 ms 7248 KB Output is correct
12 Correct 43 ms 7252 KB Output is correct
13 Correct 39 ms 7156 KB Output is correct
14 Correct 63 ms 7940 KB Output is correct
15 Correct 351 ms 14144 KB Output is correct
16 Correct 66 ms 7732 KB Output is correct
17 Correct 379 ms 14176 KB Output is correct
18 Correct 286 ms 13856 KB Output is correct
19 Correct 248 ms 14248 KB Output is correct
20 Correct 368 ms 14144 KB Output is correct

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 42 ms 6900 KB Output is correct
4 Execution timed out 4066 ms 12616 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Incorrect 1 ms 2392 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Incorrect 0 ms 2392 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Incorrect 0 ms 2396 KB Output isn't correct
5 Halted 0 ms 0 KB -