Submission #494539

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
494539	2021-12-15T17:14:59 Z	leaked	Peru (RMI20_peru)	C++14	Compilation error	0 ms	0 KB

peru

#include <bits/stdc++.h>
#define f first
#define s second
#define m_p make_pair
#define pb push_back
#define vec vector
#define sz(x) (int)(x).size()
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define fast_rmi ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,int> pli;
const int N=25e6+1;
const int M=1e9+7;
ll dp[N];
ll pw[N];
int up[N][21];
int lvl[N];
int get(int l,int r){
    int x=lvl[r-l+1];
//    cout<<"A "<<l<<' '<<r<<' '<<max(up[l][x],up[r-(1<<x)+1][x])<<endl;
    return max(up[l][x],up[r-(1<<(x))+1][x]);
}
/// dp[i]+a[i]
int solve(int n,int k,int *a){
    for(int i=2;i<N;i++)
        lvl[i]=lvl[i/2]+1;
    for(int i=0;i<n;i++)
        up[i][0]=a[i];
    for(int j=1;j<21;j++){
        for(int i=0;i+(1<<(j-1))<n;i++){
            up[i][j]=max(up[i][j-1],up[i+(1<<(j-1))][j-1]);
        }
    }
    int ans=0;
    pw[0]=1;
    for(int i=1;i<n;i++)
        pw[i]=1ll*pw[i-1]*23%M;
    deque<pli>dq;
    vec<int> lft(n,0);
    dq.pb({0,0});
    for(int i=1;i<=n;i++){
        if(sz(dq) && dq.front().s<i-k)
            dq.pop_front();
//        for(auto &z : dq)
//            cout<<z.f+get(z.s,i-1)<<' ';
//        cout<<endl;
        dp[i]=dq.front().f+get(dq.front().s,i-1);
        while(sz(dq)!=1 && dq.back().f+get(dq.back().s,i-1)>dp[i]+a[i])
            dq.pop_back();
        dq.pb({dp[i],i});
        ans+=1ll*(dp[i]%M)*pw[n-i]%M;
        ans%=M;
//        cout<<"DP "<<dp[i]<<endl;
    }
    return ans;
}
//int a[100];
//signed main(){
//    int n,k;
//    cin>>n>>k;
//    for(int i=0;i<n;i++)
//        cin>>a[i];
//    cout<<solve(n,k,a);
//}

Compilation message

/tmp/ccfdNwEM.o: in function `solve(int, int, int*)':
peru.cpp:(.text+0x18b): relocation truncated to fit: R_X86_64_PC32 against symbol `pw' defined in .bss section in /tmp/ccfdNwEM.o
peru.cpp:(.text+0x19b): relocation truncated to fit: R_X86_64_PC32 against symbol `pw' defined in .bss section in /tmp/ccfdNwEM.o
peru.cpp:(.text+0x35a): relocation truncated to fit: R_X86_64_PC32 against symbol `pw' defined in .bss section in /tmp/ccfdNwEM.o
peru.cpp:(.text+0x36d): relocation truncated to fit: R_X86_64_PC32 against symbol `dp' defined in .bss section in /tmp/ccfdNwEM.o
/tmp/ccfdNwEM.o: in function `_GLOBAL__sub_I_dp':
peru.cpp:(.text.startup+0xb): relocation truncated to fit: R_X86_64_PC32 against `.bss'
peru.cpp:(.text.startup+0x29): relocation truncated to fit: R_X86_64_PC32 against `.bss'
/usr/lib/gcc/x86_64-linux-gnu/10/libstdc++.a(vterminate.o): in function `__gnu_cxx::__verbose_terminate_handler()':
(.text._ZN9__gnu_cxx27__verbose_terminate_handlerEv+0x1e): relocation truncated to fit: R_X86_64_PC32 against `.bss._ZZN9__gnu_cxx27__verbose_terminate_handlerEvE11terminating'
(.text._ZN9__gnu_cxx27__verbose_terminate_handlerEv+0x2b): relocation truncated to fit: R_X86_64_PC32 against `.bss._ZZN9__gnu_cxx27__verbose_terminate_handlerEvE11terminating'
/usr/bin/ld: failed to convert GOTPCREL relocation; relink with --no-relax
collect2: error: ld returned 1 exit status