oj.uz

답안 #635258

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
635258 2022-08-25T18:34:14 Z tutis 송신탑 (IOI22_towers) C++17
0 / 100
 4000 ms 68332 KB 
#include "towers.h"

#include <bits/stdc++.h>
using namespace std;
struct ST
{
    int l, r;
    ST *left, *right;
    int mn;
    ST() {}
    ST(int l, int r, const vector<int>& h): l(l), r(r)
    {
        if (l < r)
        {
            left = new ST(l, (l + r) / 2, h);
            right = new ST((l + r) / 2 + 1, r, h);
            mn = min(left->mn, right->mn);
        }
        else
        {
            left = right = NULL;
            mn = h[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));
    }
} medis;
vector<vector<pair<int, int>>>Fl, Fr;
int N;
vector<int>H;
void init(int N_, vector<int> H_) {
    N = N_;
    H = H_;
    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, H);
    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;
    for (int x = L + 1; x <= R; x++)
    {
        if (medis.get(L, x - 1) + D <= H[x])
        {
            xx = x;
            break;
        }
    }
    for (int y = R; y >= L; y--)
    {
        if (medis.get(y + 1, R) + D <= H[y])
        {
            yy = y;
            break;
        }
    }
    if (xx != -1 && yy != -1 && xx <= yy)
        return 2 + get(xx, yy, D);
    return 1;
}

Subtask #1
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4043 ms 12360 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 464 KB Output is correct
2 Incorrect 4 ms 1488 KB 1st lines differ - on the 1st token, expected: '292', found: '293'
3 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 464 KB Output is correct
2 Incorrect 4 ms 1488 KB 1st lines differ - on the 1st token, expected: '292', found: '293'
3 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1395 ms 67880 KB Output is correct
2 Correct 1738 ms 68296 KB Output is correct
3 Correct 1729 ms 68332 KB Output is correct
4 Correct 1692 ms 63268 KB Output is correct
5 Correct 1659 ms 62776 KB Output is correct
6 Correct 1640 ms 63288 KB Output is correct
7 Correct 1541 ms 63392 KB Output is correct
8 Execution timed out 4018 ms 20552 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 410 ms 16064 KB 43rd lines differ - on the 1st token, expected: '1278', found: '1279'
2 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 464 KB Output is correct
2 Incorrect 4 ms 1488 KB 1st lines differ - on the 1st token, expected: '292', found: '293'
3 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4043 ms 12360 KB Time limit exceeded
2 Halted 0 ms 0 KB -