Submission #636358

#	Time	Username	Problem	Language	Result	Execution time	Memory
636358		CodePlatina	Radio Towers (IOI22_towers)	C++17	100 / 100	1850 ms	494864 KiB

towers

#include "towers.h"
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <utility>
#include <tuple>
#define pii pair<int, int>
#define piii pair<int, pii>
#define pll pair<long long, long long>
#define plll pair<long long, pll>
#define tiii tuple<int, int, int>
#define tiiii tuple<int, int, int, int>
#define ff first
#define ss second
#define ee ss.ff
#define rr ss.ss
#define DEBUG
const int INF = (int)1e9 + 7;

using namespace std;

int N, M;
vector<int> H;
vector<int> P;
vector<int> indx;
vector<pii> indm;
vector<pii> LD, RD;
vector<int> GD;
vector<int> DS;
vector<int> DH;
vector<int> Lroot, Rroot, LDroot, RDroot;

int qryx(int l, int r)
{
    int ret = 0;
    for(int x = l + N, y = r + N; x != y; x >>= 1, y >>= 1)
    {
        if(x & 1) ret = max(ret, indx[x++]);
        if(y & 1) ret = max(ret, indx[--y]);
    }
    return ret;
}

int qrym(int l, int r)
{
    pii ret = {INF, INF};
    for(int x = l + N, y = r + N; x != y; x >>= 1, y >>= 1)
    {
        if(x & 1) ret = min(ret, indm[x++]);
        if(y & 1) ret = min(ret, indm[--y]);
    }
    return ret.ss;
}

struct SEG
{
    struct Node
    {
        int x;
        int l, r;
        Node(void) : x(0), l(-1), r(-1) {}
    }nd[40404040];
    int cnt = 0;

    int init(int s, int e, const vector<int> &V)
    {
        int ret = cnt++;

        if(s + 1 == e)
        {
            nd[ret].x = V[s];
            return ret;
        }

        int mid = s + e >> 1;
        nd[ret].l = init(s, mid, V);
        nd[ret].r = init(mid, e, V);
        nd[ret].x = nd[nd[ret].l].x + nd[nd[ret].r].x;
        return ret;
    }

    int upd(int ind, int s, int e, int x, int v)
    {
        int ret = cnt++;
        nd[ret] = nd[ind];

        if(s + 1 == e)
        {
            nd[ret].x += v;
            return ret;
        }

        int mid = s + e >> 1;
        if(x < mid) nd[ret].l = upd(nd[ret].l, s, mid, x, v);
        else nd[ret].r = upd(nd[ret].r, mid, e, x, v);
        nd[ret].x = nd[nd[ret].l].x + nd[nd[ret].r].x;
        return ret;
    }

    int qry(int ind, int s, int e, int l, int r)
    {
        if(e <= l || r <= s) return 0;
        if(l <= s && e <= r) return nd[ind].x;

        int mid = s + e >> 1;
        return qry(nd[ind].l, s, mid, l, r) + qry(nd[ind].r, mid, e, l, r);
    }
}seg;

