제출 #1056660

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1056660		epicci23	송신탑 (IOI22_towers)	C++17	14 / 100	4054 ms	3024 KiB

towers

#include "bits/stdc++.h"
#include "towers.h"
//#define int long long
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
using namespace std;

vector<int> xd;
vector<int> bak;
vector<array<int,2>> v;
void init(int n, vector<int> ar) {
  if(n<=2) return;
  vector<array<int,2>> v2;
  bak=ar;
  if(ar[0]>ar[1]) v2.push_back({ar[0],0});
  else {xd.push_back(0);v2.push_back({ar[0],1});}
  for(int i=1;i<n-1;i++){
  	if(ar[i]>ar[i-1] && ar[i]>ar[i+1]) v2.push_back({ar[i],0});
  	else if(ar[i]<ar[i-1] && ar[i]<ar[i+1]) {xd.push_back(i);v2.push_back({ar[i],1});}
  }
  if(ar[n-1]<ar[n-2]) {xd.push_back(n-1);v2.push_back({ar[n-1],1});}
  else v2.push_back({ar[n-1],0});
}

int max_towers(int l, int r, int d){
  if(d==1){
  if(r-l<=1) return 1;
  int it=upper_bound(all(xd),r-1)-xd.begin();
  int it2=lower_bound(all(xd),l+1)-xd.begin();
  int cur=it-it2;
  if(bak[l]<bak[l+1]) cur++;
  if(bak[r]<bak[r-1]) cur++;
  return max(1,cur);
  }
  if(bak[l]>bak[l+1]) v.push_back({bak[l],0});
  else v.push_back({bak[l],1});
  for(int i=l+1;i<r-1;i++){
  	if(bak[i]>bak[i-1] && bak[i]>bak[i+1]) v.push_back({bak[i],0});
  	else if(bak[i]<bak[i-1] && bak[i]<bak[i+1]) v.push_back({bak[i],1});
  }
  if(bak[r]<bak[r-1]) v.push_back({bak[r],1});
  else v.push_back({bak[r],0});

  int dp[sz(v)+5];
  int maxi=1;
  for(int i=0;i<sz(v);i++){
  	dp[i]=1;
  	int lol=0;
    for(int j=i-1;j>=0;j--){
      if(v[j][1]==0) lol=max(lol,v[j][0]);
      else if(lol>v[j][0]) dp[i]=max(dp[i],dp[j]+1);
    }
    maxi=max(maxi,dp[i]);
  }
  return maxi;
}

/*void _(){
  int n,q;cin >> n >> q;
  int ar[n+5];
  for(int i=1;i<=n;i++) cin >> ar[i];
  
  if(n<=2) return;

  vector<array<int,2>> v;
  vector<int> xd;
  if(ar[1]>ar[2]) v.push_back({ar[1],0});
  else {xd.push_back(1);v.push_back({ar[1],1});}
  for(int i=2;i<n;i++){
  	if(ar[i]>ar[i-1] && ar[i]>ar[i+1]) v.push_back({ar[i],0});
  	else if(ar[i]<ar[i-1] && ar[i]<ar[i+1]) {xd.push_back(i);v.push_back({ar[i],1});}
  }
  if(ar[n]<ar[n-1]) {xd.push_back(n);v.push_back({ar[n],1});}
  else v.push_back({ar[n],0});


  while(q--){
  	int l,r,d;
  	cin >> l >> r >> d;
  	int it=upper_bound(all(xd),r)-xd.begin();
  	int it2=lower_bound(all(xd),l)-xd.begin();
  	cout << it-it2 << '\n'; 
  }
}

int32_t main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tc=1;//cin >> tc;
  while(tc--) _();
  return 0;
}*/

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