Submission #825088

#	Time	Username	Problem	Language	Result	Execution time	Memory
825088		becaido	Radio Towers (IOI22_towers)	C++17	23 / 100	4085 ms	2836 KiB

towers

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
using namespace std;

#ifndef WAIMAI
#include "towers.h"
#endif

#ifdef WAIMAI
#define debug(HEHE...) cout << "[" << #HEHE << "] : ", dout(HEHE)
void dout() {cout << '\n';}
template<typename T, typename...U>
void dout(T t, U...u) {cout << t << (sizeof...(u) ? ", " : ""), dout(u...);}
#else
#define debug(...) 7122
#endif

#define ll long long
#define Waimai ios::sync_with_stdio(false), cin.tie(0)
#define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
#define pb emplace_back
#define F first
#define S second

const int SIZE = 1e5 + 5;

int n, m;
int a[SIZE];
vector<int> lis;

void init(int N, vector<int> H) {
    n = N;
    FOR (i, 0, n - 1) a[i] = H[i], lis.pb(a[i]);
    sort(lis.begin(), lis.end());
    lis.erase(unique(lis.begin(), lis.end()), lis.end());
    m = lis.size();
}

int bit[SIZE];
void upd(int pos, int x) {
    for (; pos <= m; pos += pos & -pos) bit[pos] = max(bit[pos], x);
}
int que(int pos) {
    int re = 0;
    for (; pos; pos -= pos & -pos) re = max(re, bit[pos]);
    return re;
}

int bit2[SIZE];
void upd2(int pos, int x) {
    for (; pos; pos -= pos & -pos) bit2[pos] = max(bit2[pos], x);
}
int que2(int pos) {
    int re = 0;
    for (; pos <= m; pos += pos & -pos) re = max(re, bit2[pos]);
    return re;
}

int dp[SIZE];
int max_towers(int L, int R, int D) {
    fill(bit + 1, bit + n + 1, 0);
    fill(bit2 + 1, bit2 + n + 1, 0);
    FOR (i, L, R) {
        int pos = lower_bound(lis.begin(), lis.end(), a[i]) - lis.begin() + 1;
        dp[i] = que2(pos) + 1;
        upd(pos, dp[i]);
        pos = upper_bound(lis.begin(), lis.end(), a[i] - D) - lis.begin();
        upd2(pos, que(pos));
        debug(i, dp[i]);
    }
    return *max_element(dp + L, dp + R + 1);
}

/*
in1
7 3
10 20 60 40 50 30 70
1 5 10
2 2 100
0 6 17
out1
3
1
2
*/

#ifdef WAIMAI
int main() {
  int N, Q;
  assert(2 == scanf("%d %d", &N, &Q));
  vector<int> H(N);
  for (int i = 0; i < N; ++i) {
    assert(1 == scanf("%d", &H[i]));
  }
  init(N, H);

  for (int i = 0; i < Q; ++i) {
    int L, R, D;
    assert(3 == scanf("%d %d %d", &L, &R, &D));
    printf("%d\n", max_towers(L, R, D));
  }
  return 0;
}
#endif

Compilation message (stderr)

towers.cpp: In function 'int max_towers(int, int, int)':
towers.cpp:16:20: warning: statement has no effect [-Wunused-value]
   16 | #define debug(...) 7122
      |                    ^~~~
towers.cpp:70:9: note: in expansion of macro 'debug'
   70 |         debug(i, dp[i]);
      |         ^~~~~

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