oj.uz

Submission #635263

# Submission time Handle Problem Language Result Execution time Memory
635263 2022-08-25T19:21:31 Z tutis Radio Towers (IOI22_towers) C++17
4 / 100
 3010 ms 71724 KB 
#include "towers.h"

#include <bits/stdc++.h>
using namespace std;
vector<int>H;
struct ST
{
    int l, r;
    ST *left, *right;
    int mn;
    pair<int, int> mni;
    pair<int, int> mxi;
    ST() {}
    ST(int l, int r): l(l), r(r)
    {
        if (l < r)
        {
            left = new ST(l, (l + r) / 2);
            right = new ST((l + r) / 2 + 1, r);
            mn = min(left->mn, right->mn);
            mni = min(left->mni, right->mni);
            mxi = max(left->mxi, right->mxi);
        }
        else
        {
            left = right = NULL;
            mn = H[l];
            mni = mxi = {H[l], l};
        }
    }
    int get(int x, int y)
    {
        if (x <= l && r <= y)
            return mn;
        if (r < x || y < l)
            return 2e9;
        return min(left->get(x, y), right->get(x, y));
    }
    pair<int, int> getmx(int x, int y)
    {
        if (x <= l && r <= y)
            return mxi;
        if (r < x || y < l)
            return { -2e9, 0};
        return max(left->getmx(x, y), right->getmx(x, y));
    }
    pair<int, int> getmn(int x, int y)
    {
        if (x <= l && r <= y)
            return mni;
        if (r < x || y < l)
            return { 2e9, 0};
        return min(left->getmn(x, y), right->getmn(x, y));
    }
} medis;
vector<vector<pair<int, int>>>Fl, Fr;
int N;
vector<int>prv;
vector<int>nxt;
void init(int N_, vector<int> H_) {
    N = N_;
    H = H_;
    prv = vector<int>(N, -1);
    nxt = vector<int>(N, N + 1);
    {
        vector<int>A;
        for (int i = 0; i < N; i++)
        {
            while (!A.empty() && H[A.back()] <= H[i])
                A.pop_back();
            if (!A.empty())
                prv[i] = A.back();
            A.push_back(i);
        }
        A.clear();
        for (int i = N - 1; i >= 0; i--)
        {
            while (!A.empty() && H[A.back()] <= H[i])
                A.pop_back();
            if (!A.empty())
                nxt[i] = A.back();
            A.push_back(i);
        }
    }
    vector<int> p(N);
    iota(p.begin(), p.end(), 0);
    sort(p.begin(), p.end(), [&](int a, int b) {return H[a] > H[b];});
    set<int>X;
    medis = ST(0, N - 1);
    auto get = [&](int l, int r)
    {
        if (l + 1 >= r)
            return -1;
        int h = medis.get(l + 1, r - 1);
        return max(0, min(H[l] - h, H[r] - h));
    };
    map<int, vector<pair<int, int>>>L;
    map<int, vector<pair<int, int>>>R;
    auto add = [&](int l, int r, int d, int w)
    {
        R[d].push_back({r, w});
        L[d].push_back({l, w});
    };
    for (int i : p)
    {
        int r = -1, l = -1;
        auto it = X.lower_bound(i);
        if (it != X.end())
        {
            r = *it;
        }
        if (it != X.begin())
        {
            it--;
            l = *it;
        }
        X.insert(i);
        if (l == -1 || r == -1)
        {
            if (r != -1 && i + 1 < r)
                add(i, r, get(i, r), 1);
            if (l != -1 && l + 1 < i)
                add(l, i, get(l, i), 1);
        }
        else
        {
            int d = get(l, r);
            int d1 = get(i, r);
            int d2 = get(l, i);
            if (d1 >= 0 || d2 >= 0)
            {
                add(i, r, d1, 1);
                add(l, i, d2, 1);
                assert(max(d1, d2) <= d);
                add(l, r, max(d1, d2), -1);
            }
        }
    }
    Fl = vector<vector<pair<int, int>>>(N);
    Fr = vector<vector<pair<int, int>>>(N);
    for (const auto &dd : L)
    {
        int d = dd.first;
        for (pair<int, int>lw : dd.second)
            for (int i = lw.first; i < N; i |= i + 1)
            {
                if (!Fl[i].empty() && Fl[i].back().first == d)
                    Fl[i].back().second += lw.second;
                else
                    Fl[i].push_back({d, lw.second});
            }
    }
    for (const auto &dd : R)
    {
        int d = dd.first;
        for (pair<int, int>rw : dd.second)
            for (int i = rw.first; i < N; i |= i + 1)
            {
                if (!Fr[i].empty() && Fr[i].back().first == d)
                    Fr[i].back().second += rw.second;
                else
                    Fr[i].push_back({d, rw.second});
            }
    }
    for (int i = 0; i < N; i++)
    {
        for (int j = 1; j < (int)Fl[i].size(); j++)
            Fl[i][j].second += Fl[i][j - 1].second;
        for (int j = 1; j < (int)Fr[i].size(); j++)
            Fr[i][j].second += Fr[i][j - 1].second;
    }
}
int get(int l, int r, int d)
{
    int ret = 0;
    int i = r;
    while (i >= 0)
    {
        if (!Fr[i].empty())
        {
            auto it = lower_bound(Fr[i].begin(), Fr[i].end(), make_pair(d, (int) - 1e9));
            ret += Fr[i].back().second;
            if (it != Fr[i].begin())
            {
                it--;
                ret -= it->second;
            }
        }
        i = (i & (i + 1)) - 1;
    }
    i = l - 1;
    while (i >= 0) {
        if (!Fl[i].empty())
        {
            auto it = lower_bound(Fl[i].begin(), Fl[i].end(), make_pair(d, (int) - 1e9));
            ret -= Fl[i].back().second;
            if (it != Fl[i].begin())
            {
                it--;
                ret += it->second;
            }
        }
        i = (i & (i + 1)) - 1;
    }
    return ret;
}
int max_towers(int L, int R, int D) {
    int xx = -1;
    int yy = -1;
    if (L != N - 1)
    {
        int lo = L + 1;
        int hi = N - 1;
        while (lo < hi)
        {
            int m = (lo + hi) / 2;
            if (medis.getmx(L + 1, m).first - medis.getmn(L, m).first >= D)
                hi = m;
            else
                lo = m + 1;
        }
        int m = lo;
        pair<int, int>a = medis.getmx(L + 1, m);
        pair<int, int>b = medis.getmn(L, m);
        if (a.first - b.first >= D)
        {
            if (a.second >= b.second)
                xx = a.second;
            else
                xx = nxt[a.second];
        }
    }
    if (R != 0)
    {
        int lo = 0;
        int hi = R - 1;
        while (lo < hi)
        {
            int m = (lo + hi + 1) / 2;
            if (medis.getmx(m, R - 1).first - medis.getmn(m, R).first >= D)
                lo = m;
            else
                hi = m - 1;
        }
        int m = lo;
        pair<int, int>a = medis.getmx(m, R - 1);
        pair<int, int>b = medis.getmn(m, R);
        if (a.first - b.first >= D)
        {
            if (a.second <= b.second)
                yy = a.second;
            else
                yy = prv[a.second];
        }
    }
    if (xx != -1 && yy != -1 && xx <= yy)
        return 2 + get(xx, yy, D);
    return 1;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1359 ms 14764 KB Output is correct
2 Correct 3010 ms 24536 KB Output is correct
3 Correct 2982 ms 24516 KB Output is correct
4 Correct 2996 ms 24436 KB Output is correct
5 Correct 2715 ms 24548 KB Output is correct
6 Correct 2899 ms 24460 KB Output is correct
7 Correct 2957 ms 24472 KB Output is correct
8 Correct 1 ms 208 KB Output is correct
9 Correct 1 ms 720 KB Output is correct
10 Correct 1 ms 720 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 464 KB Output is correct
2 Correct 5 ms 1488 KB Output is correct
3 Correct 5 ms 1488 KB Output is correct
4 Correct 4 ms 1488 KB Output is correct
5 Correct 4 ms 1488 KB Output is correct
6 Correct 4 ms 1488 KB Output is correct
7 Correct 4 ms 1432 KB Output is correct
8 Correct 1 ms 720 KB Output is correct
9 Correct 1 ms 720 KB Output is correct
10 Correct 3 ms 1232 KB Output is correct
11 Correct 3 ms 1488 KB Output is correct
12 Correct 0 ms 208 KB Output is correct
13 Correct 2 ms 720 KB Output is correct
14 Correct 1 ms 720 KB Output is correct
15 Correct 5 ms 1488 KB Output is correct
16 Correct 4 ms 1488 KB Output is correct
17 Correct 4 ms 1468 KB Output is correct
18 Correct 1 ms 720 KB Output is correct
19 Correct 2 ms 1104 KB Output is correct
20 Correct 5 ms 1488 KB Output is correct
21 Correct 4 ms 1360 KB Output is correct
22 Correct 4 ms 1360 KB Output is correct
23 Correct 1 ms 720 KB Output is correct
24 Incorrect 2 ms 976 KB 1st lines differ - on the 1st token, expected: '5', found: '1'
25 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 464 KB Output is correct
2 Correct 5 ms 1488 KB Output is correct
3 Correct 5 ms 1488 KB Output is correct
4 Correct 4 ms 1488 KB Output is correct
5 Correct 4 ms 1488 KB Output is correct
6 Correct 4 ms 1488 KB Output is correct
7 Correct 4 ms 1432 KB Output is correct
8 Correct 1 ms 720 KB Output is correct
9 Correct 1 ms 720 KB Output is correct
10 Correct 3 ms 1232 KB Output is correct
11 Correct 3 ms 1488 KB Output is correct
12 Correct 0 ms 208 KB Output is correct
13 Correct 2 ms 720 KB Output is correct
14 Correct 1 ms 720 KB Output is correct
15 Correct 5 ms 1488 KB Output is correct
16 Correct 4 ms 1488 KB Output is correct
17 Correct 4 ms 1468 KB Output is correct
18 Correct 1 ms 720 KB Output is correct
19 Correct 2 ms 1104 KB Output is correct
20 Correct 5 ms 1488 KB Output is correct
21 Correct 4 ms 1360 KB Output is correct
22 Correct 4 ms 1360 KB Output is correct
23 Correct 1 ms 720 KB Output is correct
24 Incorrect 2 ms 976 KB 1st lines differ - on the 1st token, expected: '5', found: '1'
25 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 3009 ms 71724 KB 4th lines differ - on the 1st token, expected: '13956', found: '13955'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 558 ms 16872 KB 1st lines differ - on the 1st token, expected: '7197', found: '7196'
2 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 464 KB Output is correct
2 Correct 5 ms 1488 KB Output is correct
3 Correct 5 ms 1488 KB Output is correct
4 Correct 4 ms 1488 KB Output is correct
5 Correct 4 ms 1488 KB Output is correct
6 Correct 4 ms 1488 KB Output is correct
7 Correct 4 ms 1432 KB Output is correct
8 Correct 1 ms 720 KB Output is correct
9 Correct 1 ms 720 KB Output is correct
10 Correct 3 ms 1232 KB Output is correct
11 Correct 3 ms 1488 KB Output is correct
12 Correct 0 ms 208 KB Output is correct
13 Correct 2 ms 720 KB Output is correct
14 Correct 1 ms 720 KB Output is correct
15 Correct 5 ms 1488 KB Output is correct
16 Correct 4 ms 1488 KB Output is correct
17 Correct 4 ms 1468 KB Output is correct
18 Correct 1 ms 720 KB Output is correct
19 Correct 2 ms 1104 KB Output is correct
20 Correct 5 ms 1488 KB Output is correct
21 Correct 4 ms 1360 KB Output is correct
22 Correct 4 ms 1360 KB Output is correct
23 Correct 1 ms 720 KB Output is correct
24 Incorrect 2 ms 976 KB 1st lines differ - on the 1st token, expected: '5', found: '1'
25 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1359 ms 14764 KB Output is correct
2 Correct 3010 ms 24536 KB Output is correct
3 Correct 2982 ms 24516 KB Output is correct
4 Correct 2996 ms 24436 KB Output is correct
5 Correct 2715 ms 24548 KB Output is correct
6 Correct 2899 ms 24460 KB Output is correct
7 Correct 2957 ms 24472 KB Output is correct
8 Correct 1 ms 208 KB Output is correct
9 Correct 1 ms 720 KB Output is correct
10 Correct 1 ms 720 KB Output is correct
11 Correct 1 ms 464 KB Output is correct
12 Correct 5 ms 1488 KB Output is correct
13 Correct 5 ms 1488 KB Output is correct
14 Correct 4 ms 1488 KB Output is correct
15 Correct 4 ms 1488 KB Output is correct
16 Correct 4 ms 1488 KB Output is correct
17 Correct 4 ms 1432 KB Output is correct
18 Correct 1 ms 720 KB Output is correct
19 Correct 1 ms 720 KB Output is correct
20 Correct 3 ms 1232 KB Output is correct
21 Correct 3 ms 1488 KB Output is correct
22 Correct 0 ms 208 KB Output is correct
23 Correct 2 ms 720 KB Output is correct
24 Correct 1 ms 720 KB Output is correct
25 Correct 5 ms 1488 KB Output is correct
26 Correct 4 ms 1488 KB Output is correct
27 Correct 4 ms 1468 KB Output is correct
28 Correct 1 ms 720 KB Output is correct
29 Correct 2 ms 1104 KB Output is correct
30 Correct 5 ms 1488 KB Output is correct
31 Correct 4 ms 1360 KB Output is correct
32 Correct 4 ms 1360 KB Output is correct
33 Correct 1 ms 720 KB Output is correct
34 Incorrect 2 ms 976 KB 1st lines differ - on the 1st token, expected: '5', found: '1'
35 Halted 0 ms 0 KB -