답안 #596498

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
596498	2022-07-14T19:23:21 Z	Deepesson	Peru (RMI20_peru)	C++17	컴파일 오류	0 ms	0 KB

peru

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")

#define MAX 2500005

int solve(int n, int k, int* v);

using ll = long long;

typedef std::pair<int,int> pii;

ll inf = 1LL<<60LL;
ll dp[MAX];

int N,K;
ll MOD = 1e9+7;

ll expo[MAX];
ll gera_hash(void){
    ll hash = 0;
    ll x = 1;
    for(int i=N-1;i!=-1;--i){
        hash = (hash + ((dp[i]%MOD)*x))%MOD;
        x = (x*23LL)%MOD;
    }
    return hash;
}

ll t[MAX*2];
ll d[MAX*2];
ll h = sizeof(ll) * 8 - __builtin_clz(MAX);

void update(int p, const ll value) {
  for (t[p += MAX] = value; p >>= 1; ) t[p] = std::min(t[p<<1], t[p<<1|1]);
}

void apply(int p, ll value) {
  t[p] = value+t[p];
  if (p < MAX) d[p] += value;
}

void push(int p) {
  for (int s = h; s > 0; --s) {
    int i = p >> s;
    if (d[i] != 0) {
      apply(i<<1, d[i]);
      apply(i<<1|1, d[i]);
      d[i] = 0;
    }
  }
}

void build(int p) {
  while (p > 1) p >>= 1, t[p] = std::min(t[p<<1], t[p<<1|1]) + d[p];
}

void inc(int l, int r, ll value) {
  l += MAX, r += MAX;
  ll l0 = l, r0 = r;
  for (; l < r; l >>= 1, r >>= 1) {
    if (l&1) apply(l++, value);
    if (r&1) apply(--r, value);
  }
  build(l0);
  build(r0 - 1);
}

ll query(int l, int r) {
  l += MAX, r += MAX;
  push(l);
  push(r - 1);
  ll res =  inf;
  for (; l < r; l >>= 1, r >>= 1) {
    if (l&1) res = std::min(res, t[l++]);
    if (r&1) res = std::min(t[--r], res);
  }
  return res;
}

pii vecstack[MAX];
int cur=0;
pii back(void){return vecstack[cur-1];}

int size(void){return cur;}

void push_back(auto x){vecstack[cur]=x;++cur;}

void pop_back(){--cur;}

int solve(int n, int k, int* array){
    N=n;
    K=k;
    expo[0]=1;
    for(auto&x:t)x=inf;
    for(auto&x:dp)x=inf;
    {
        ll max=0;
        for(int i=0;i!=K;++i){
            max=std::max(max,(ll)array[i]);
            dp[i]=max;
        }
    }


    for(int i=0;i!=std::min(N,1e6);++i){
        pii ent = {array[i],i};
        int last_r = i-1;
        const int barrier = i-K;
        while(size()&&last_r>=barrier&&back().first<=array[i]){
            auto ref = back();
            int dif = array[i]-ref.first;
            inc(ref.second,last_r,dif);
            last_r=ref.second-1;
            ent.second=ref.second;
            pop_back();
        }

        ent.second=std::max(ent.second,barrier);
        push_back(ent);
        ll ask = query(std::max(0,barrier),i+1);

        dp[i]=std::min(dp[i],ask);
        update(i,array[i]+dp[i]);
    }

    return gera_hash();
}

Compilation message

peru.cpp:4: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    4 | #pragma GCC optimization ("unroll-loops")
      | 
peru.cpp:88:16: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   88 | void push_back(auto x){vecstack[cur]=x;++cur;}
      |                ^~~~
peru.cpp: In function 'int solve(int, int, int*)':
peru.cpp:107:34: error: no matching function for call to 'min(int&, double)'
  107 |     for(int i=0;i!=std::min(N,1e6);++i){
      |                                  ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from peru.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:230:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)'
  230 |     min(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:230:5: note:   template argument deduction/substitution failed:
peru.cpp:107:34: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'double')
  107 |     for(int i=0;i!=std::min(N,1e6);++i){
      |                                  ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from peru.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:278:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)'
  278 |     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:278:5: note:   template argument deduction/substitution failed:
peru.cpp:107:34: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'double')
  107 |     for(int i=0;i!=std::min(N,1e6);++i){
      |                                  ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from peru.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3468:5: note: candidate: 'template<class _Tp> constexpr _Tp std::min(std::initializer_list<_Tp>)'
 3468 |     min(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3468:5: note:   template argument deduction/substitution failed:
peru.cpp:107:34: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
  107 |     for(int i=0;i!=std::min(N,1e6);++i){
      |                                  ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from peru.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3474:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::min(std::initializer_list<_Tp>, _Compare)'
 3474 |     min(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3474:5: note:   template argument deduction/substitution failed:
peru.cpp:107:34: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
  107 |     for(int i=0;i!=std::min(N,1e6);++i){
      |                                  ^