답안 #1035576

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1035576	2024-07-26T12:05:15 Z	aymanrs	송신탑 (IOI22_towers)	C++17	0 / 100	4000 ms	21848 KB

towers

#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> pr, h;
const int K = 17;
vector<pair<int, int>> sp[K];
vector<int> spm[K];
inline int msb(int x){
    return 31-__builtin_clz(x);
}
int que(int l, int r){
  int d = msb(r-l+1);
  return max(sp[d][l], sp[d][r-(1<<d)+1]).second;
}
int qum(int l, int r){
  int d = msb(r-l+1);
  return min(spm[d][l], spm[d][r-(1<<d)+1]);
}
bool sub1 = true;
int th;
void init(int N, std::vector<int> H) {
  h = H;
  pr.resize(N);
  pr[0]=0;
  auto mx = max_element(h.begin(), h.end());
  if(is_sorted(h.begin(), mx) && is_sorted(mx, h.end(), greater<int>())) {
    sub1=true;
    th = mx-h.begin();
  }
  else sub1=false;
  for(int i = 0;i < K;i++) {
    sp[i].resize(N);
    spm[i].resize(N);
  }
  for(int i = 0;i < N;i++){
    sp[0][i] = {H[i], i};spm[0][i]=H[i];
  }
  for(int k = 1;k < K;k++){
    for(int i = 0;i+(1<<k)<=N;i++){
      sp[k][i] = max(sp[k-1][i], sp[k-1][i+(1<<k-1)]);
      spm[k][i] = min(spm[k-1][i], spm[k-1][i+(1<<k-1)]);
    }
  }
  for(int i = 1;i < N-1;i++){
    pr[i]=pr[i-1];
    if(H[i] < H[i-1] && H[i] < H[i+1]) pr[i]++;
  }
}
int de;
int ans(int l, int r, int atm){
  if(l==r){
    if(h[l]<=atm) return 1;
    return 0;
  }
  int m = que(l, r);
  if(l==m) return ans(l+1, r, atm);
  if(m==r) return ans(l, r-1, atm);
  return max(ans(l, m-1, h[m]-de)+ans(m+1, r, h[m]-de), (qum(l,r) <= atm ? 1 : 0));
}
int max_towers(int L, int R, int D) {
  if(sub1){
    if(L>th || R < th) return 1;
    return max(1, int(lower_bound(h.begin()+L, h.begin()+th+1, h[th]-D+1)-h.begin()-L+ h.begin()+R+1-lower_bound(h.begin()+th, h.begin()+R+1, h[th]-D, greater<int>())));
  }
  de = D;
  if(L+1>=R) return 1;
  if(D==1) return pr[R-1]-pr[L]+(h[L] < h[L+1])+(h[R]<h[R-1]);
  return ans(L, R, INT_MAX);
}

Compilation message

towers.cpp: In function 'void init(int, std::vector<int>)':
towers.cpp:40:49: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   40 |       sp[k][i] = max(sp[k-1][i], sp[k-1][i+(1<<k-1)]);
      |                                                ~^~
towers.cpp:41:52: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   41 |       spm[k][i] = min(spm[k-1][i], spm[k-1][i+(1<<k-1)]);
      |                                                   ~^~

Subtask #1
0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	288 ms	13144 KB	2nd lines differ - on the 1st token, expected: '1', found: '5353'
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	1 ms	856 KB	Output is correct
3	Correct	1 ms	632 KB	Output is correct
4	Correct	1 ms	856 KB	Output is correct
5	Correct	1 ms	856 KB	Output is correct
6	Correct	1 ms	856 KB	Output is correct
7	Correct	1 ms	856 KB	Output is correct
8	Correct	1 ms	856 KB	Output is correct
9	Correct	1 ms	856 KB	Output is correct
10	Correct	1 ms	596 KB	Output is correct
11	Correct	1 ms	856 KB	Output is correct
12	Correct	0 ms	344 KB	Output is correct
13	Correct	1 ms	856 KB	Output is correct
14	Correct	1 ms	856 KB	Output is correct
15	Correct	1 ms	856 KB	Output is correct
16	Correct	1 ms	856 KB	Output is correct
17	Correct	1 ms	856 KB	Output is correct
18	Correct	1 ms	856 KB	Output is correct
19	Correct	1 ms	856 KB	Output is correct
20	Correct	1 ms	852 KB	Output is correct
21	Correct	1 ms	856 KB	Output is correct
22	Correct	1 ms	1112 KB	Output is correct
23	Incorrect	1 ms	856 KB	1st lines differ - on the 1st token, expected: '1', found: '1999'
24	Halted	0 ms	0 KB	-

