제출 #1169295

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1169295		sasde	Valley (BOI19_valley)	C++20	0 / 100	23 ms	3264 KiB

valley

#include<bits/stdc++.h>
#define int long long
#define str string
#define task "attack"
#define ii pair<int,int>
#define iii pair<int,ii>
#define iv pair<ii,ii>
#define se second
#define fi first
#define ffi fi.fi
#define sfi se.fi
#define sse se.se
#define fse fi.se
#define lt(i, c, d) for(int i = c; i <= d; ++i)
#define fl(i, c, d) for(int i = d; i >= c; --i)
#define pb push_back
#define emb emplace_back
#define emf emplace_front
#define em emplace
using namespace std;
const int N=5e4+5,lg=20,mod=1e9+7;
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
int Rand(int u,int v){
 return u+rd()%(v-u+1);
}
int ans=0,A[N],W[N],D[N],n;
struct pt
{
  int hp,en,atk,def,e,i;
  friend bool operator<(pt x,pt y){
    if(x.hp!=y.hp)return x.hp<y.hp;
    if(x.en!=y.en)return x.en<y.en;
    if(x.atk!=y.atk)return x.atk<y.atk;
    if(x.def!=y.def)return x.def<y.def;
    return x.e<y.e;
  }
  friend bool operator!=(pt x,pt y){
    return  (x.hp!=y.hp||x.en!=y.en||x.atk!=y.atk||x.def!=y.def);
  }
}b[N],a[N],c[N];

int bit[N*2],vv=1e5+1,timer,tt[N];
void check(int idx){
  if(tt[idx]!=timer){
    tt[idx]=timer;
    bit[idx]=0;
  }
}
void update(int idx,int val){
  while(idx<=n){
    check(idx);
    bit[idx]=max(bit[idx],val);
    idx+=idx&(-idx);
  }
}
int get(int idx){
  int res=0;
  while(idx){
    check(idx);
    res=max(res,bit[idx]);
    idx-=idx&(-idx);
  }
  return res;
}
int dp[N];
ii e[N],f[N];
void dnc1(int r,int l){
 if(r>=l){  return;
 }
 int mid=(r+l)>>1;
 dnc1(r,mid);
 int q=0,w=0;
 for(int i=r;i<=mid;++i){
  if(c[i].e==0){
    ++q;
    e[q]={a[c[i].i].atk,c[i].i};
  }
 }
 for(int i=mid+1;i<=l;++i){
 // cout <<c[i].hp<<" "<<c[i].en<<" "<<c[i].atk<<" "<< c[i].def<<'\n';

  if(c[i].e==1){
    ++w;
    f[w]={a[c[i].i].atk,c[i].i};
  }
}
 int j=1;
 sort(f+1,f+1+w);
 sort(e+1,e+1+q);
 for(int i=1;i<=w;++i){
  while(e[j].fi<=f[i].fi&&j<=q){
    update(a[e[j].se].def,dp[e[j].se]);
    ++j;
  }
  int pos=f[i].se;
  // cout <<f[i].fi<<" "<<pos<<" "<<a[pos].def<<'\n';
  dp[pos]=max(dp[pos],get(a[pos].def)+a[pos].e);
  // cout <<dp[pos]<<
 }
 timer++;
 dnc1(mid+1,l);
}
bool cmp1(pt x,pt y){
   if(x.en!=y.en)return x.en<y.en;
    if(x.atk!=y.atk)return x.atk<y.atk;
    if(x.def!=y.def)return x.def<y.def;
    return x.e<y.e;
}
void dnc(int r,int l){
 if(r>=l){
  return;
 }
 int mid=(r+l)>>1;
 dnc(r,mid);
 for(int i=r;i<=l;++i){
  c[i].i=a[i].i;
  c[i].e=(i>mid);
  c[i].en=a[i].en;
  // cout <<a[i].en<<" "<<a[i].e<<" "<<a[i].i<<'\n';
  // a[i].
 }
 sort(c+r,c+1+l);
 dnc1(r,l);
 dnc(mid+1,l);
}
vector<int>nenn;
int ne(int u){
  return lower_bound(nenn.begin(),nenn.end(),u)-nenn.begin()+1;
}
void solve(){
  cin >> n;
  ans=-1e18;
  int k=0;
 for(int i=1;i<=n;++i){
      ++k;
    cin >> b[k].hp >> b[k].en >> b[k].atk >> b[k].def >> b[k].e;
    ans=max(ans,b[k].e);
   if(b[k].e<=0){--k;continue;}
    nenn.emb(b[k].def);
  }
  n=k;

  sort(nenn.begin(),nenn.end());
  nenn.erase(unique(nenn.begin(),nenn.end()),nenn.end());
  for(int i=1;i<=n;++i)b[i].def=ne(b[i].def);
  // for(int i=1;i<=n;++i)cout <<a[i].hp<<" "<<a[i].en<<" "<<a[i].atk<<" "<< a[i].def<<'\n';
  
  sort(b+1,b+1+n);
  k=0;
  b[n+1].hp=-1e9;
  int val=0;
  for(int i=1;i<=n;++i){
    val+=b[i].e;
    if(b[i]!=b[i+1]){
      ++k;
      a[k]=b[i];
      a[k].e=val;
      val=0;
    }
  }
  n=k;
  // cout <<n;
  for(int i=1;i<=n;++i){    dp[i]=a[i].e;
     a[i].i=i;}
  dnc(1,n);
for(int i=1;i<=n;++i){
  // cout <<D[i]<<" ";
// cout <<a[i].hp<<" "<<a[i].en<<" "<<a[i].atk<<" "<<a[i].def<<" "<<a[i].e<<'\n';

  ans=max(ans,dp[i]);
}
  cout << ans;
}
main()
{
  srand(time(0));
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    if(fopen(task".inp","r")){
      freopen(task".inp","r",stdin);
      freopen(task".out","w",stdout);
    }
    int t=1;
 //   cin >> t;
while(t--){
    solve();
    cout<<'\n'; 
}

}

컴파일 시 표준 에러 (stderr) 메시지

valley.cpp:174:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  174 | main()
      | ^~~~
valley.cpp: In function 'int main()':
valley.cpp:181:14: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  181 |       freopen(task".inp","r",stdin);
      |       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
valley.cpp:182:14: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  182 |       freopen(task".out","w",stdout);
      |       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 9
• Subtask 2: 0 / 27
• Subtask 3: 0 / 23
• Subtask 4: 0 / 41