oj.uz

Submission #483723

# Submission time Handle Problem Language Result Execution time Memory
483723 2021-11-01T01:28:11 Z tranxuanbach Peru (RMI20_peru) C++17
0 / 100
 1 ms 468 KB 
#include "peru.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
 
#define endl '\n'
#define fi first
#define se second
#define For(i, l, r) for (int i = l; i < r; i++)
#define ForE(i, l, r) for (int i = l; i <= r; i++)
#define FordE(i, l, r) for (int i = l; i >= r; i--)
#define Fora(v, a) for (auto v: a)
#define bend(a) a.begin(), a.end()
#define isz(a) ((signed)a.size())
 
typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
typedef vector <int> vi;
typedef vector <pii> vpii;
typedef vector <vi> vvi;
 
const int N = 2e6 + 5e5 + 5, M = 22, mod = 1e9 + 7;
const ll infll = (ld)1e18 + 7;
 
deque <pair <int, ll>> dq;
multiset <ll> mtsdp;
ll dp[N];
int a[N];
int sparse[M][N];

int rmq(int l, int r){
    int z = __lg(r - l + 1);
    return max(sparse[z][l], sparse[z][r - (1 << z) + 1]);
}

int convert(int n){
    int ans = 0;
    For(i, 0, n){
        ans = (ll)ans * 23 % mod;
        ans += dp[i] % mod;
        if (ans >= mod){
            ans -= mod;
        }
    }
    return ans;
}
 
int solve(int n, int k, int v[]){
    For(i, 0, n){
        a[i] = v[i];
    }
    For(i, 0, n){
        sparse[0][i] = a[i];
    }
    For(j, 1, M){
        ForE(i, 0, n - (1 << j)){
            sparse[j][i] = max(sparse[j - 1][i], sparse[j - 1][i + (1 << (j - 1))]);
        }
    }
    if (k == 1){
        For(i, 0, n){
            dp[i] = (i == 0 ? 0 : dp[i - 1]) + a[i];
        }
        return convert(n);
    }
    return 0;
    For(i, 0, n){
        int val = 0;
        while (!dq.empty() and a[dq.front().fi] <= a[i]){
            mtsdp.erase(mtsdp.lower_bound(dq.front().se));
            val = a[dq.front().fi];
            dq.pop_front();
        }
        if (!dq.empty()){
            mtsdp.erase(mtsdp.lower_bound(dq.front().se));
            dq.front().se -= val;
            dq.front().se += a[i];
            mtsdp.insert(dq.front().se);
        }
        dp[i] = infll;
        if (!mtsdp.empty()){
            dp[i] = *mtsdp.begin();
        }
        dp[i] = min(dp[i], rmq(max(0, i - k + 1), i) + (i >= k ? dp[i - k] : 0));
        dq.push_front(make_pair(i, dp[i]));
        mtsdp.insert(dp[i]);
        while (!dq.empty() and dq.back().fi == i - k + 1){
            mtsdp.erase(mtsdp.lower_bound(dq.back().se));
            dq.pop_back();
        }
    }
    // For(i, 0, n){
    //     cout << dp[i] << ' ';
    // } cout << endl;
    return convert(n);
}
 
 
/*
==================================================+
INPUT:                                            |
--------------------------------------------------|
 
--------------------------------------------------|
==================================================+
OUTPUT:                                           |
--------------------------------------------------|
 
--------------------------------------------------|
==================================================+
*/

Subtask #1
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 468 KB Output isn't correct
2 Halted 0 ms 0 KB -