oj.uz

Submission #635284

# Submission time Handle Problem Language Result Execution time Memory
635284 2022-08-25T21:18:24 Z tutis Radio Towers (IOI22_towers) C++17
21 / 100
 1578 ms 118296 KB 
#include "towers.h"

#include <bits/stdc++.h>
using namespace std;
vector<int>H;
struct ST
{
    int l, r;
    ST *left, *right;
    int mn;
    ST() {}
    vector<pair<int, int>>V;
    vector<pair<int, int>>W;
    vector<pair<int, int>>V_;
    vector<pair<int, int>>W_;
    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);
        }
        else
        {
            left = right = NULL;
            mn = H[l];
        }
        {
            for (int i = l; i <= r; i++)
            {
                if (W.empty() || H[i] > W.back().first)
                    W.push_back({H[i], i});
            }
            int mm = 1.1e9;
            for (int i = l + 1; i <= r; i++)
            {
                mm = min(mm, H[i - 1]);
                if (V.empty() || H[i] - mm > V.back().first)
                    V.push_back({H[i] - mm, i});
            }
        }
        {
            for (int i = r; i >= l; i--)
            {
                if (W_.empty() || H[i] > W_.back().first)
                    W_.push_back({H[i], i});
            }
            int mm = 1.1e9;
            for (int i = r - 1; i >= l; i--)
            {
                mm = min(mm, H[i + 1]);
                if (V_.empty() || H[i] - mm > V_.back().first)
                    V_.push_back({H[i] - mm, i});
            }
        }
    }
    int get(int x, int y)
    {
        if (x <= l && r <= y)
            return mn;
        if (r < x || y < l)
            return 1.1e9;
        return min(left->get(x, y), right->get(x, y));
    }
    pair<int, int> get1(int L, int D, int mnl = 1.1e9)
    {
        if (L <= l)
        {
            int rr = -1;
            if (!V.empty() && V.back().first >= D)
                rr = lower_bound(V.begin(), V.end(), make_pair(D, -1))->second;
            //W-mn>=D
            //W>=D+mn
            if (!W.empty() && W.back().first >= D + mnl) {
                auto it = lower_bound(W.begin(), W.end(), make_pair(D + mnl, -1));
                int r1 = it->second;
                if (rr == -1)
                    rr = r1;
                else
                    rr = min(rr, r1);
            }
            return {rr, mn};
        }
        if (r < L)
            return { -1, 1.1e9};
        pair<int, int> i = left->get1(L, D, mnl);
        if (i.first != -1)
            return i;
        pair<int, int> j = right->get1(L, D, min(i.second, mnl));
        j.second = min(j.second, i.second);
        if (i.first != -1)
            j.first = i.first;
        return j;
    }
    pair<int, int> get2(int R, int D, int mnl = 1.1e9)
    {
        if (R >= r)
        {
            int rr = -1;
            if (!V_.empty() && V_.back().first >= D)
                rr = lower_bound(V_.begin(), V_.end(), make_pair(D, -1))->second;
            //W-mn>=D
            //W>=D+mn
            if (!W_.empty() && W_.back().first >= D + mnl) {
                auto it = lower_bound(W_.begin(), W_.end(), make_pair(D + mnl, -1));
                int r1 = it->second;
                if (rr == -1)
                    rr = r1;
                else
                    rr = min(rr, r1);
            }
            return {rr, mn};
        }
        if (l > R)
            return { -1, 1.1e9};
        pair<int, int> i = right->get2(R, D, mnl);
        if (i.first != -1)
            return i;
        pair<int, int> j = left->get2(R, D, min(i.second, mnl));
        j.second = min(j.second, i.second);
        if (i.first != -1)
            j.first = i.first;
        return j;
    }
} 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, pair<vector<pair<int, int>>, vector<pair<int, int>>>>LR;
    auto add = [&](int l, int r, int d, int w)
    {
        LR[d].second.push_back({r, w});
        LR[d].first.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 : LR)
    {
        int d = dd.first;
        for (pair<int, int>lw : dd.second.first)
            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 (pair<int, int>rw : dd.second.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 = medis.get1(L, D).first;
    int yy = medis.get2(R, D).first;
    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 573 ms 49720 KB Output is correct
2 Correct 1276 ms 87528 KB Output is correct
3 Correct 1156 ms 87540 KB Output is correct
4 Correct 1274 ms 87292 KB Output is correct
5 Correct 1263 ms 87288 KB Output is correct
6 Correct 1034 ms 87380 KB Output is correct
7 Correct 1148 ms 87320 KB Output is correct
8 Correct 0 ms 208 KB Output is correct
9 Correct 3 ms 1744 KB Output is correct
10 Correct 3 ms 1744 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 592 KB Output is correct
2 Incorrect 6 ms 2244 KB 1st lines differ - on the 1st token, expected: '292', found: '291'
3 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 592 KB Output is correct
2 Incorrect 6 ms 2244 KB 1st lines differ - on the 1st token, expected: '292', found: '291'
3 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1554 ms 103488 KB 9th lines differ - on the 1st token, expected: '22097', found: '22096'
2 Halted 0 ms 0 KB -

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 279 ms 24408 KB Output is correct
2 Correct 1578 ms 104852 KB Output is correct
3 Correct 1505 ms 103616 KB Output is correct
4 Correct 1380 ms 97912 KB Output is correct
5 Correct 1331 ms 97580 KB Output is correct
6 Correct 1526 ms 98048 KB Output is correct
7 Correct 1299 ms 98112 KB Output is correct
8 Correct 879 ms 87284 KB Output is correct
9 Correct 781 ms 87236 KB Output is correct
10 Correct 1192 ms 112812 KB Output is correct
11 Correct 970 ms 118296 KB Output is correct
12 Correct 565 ms 103996 KB Output is correct
13 Correct 557 ms 97660 KB Output is correct
14 Correct 524 ms 97736 KB Output is correct
15 Correct 142 ms 87324 KB Output is correct
16 Correct 274 ms 110680 KB Output is correct
17 Correct 552 ms 99828 KB Output is correct
18 Correct 592 ms 103724 KB Output is correct
19 Correct 590 ms 103828 KB Output is correct
20 Correct 512 ms 98156 KB Output is correct
21 Correct 505 ms 98336 KB Output is correct
22 Correct 511 ms 97980 KB Output is correct
23 Correct 555 ms 97540 KB Output is correct
24 Correct 143 ms 87232 KB Output is correct
25 Correct 164 ms 87432 KB Output is correct
26 Correct 272 ms 114108 KB Output is correct
27 Correct 166 ms 89168 KB Output is correct
28 Correct 5 ms 2128 KB Output is correct
29 Correct 5 ms 2000 KB Output is correct
30 Correct 5 ms 2000 KB Output is correct
31 Correct 3 ms 1744 KB Output is correct
32 Correct 3 ms 1872 KB Output is correct
33 Correct 3 ms 1104 KB Output is correct
34 Correct 5 ms 2128 KB Output is correct
35 Correct 5 ms 2128 KB Output is correct
36 Correct 5 ms 2000 KB Output is correct
37 Correct 6 ms 2088 KB Output is correct
38 Correct 5 ms 2124 KB Output is correct
39 Correct 5 ms 2128 KB Output is correct
40 Correct 2 ms 1744 KB Output is correct
41 Correct 2 ms 1744 KB Output is correct
42 Correct 4 ms 1872 KB Output is correct
43 Correct 4 ms 2000 KB Output is correct

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 592 KB Output is correct
2 Incorrect 6 ms 2244 KB 1st lines differ - on the 1st token, expected: '292', found: '291'
3 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 573 ms 49720 KB Output is correct
2 Correct 1276 ms 87528 KB Output is correct
3 Correct 1156 ms 87540 KB Output is correct
4 Correct 1274 ms 87292 KB Output is correct
5 Correct 1263 ms 87288 KB Output is correct
6 Correct 1034 ms 87380 KB Output is correct
7 Correct 1148 ms 87320 KB Output is correct
8 Correct 0 ms 208 KB Output is correct
9 Correct 3 ms 1744 KB Output is correct
10 Correct 3 ms 1744 KB Output is correct
11 Correct 1 ms 592 KB Output is correct
12 Incorrect 6 ms 2244 KB 1st lines differ - on the 1st token, expected: '292', found: '291'
13 Halted 0 ms 0 KB -