Submission #538255

#	Time	Username	Problem	Language	Result	Execution time	Memory
538255		AdamGS	Peru (RMI20_peru)	C++17	0 / 100	1 ms	340 KiB

peru

#include "peru.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const ll MOD=1e9+7, LIM=25e5+7, INF=1e18+7;
ll dp[LIM], odw[LIM], tr[4*LIM], trm[4*LIM], N=1, li, li2;
vector<pair<ll,int>>V;
vector<pair<ll,pair<int,int>>>P;
ll cnt(int l, int r) {
  l+=N; r+=N;
  ll ans=max(tr[l], tr[r]);
  while(l/2!=r/2) {
    if(l%2==0) ans=max(ans, tr[l+1]);
    if(r%2==1) ans=max(ans, tr[r-1]);
    l/=2; r/=2;
  }
  return ans;
}
void dodaj(ll x, int i) {
  while(V.size() && x>=V.back().st) {
    odw[V.back().nd]=1;
    V.pop_back();
    li=min(li, (long long)V.size());
  }
  if(V.size()) {
    while(P.size() && x+dp[V.back().nd]<=P.back().st) {
      P.pop_back();
      li2=min(li2, (long long)P.size());
    }
    P.pb({x+dp[V.back().nd], {V.back().nd+1, i}});
  }
  V.pb({x, i});
}
int solve(int n, int k, int* v){
  while(N<n) N*=2;
  rep(i, n) tr[N+i]=v[i];
  for(int i=N-1; i>=0; --i) tr[i]=max(tr[2*i], tr[2*i+1]);
  rep(i, k) {
    dp[i]=cnt(0, i);
    dodaj(v[i], i);
  }
  for(int i=k; i<n; ++i) {
    dodaj(v[i], i);
    dp[i]=dp[i-k]+cnt(i-k+1, i);
    while(li<V.size() && V[li].nd<=i-k) ++li;
    if(li==V.size()) li2=P.size();
    while(li2<P.size() && (P[li2].nd.st<=i-k || odw[P[li2].nd.nd])) ++li2;
    if(li2<P.size()) dp[i]=min(dp[i], P[li2].st);
  }
  ll ans=0;
  rep(i, n) ans=(ans*23+dp[i])%MOD;
  return ans;
}

Compilation message (stderr)

peru.cpp: In function 'int solve(int, int, int*)':
peru.cpp:50:13: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |     while(li<V.size() && V[li].nd<=i-k) ++li;
      |           ~~^~~~~~~~~
peru.cpp:51:10: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |     if(li==V.size()) li2=P.size();
      |        ~~^~~~~~~~~~
peru.cpp:52:14: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |     while(li2<P.size() && (P[li2].nd.st<=i-k || odw[P[li2].nd.nd])) ++li2;
      |           ~~~^~~~~~~~~
peru.cpp:53:11: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |     if(li2<P.size()) dp[i]=min(dp[i], P[li2].st);
      |        ~~~^~~~~~~~~

• Subtask 1: 0 / 18
• Subtask 2: 0 / 31
• Subtask 3: 0 / 51