제출 #716252

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
716252		ktkerem	Money (IZhO17_money)	C++17	100 / 100	173 ms	22764 KiB

money

/*#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")/**/
#include<bits/stdc++.h>
typedef long long ll;
typedef long double ld;
typedef __int128 vll;
typedef long long ftyp;
typedef std::complex<ftyp> vec;
#define llll std::pair<ll , ll>
#define pb push_back
#define fi first
#define sec second
#define cx real
#define cy imag
#define all(a) a.begin() , a.end()
#define debug std::cout << "!!ALERT ALERT!!" << std::endl;
const ll limit = 1e15+7;
const ll sus = 1e6+5;
std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
ll n;std::vector<ll> ar;
ll ftw[sus];
void upd(ll k , ll upd){
  for(;sus > k;k = (k | (k+1))){
    ftw[k] += upd;
  }
}
ll que(ll x){
  ll g = 0;
  for(;x>=0;x = (x & (x+1))-1){
    g+=ftw[x];
  }
  return g;
}
void solve(){
  std::cin >> n;
  ar.resize(n);
  for(ll i = 0 ; n>i;i++){
    std::cin >> ar[i];
  }
  ll ans = 0;
  ll lst = 0;
  for(ll i = 0;n>i;i++){
    if(i == n-1 || ar[i] > ar[i+1] || (ar[i] < ar[i+1] && (que(ar[i+1]-1) - que(ar[lst])))){
      for(ll j = lst;i>=j;j++){
        upd(ar[j] , 1);
      }
      lst = i + 1;
      ans++;
    }
  }
  std::cout << ans << "\n";
  return;/**/
}
int main(){
  std::ios_base::sync_with_stdio(false);std::cin.tie(NULL);
  ll t = 1;
  //std::cin >> t;
  while(t--){
    solve();
  }
}

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

money.cpp:5:78: warning: "/*" within comment [-Wcomment]
    5 | #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")/**/
      |

• Subtask 1: 9 / 9
• Subtask 2: 16 / 16
• Subtask 3: 20 / 20
• Subtask 4: 55 / 55