답안 #629575

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
629575 2022-08-14T16:16:08 Z somethingnew 송신탑 (IOI22_towers) C++17
컴파일 오류
0 ms 0 KB
#include "towers.h"

#include <cassert>
#include <cstdio>

#include <vector>
using namespace std;
vector<int> h;
struct segtree{
    int sz;
    vector<int> tree;
    void init(int n, vector<int> a) {
        sz = 1;
        while (sz < n)
            sz *= 2;
        tree.assign(sz * 2, 0);
        for (int i = 0; i < n; ++i) {
            tree[i + sz] = a[i];
        }
        for (int i = sz - 1; i > 0; --i) {
            tree[i] = tree[i * 2] + tree[i * 2 + 1];
        }
    }
    int get(int l, int r) {
        int res = 0;
        while (l <= r) {
            if (l & 1) {
                res += tree[l];
                l++;
            }
            if ((r & 1) == 0) {
                res += tree[r];
                r--;
            }
            l /= 2;r /= 2;
        }
        return res;
    }
};
segtree sg;

void init(int n, vector<int> hh) {
    h = hh;
    vector<int> bebra(n);
    for (int i = 1; i + 1 < n; ++i) {
        if (hh[i-1] > hh[i] and hh[i] < hh[i + 1])
            bebra[i] = 1;
    }
    sg.init(n, bebra);
}
int max_towers(int L, int R, int D) {
    if (D == 1) {
        int val = sg.get(L + 1, R - 1);
        if (L + 1 <= R and h[L] < h[L + 1])
            val++;
        if (L + 1 <= R and h[R-1] > h[R])
            val++;
        return max(val, 1);
    }
    vector<int> dp(h.size(), 1);
    int res = 0;
    for (int i = L; i < R; ++i) {
        int mx = h[i];
        res = max(res, dp[i]);
        for (int j = i + 1; j <= R; ++j) {
            mx = max(mx, h[j]);
            if (mx - D >= max(h[i], h[j]) and h[j - 1] > h[j] and (j == R or h[j + 1] > h[j])) {
                dp[j] = max(dp[j], dp[i] + 1);
            }
        }
    }
    res = max(res, dp[R]);
    return res;
}

int main() {
  int N, Q;
  assert(2 == scanf("%d %d", &N, &Q));
  std::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;
}

Compilation message

/usr/bin/ld: /tmp/ccvsh300.o: in function `main':
stub.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccGkx1V1.o:towers.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status