Subtask #3
0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	1 ms	856 KB	Output is correct
3	Correct	1 ms	632 KB	Output is correct
4	Correct	1 ms	856 KB	Output is correct
5	Correct	1 ms	856 KB	Output is correct
6	Correct	1 ms	856 KB	Output is correct
7	Correct	1 ms	856 KB	Output is correct
8	Correct	1 ms	856 KB	Output is correct
9	Correct	1 ms	856 KB	Output is correct
10	Correct	1 ms	596 KB	Output is correct
11	Correct	1 ms	856 KB	Output is correct
12	Correct	0 ms	344 KB	Output is correct
13	Correct	1 ms	856 KB	Output is correct
14	Correct	1 ms	856 KB	Output is correct
15	Correct	1 ms	856 KB	Output is correct
16	Correct	1 ms	856 KB	Output is correct
17	Correct	1 ms	856 KB	Output is correct
18	Correct	1 ms	856 KB	Output is correct
19	Correct	1 ms	856 KB	Output is correct
20	Correct	1 ms	852 KB	Output is correct
21	Correct	1 ms	856 KB	Output is correct
22	Correct	1 ms	1112 KB	Output is correct
23	Incorrect	1 ms	856 KB	1st lines differ - on the 1st token, expected: '1', found: '1999'
24	Halted	0 ms	0 KB	-

Subtask #4
0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	494 ms	21592 KB	Output is correct
2	Correct	696 ms	21848 KB	Output is correct
3	Correct	633 ms	21848 KB	Output is correct
4	Correct	675 ms	21848 KB	Output is correct
5	Correct	700 ms	21840 KB	Output is correct
6	Correct	603 ms	21848 KB	Output is correct
7	Correct	561 ms	21848 KB	Output is correct
8	Incorrect	577 ms	21848 KB	76943rd lines differ - on the 1st token, expected: '1', found: '19721'
9	Halted	0 ms	0 KB	-

Subtask #5
0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	4051 ms	5464 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #6
0 / 19.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	1 ms	856 KB	Output is correct
3	Correct	1 ms	632 KB	Output is correct
4	Correct	1 ms	856 KB	Output is correct
5	Correct	1 ms	856 KB	Output is correct
6	Correct	1 ms	856 KB	Output is correct
7	Correct	1 ms	856 KB	Output is correct
8	Correct	1 ms	856 KB	Output is correct
9	Correct	1 ms	856 KB	Output is correct
10	Correct	1 ms	596 KB	Output is correct
11	Correct	1 ms	856 KB	Output is correct
12	Correct	0 ms	344 KB	Output is correct
13	Correct	1 ms	856 KB	Output is correct
14	Correct	1 ms	856 KB	Output is correct
15	Correct	1 ms	856 KB	Output is correct
16	Correct	1 ms	856 KB	Output is correct
17	Correct	1 ms	856 KB	Output is correct
18	Correct	1 ms	856 KB	Output is correct
19	Correct	1 ms	856 KB	Output is correct
20	Correct	1 ms	852 KB	Output is correct
21	Correct	1 ms	856 KB	Output is correct
22	Correct	1 ms	1112 KB	Output is correct
23	Incorrect	1 ms	856 KB	1st lines differ - on the 1st token, expected: '1', found: '1999'
24	Halted	0 ms	0 KB	-

Subtask #7
0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	288 ms	13144 KB	2nd lines differ - on the 1st token, expected: '1', found: '5353'
2	Halted	0 ms	0 KB	-

답안 #1035576

Compilation message

Subtask #1 0 / 4.0

Subtask #2 0 / 11.0

Subtask #3 0 / 12.0

Subtask #4 0 / 14.0

Subtask #5 0 / 17.0

Subtask #6 0 / 19.0

Subtask #7 0 / 23.0

Subtask #1
0 / 4.0

Subtask #2
0 / 11.0

Subtask #3
0 / 12.0

Subtask #4
0 / 14.0

Subtask #5
0 / 17.0

Subtask #6
0 / 19.0

Subtask #7
0 / 23.0