void init(int _N, vector<int> _H)
{
    N = _N;
    H = _H;
    for(int i = 0; i < N; ++i) P.push_back(i);
    sort(P.begin(), P.end(), [](int x, int y){return H[x] < H[y];});
    indx.resize(2 * N);
    for(int i = 0; i < N; ++i) indx[i + N] = H[i];
    for(int i = N - 1; i >= 1; --i) indx[i] = max(indx[i << 1], indx[i << 1 | 1]);
    indm.resize(2 * N);
    for(int i = 0; i < N; ++i) indm[i + N] = { H[i], i };
    for(int i = N - 1; i >= 1; --i) indm[i] = min(indm[i << 1], indm[i << 1 | 1]);
    set<int> S;
    LD.resize(N);
    RD.resize(N);
    GD.resize(N);
    for(int i : P)
    {
        auto it = S.lower_bound(i);
        int l = (it == S.begin() ? -1 : *prev(it));
        int r = (it == S.end() ? N : *it);
        LD[i] = { l, qryx(l + 1, i + 1) - H[i] };
        RD[i] = { r, qryx(i, r) - H[i] };
        GD[i] = min(LD[i].ss, RD[i].ss);
        DH.push_back(LD[i].ss);
        DH.push_back(RD[i].ss);
        S.insert(i);
    }
    sort(DH.begin(), DH.end());
    DH.resize(unique(DH.begin(), DH.end()) - DH.begin());
    M = DH.size();
    for(int i = 0; i < N; ++i)
    {
        LD[i].ss = lower_bound(DH.begin(), DH.end(), LD[i].ss) - DH.begin();
        RD[i].ss = lower_bound(DH.begin(), DH.end(), RD[i].ss) - DH.begin();
        GD[i] = lower_bound(DH.begin(), DH.end(), GD[i]) - DH.begin();
        DS.push_back(GD[i]);
    }
    sort(DS.begin(), DS.end());
    Lroot.resize(N + 1);
    Rroot.resize(N + 1);
    vector<int> tmp(M);
    vector<int> ls[N + 1];
    for(int i = 0; i < N; ++i) ++tmp[GD[i]], ls[LD[i].ff + 1].push_back(i);
    Lroot[0] = Rroot[N] = seg.init(0, M, tmp);
    for(int i = 0; i <= N; ++i)
    {
        if(i) Lroot[i] = Lroot[i - 1];
        for(auto x : ls[i])
        {
            Lroot[i] = seg.upd(Lroot[i], 0, M, GD[x], -1);
            Lroot[i] = seg.upd(Lroot[i], 0, M, RD[x].ss, 1);
        }
    }
    for(auto &v : ls) v.clear();
    for(int i = 0; i < N; ++i) ls[RD[i].ff].push_back(i);
    for(int i = N - 1; i >= 0; --i)
    {
        Rroot[i] = Rroot[i + 1];
        for(auto x : ls[i + 1])
        {
            Rroot[i] = seg.upd(Rroot[i], 0, M, GD[x], -1);
            Rroot[i] = seg.upd(Rroot[i], 0, M, LD[x].ss, 1);
        }
    }
    LDroot.resize(N);
    LDroot[0] = seg.init(0, M, vector<int>(M));
    for(int i = 1; i < N; ++i) LDroot[i] = seg.upd(LDroot[i - 1], 0, M, RD[i - 1].ss, 1);
    RDroot.resize(N);
    RDroot[N - 1] = LDroot[0];
    for(int i = N - 2; i >= 0; --i) RDroot[i] = seg.upd(RDroot[i + 1], 0, M, LD[i + 1].ss, 1);


//    for(int i = 0; i < N; ++i)
//    {
//        cout << LD[i].ff << ' ' << LD[i].ss << ' ' << RD[i].ff << ' ' << RD[i].ss << endl;
//    }
}

int max_towers(int L, int R, int D)
{
    int x = qryx(L, R + 1);
    int m = qrym(L, R + 1);
    if(x - H[m] < D) return 1;
    D = lower_bound(DH.begin(), DH.end(), D) - DH.begin();
//    cout << seg.qry(Lroot[L], 0, M, D, M) << endl;
//    cout << seg.qry(Rroot[R], 0, M, D, M) << endl;
//    cout << (DS.end() - lower_bound(DS.begin(), DS.end(), D)) << endl;
//    cout << (GD[m] >= D ? 1 : 0) << endl;
//    cout << (LD[m].ss >= D ? 1 : 0) << endl;
//    cout << (RD[m].ss >= D ? 1 : 0) << endl;
//    cout << seg.qry(LDroot[L], 0, M, D, M) << endl;
//    cout << seg.qry(RDroot[R], 0, M, D, M) << endl;
    return seg.qry(Lroot[L], 0, M, D, M) + seg.qry(Rroot[R], 0, M, D, M)
            - (DS.end() - lower_bound(DS.begin(), DS.end(), D))
            + (GD[m] >= D ? 1 : 0) - (LD[m].ss >= D ? 1 : 0) - (RD[m].ss >= D ? 1 : 0)
            - seg.qry(LDroot[L], 0, M, D, M) - seg.qry(RDroot[R], 0, M, D, M) + 1;
}

Compilation message (stderr)

towers.cpp: In member function 'int SEG::init(int, int, const std::vector<int>&)':
towers.cpp:76:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   76 |         int mid = s + e >> 1;
      |                   ~~^~~
towers.cpp: In member function 'int SEG::upd(int, int, int, int, int)':
towers.cpp:94:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   94 |         int mid = s + e >> 1;
      |                   ~~^~~
towers.cpp: In member function 'int SEG::qry(int, int, int, int, int)':
towers.cpp:106:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  106 |         int mid = s + e >> 1;
      |                   ~~^~~

• Subtask 1: 4 / 4
• Subtask 2: 11 / 11
• Subtask 3: 12 / 12
• Subtask 4: 14 / 14
• Subtask 5: 17 / 17
• Subtask 6: 19 / 19
• Subtask 7: 23 / 23