Submission #1296958

#	Time	Username	Problem	Language	Result	Execution time	Memory
1296958		NotLinux	Peru (RMI20_peru)	C++20	0 / 100	569 ms	49456 KiB

peru

#include "peru.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int)x.size()
#define all(x) x.begin() , x.end()
const int inf = 1e18 + 7;
const int mod = 1e9 + 7;
long long fastpow(long long a , long long b){
    long long ret = 1;
    while(b){
        if(b&1)ret = ret * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ret;
}
struct SEGTmax{
    vector < int > t;
    int tree_size;
    const int identity_element = -inf;
    int merge(int x , int y){ 
        return max(x,y);
    }
    void init(int x){
        tree_size = x+3;
        t.assign(2*tree_size , identity_element);
    }
    void modify(int p, int value) {  // set value at position p
        for (t[p += tree_size] = value; p > 1; p >>= 1){
            t[p>>1] = merge(t[p] , t[p^1]); 
        }
    }
    int query(int l, int r) {  // sum on interval [l, r]
        int res = identity_element;
        for (r+=1 , l += tree_size, r += tree_size; l < r; l >>= 1, r >>= 1) {
            if (l&1) res = merge(res , t[l++]); 
            if (r&1) res = merge(res , t[--r]); 
        }
        return res;
    }
};
struct SEGTmin{
    vector < int > t;
    int tree_size;
    const int identity_element = inf;
    int merge(int x , int y){ 
        return min(x,y);
    }
    void init(int x){
        tree_size = x+3;
        t.assign(2*tree_size , identity_element);
    }
    void modify(int p, int value) {  // set value at position p
        for (t[p += tree_size] = value; p > 1; p >>= 1){
            t[p>>1] = merge(t[p] , t[p^1]); 
        }
    }
    int query(int l, int r) {  // sum on interval [l, r]
        int res = identity_element;
        for (r+=1 , l += tree_size, r += tree_size; l < r; l >>= 1, r >>= 1) {
            if (l&1) res = merge(res , t[l++]); 
            if (r&1) res = merge(res , t[--r]); 
        }
        return res;
    }
};
int solve(int n, int k, int* v){
    SEGTmax arr;
    arr.init(n);
    SEGTmin dp;
    dp.init(n);
    for(int i = 0;i<n;i++){
        arr.modify(i , v[i]);
    }
    long long ans = 0;
    dp.modify(0 , 0);
    for(int i = 0;i<n;i++){
        int val = arr.query(max(0,i-k+1) , i) + dp.query(max(0,i+1-k) , i);
        // cout << "bruh : " << dp.query(max(0ll,i+1-k),i) << endl;
        // cout << i+1 << " : " << val << endl;
        dp.modify(i+1 , val);
        ans = 1LL * (ans + 1LL * val * fastpow(23,n-i-1) % mod) % mod;
    }
    return ans;
}

// signed main(){
//     int n,k;
//     cin >> n >> k;
//     int arr[n];
//     for(int i = 0;i<n;i++)cin >> arr[i];
//     cout << solve(n,k,arr) << endl;
// }

Compilation message (stderr)

peru.cpp:6:22: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
    6 | const int inf = 1e18 + 7;
      |                 ~~~~~^~~

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