제출 #914787

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
914787		vjudge1	송신탑 (IOI22_towers)	C++17	0 / 100	24 ms	18328 KiB

towers

#include "towers.h"

#include <bits/stdc++.h>
using namespace std;
typedef int ll;
using pl = pair<ll, ll>;
using vl = vector<ll>;
#define F(i, l, r) for (ll i = ll(l); i < ll(r); ++i)
#define FD(i, l, r) for (ll i = ll(l); i > ll(r); --i)
#define A(a) (a).begin(), (a).end()
#define K first
#define V second

template<typename T> struct SparseTable {
    int n,log2=0;
    function<T(T, T)> merge;
    T id ;
    vector<vector<T>> a = {{}};
    SparseTable(const vector<T>& v, function<T(T, T)> _merge, T _id): merge(_merge), id(_id) {
        n = v.size();
        while((1<<log2) <= n) {
            ++log2;
        }
        a.resize(log2);
        a[0] = v;
        for(int i=1,len=1;i<log2;++i,len*=2) {
            a[i].resize(n + 1 - (1<<i));
            for(size_t j=0;j<a[i].size();++j) {
                a[i][j] = merge(a[i-1][j], a[i-1][j + len]);
            }
        }
    }
    SparseTable(){}
    T query(int l, int r) { // [l,r)
        if (r <= l) return id;
        int len = __lg(r-l);
        return merge(a[len][l], a[len][r- (1<<len)]);
    }   
};

SparseTable<ll> spmin;
 

const int MAXN = 100010, INF = 1000000010;

namespace seg {
    pl merge(pl a, pl b) {
        return pair(min(a.K, b.K), max(a.V, b.V));
    }

    struct node{
        vector<pl> vec;
        vector<pl> indices; // {mn, mx}
        node(){};
        node(int value, int pos){
            vec.emplace_back(value, pos);
            indices.emplace_back(pos, pos);
        }
        node(node& a, node& b){
            vec.resize(a.vec.size() + b.vec.size());
            indices.resize(vec.size());
            merge(a.vec.begin(), a.vec.end(), b.vec.begin(), b.vec.end(), vec.begin());
            pl cur(MAXN, -1);

            // All items are now in sorted order, relative to first key.
            // Now mn and max represent the range of indices or something?  
            // for the suffix max.
            FD(i, ll(vec.size())-1, -1) indices[i] = merge(pair(vec[i].V, vec[i].V), cur);
        }
    };

    node tr[2*MAXN];

    pair<int, pl> query(int l, int r, int x){
        int ret=0;
        pl res(MAXN, -1);

        auto handle = [&](node& cur) {
            auto &[vec, indices] = cur;
            auto itr = lower_bound(A(vec), pair(x, -1));
            int pos = (int)(itr - vec.begin());
            ret += (int)(vec.end() - itr);
            if(itr!=vec.end()) res = merge(res, indices[pos]);
        };

        for(l+=MAXN, r+=MAXN; l<r; l>>=1, r>>=1){
            if(l&1) handle(tr[l++]);
            if(r&1) handle(tr[--r]);
        }

        return {ret, res};
    }

    void build(vl res) {
        F(i, 0, res.size()) seg::tr[MAXN+i]=seg::node(res[i], i);
        FD(i, MAXN-1, -1) tr[i]=node(tr[i<<1], tr[i<<1|1]);
    }
}
 
 
int arr[MAXN];
 
void init(int n, vector<int> H) {
    vl maxl(n), maxr(n);
    copy(A(H), arr);

    spmin = SparseTable<ll>(H, [](ll a, ll b) {
        return min(a, b);
    }, INF);

    F(i, 0, n) {
        int x;
        for(x=i-1; x!=-1 && H[x]<H[i]; x=maxl[x]);
        maxl[i]=x;
    }

    FD(i, n-1, -1) {
        int x;
        for(x=i+1; x!=n && H[x]<H[i]; x=maxr[x]);
        maxr[i]=x;
    }
    // maxl and maxr finds closest node greater than it to left and right 

    vl res(n);
    F(i, 0, n) cout << H[i] << " "; cout << endl;

    F(i, 0, n) {
        int l = maxl[i], r = maxr[i];
        int a = H[i] - spmin.query(l+1, i);
        int b = H[i] - spmin.query(i+1, r);
        res[i] = min(a, b);
    }
    // Somehow, res is now filled with like 
    // "Consider only the peaks of the array. Now, when we scan left/right until we hit another peak",
    // find the min item in both sides. 
    // Do above equation 
    F(i, 0, n) cout << res[i] << " "; cout << endl;

    seg::build(res);
}
 
int max_towers(int L, int R, int D) {
  auto [ret, indices] = seg::query(L, R+1, D);
  if(!ret == 0) return 1;
  auto [mn, mx] = indices;
  int sa = (spmin.query(L, mn) > arr[mn] - D);
  int sb = (spmin.query(mx+1, R+1) > arr[mx] - D);
  
  return max(0, ret - sa - sb) + 1;
}

컴파일 시 표준 에러 (stderr) 메시지

towers.cpp: In function 'void init(int, std::vector<int>)':
towers.cpp:8:20: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
    8 | #define F(i, l, r) for (ll i = ll(l); i < ll(r); ++i)
      |                    ^~~
towers.cpp:125:5: note: in expansion of macro 'F'
  125 |     F(i, 0, n) cout << H[i] << " "; cout << endl;
      |     ^
towers.cpp:125:37: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  125 |     F(i, 0, n) cout << H[i] << " "; cout << endl;
      |                                     ^~~~
towers.cpp:8:20: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
    8 | #define F(i, l, r) for (ll i = ll(l); i < ll(r); ++i)
      |                    ^~~
towers.cpp:137:5: note: in expansion of macro 'F'
  137 |     F(i, 0, n) cout << res[i] << " "; cout << endl;
      |     ^
towers.cpp:137:39: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  137 |     F(i, 0, n) cout << res[i] << " "; cout << endl;
      |                                       ^~~~

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