Submission #1060257

#	Time	Username	Problem	Language	Result	Execution time	Memory
1060257		prvocislo	Peru (RMI20_peru)	C++17	0 / 100	1 ms	4444 KiB

peru

// What we thought was for all time was momentary
// Still alive, killing time at the cemetery, never quite buried
 
#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <string>
#include <vector>
#include "peru.h"
typedef long long ll;
typedef long double ld;
using namespace std;
 
const int mod = 1e9 + 7, base = 23;
void upd(int& a, int b) { a = (a + b) % mod; }
int add(int a, int b) { return (a + b) % mod; }
int mul(int a, int b) { return (a * 1ll * b) % mod; }
 
const int maxn = 2.5e6 + 5;
int p[maxn];
ll dp[maxn], s[maxn];
int root(int i) { return p[i] == i ? i : p[i] = root(p[i]); }
void merge(int i, int j)
{
    i = root(i), j = root(j);
    p[i] = j;
}
ll eval(int i)
{
    return dp[i] + s[root(i)];
}
deque<int> dpq;
deque<int> mq;
int solve(int n, int k, int* S)
{
    for (int i = 0; i < n; i++) s[i] = S[i], p[i] = i;
    for (int i = 1; i <= n; i++) // ideme postavit prefix dlzky i
    {
        if (dpq.size() && dpq.front() == i - k - 1) dpq.pop_front();
        if (mq.size() && mq.front() == i - k - 1) mq.pop_front();
        while (mq.size() && s[mq.back()] < s[i - 1]) merge(mq.back(), i - 1), mq.pop_back();
        mq.push_back(i - 1);
        while (dpq.size() && eval(i - 1) < eval(dpq.back())) dpq.pop_back();
        dpq.push_back(i - 1);
        dp[i] = eval(dpq.front());
        //cout << i << " : " << dp[i] << "\n";
    }
    int ans = 0, m = 1;
    for (int i = n; i >= 1; i--) upd(ans, mul(dp[i] % (ll)mod, m)), m = mul(m, base);
    return ans;
}

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