Submission #910153

#	Time	Username	Problem	Language	Result	Execution time	Memory
910153		bobbilyking	송신탑 (IOI22_towers)	C++17	37 / 100	4089 ms	7504 KiB

towers

#include "towers.h"
#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")

#include<bits/stdc++.h>
#include<math.h>
using namespace std;

typedef long long int ll;
typedef long double ld;
typedef pair<ll, ll> pl;
typedef vector<ll> vl;
#define FD(i, r, l) for(ll i = r; i > (l); --i)

#define K first
#define V second
#define G(x) ll x; cin >> x;
#define GD(x) ld x; cin >> x;
#define GS(s) string s; cin >> s;
#define EX(x) { cout << x << '\n'; exit(0); }
#define A(a) (a).begin(), (a).end()
#define F(i, l, r) for (ll i = l; i < (r); ++i)

#define NN 100010
#define M 1000000007 // 998244353

ll h[NN];
ll n;

namespace seg {
    typedef pl T;
    T id={-1, -1};
    T f(T a, T b) {return pair(max(a.K, b.K), max(a.V, b.V)) ;}

    T t[2 * NN];
    ll n=NN;  // array size

    void init(ll p, ll value) {  // set value at position p
      for (p+=n, t[p].K = value; p /= 2;) t[p] = f(t[2*p], t[2*p+1]);
    }

    void modify(ll p, ll value) {  // set value at position p
      for (p+=n, t[p].V = max(t[p].V, value); p /= 2;) t[p] = f(t[2*p], t[2*p+1]);
    }

    T query(ll l, ll r) { // fold f on interval [l, r)
      T resl=id, resr=id;
      for (l += n, r += n; l < r; l /= 2, r /= 2) {
        if (l&1) resl = f(resl, t[l++]);
        if (r&1) resr = f(t[--r], resr);
      }
      return f(resl, resr);
    }
}

int brute_force(int L, int R, int D) {
        // vl dp(n+1, -1);/
    F(i, 0, 2*NN) seg::t[i].V = -1;


    ll res = 0;
    // ll res2 = 0;
    F(i, L, R+1) {
        ll ans = 1;
        // ll ans2 = 1;
        {
            // for (ll cur = i-1; cur >= L; cur--) if (h[cur] >= D + h[i]) ans2 = max(ans2, dp[cur] + 1);

            ll l = L - 1, r = i + 1;
            while (l+1<r) {
                ll m = (l+r)/2;
                if (seg::query(m, i).K >= D + h[i]) l = m;
                else r = m;
            }

            // if (i == 5) {
            //     cout << L << " " << l+1 << " " << seg::query(L, l+1).V << " " << endl;
            //     cout << seg::query(l, l+1).V << endl;
            // }
            ans = max(ans, seg::query(L, l+1).V + 1);
        }
        {
            // for (ll cur = i+1; cur <= R; cur++) if (h[cur] >= D + h[i]) dp[cur] = max(dp[cur], ans2);

            ll l = i, r = R+1;
            while (l+1<r) {
                ll m = (l+r)/2;
                if (seg::query(i, m+1).K >= D + h[i]) r = m;
                else l = m;
            }
            seg::modify(r, ans); 

            // if (ans2 == 3) cout << "TURNEd 3 AT " << i << endl;
        }
        res = max(res, ans);
        // res2 = max(ans, ans2);
        // cout << "ARRAYS FOR  " << i << endl;
        // F(i, L, R+1) cout << dp[i] << " "; cout << endl;

        // F(i, L, R+1) cout << seg::query(i, i+1).V << " "; cout << endl;
        
    }
    // assert(res == res2);
    return res;
}

namespace segval {
    typedef ll T;
    T id=0;
    T f(T a, T b) {return a+b;}

    T t[2 * NN];
    ll n=NN;  // array size

    void modify(ll p, T value) {  // set value at position p
      for (p+=n, t[p] = value; p /= 2;) t[p] = f(t[2*p], t[2*p+1]);
    }

    T query(ll l, ll r) { // fold f on interval [l, r)
      T resl=id, resr=id;
      for (l += n, r += n; l < r; l /= 2, r /= 2) {
        if (l&1) resl = f(resl, t[l++]);
        if (r&1) resr = f(t[--r], resr);
      }
      return f(resl, resr);
    }
}
vl valleys;
void init(int N, std::vector<int> H) {
    n = N;
    F(i, 0, n) h[i] = H[i];

    F(i, 0, n) seg::init(i, H[i]);

    valleys.resize(n);
    F(i, 0, n) {
        valleys[i] = 1;
        if (i + 1 < n) valleys[i] &= h[i] < h[i+1];
        if (i > 0) valleys[i] &= h[i-1] > h[i];
        segval::modify(i, valleys[i]);
    }
}


void gen_graph(int L, int R, int D) {
    cout << "Query: " << L << " " << R << " " << D << endl;
    F(i, L, R+1) cout << h[i] << " "; cout << endl;

    vector<ll> peak(n), valley(n);
    F(i, L, R+1) {
        peak[i] = 1, valley[i] = 1;
        if (i > 0) {
            peak[i] &= h[i-1] < h[i];
            valley[i] &= h[i-1] > h[i];
        }
        if (i + 1 < n) {
            peak[i] &= h[i+1] < h[i];
            valley[i] &= h[i+1] > h[i];
        }

        // cout << h[i] << ": " << peak[i] << " " << valley[i] << endl;
    } 
    

    F(i, L, R+1) {
        if (valley[i]) {
            for (ll j = i + 1; j <= R; ++j) if (peak[j] and h[j] - h[i] >= D) {
                cout << "V" << i << " P" << j << endl; break;
            }
        } else if (peak[i]) {
            for (ll j = i + 1; j <= R; ++j) if (valley[j] and h[i] - h[j] >= D) {
                cout << "P" << i << " V" << j << endl; break;
            }
        }
    }
}

// if (valley[i]) {
//             for (ll l = i-1; l >= L; --l) if (peak[l] and h[l] - h[i] >= D) {
//                 cout << l << " " << i << endl; break;
//             }
//         }
//         for (ll r = i+1; r <= R; ++r) if (valley[r] and h[r] - h[i] >= D) {
//             cout << i << " " << r << endl; break;
//         }


int max_towers(int L, int R, int D) {
    if (L == R) return 1;
    if (D == 1) {
        if (!valleys[L] and h[L] < h[L+1]) segval::modify(L, 1);

        if (!valleys[R] and h[R] < h[R-1]) segval::modify(R, 1);

        int ans = segval::query(L, R+1);

        if (!valleys[R] and h[R] < h[R-1]) segval::modify(R, 0);

        if (!valleys[L] and h[L] < h[L+1]) segval::modify(L, 0);

        // ll temp = brute_force(L, R, D);
        // if (temp != ans) cout << L << " " << R << " " << D << ", " << temp << " " << ans << endl;
        // assert(temp == ans);
        return ans;
    }   
    // gen_graph(L, R, D);

    // cout << "Actual: " << brute_force(L, R, D) << endl;

    return brute_force(L, R, D);
}

Compilation message (stderr)

towers.cpp: In function 'void gen_graph(int, int, int)':
towers.cpp:23:20: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   23 | #define F(i, l, r) for (ll i = l; i < (r); ++i)
      |                    ^~~
towers.cpp:148:5: note: in expansion of macro 'F'
  148 |     F(i, L, R+1) cout << h[i] << " "; cout << endl;
      |     ^
towers.cpp:148:39: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  148 |     F(i, L, R+1) cout << h[i] << " "; cout << endl;
      |                                       ^~~~

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