Submission #655342

#	Time	Username	Problem	Language	Result	Execution time	Memory
655342		kingfran1907	Peru (RMI20_peru)	C++14	0 / 100	1 ms	468 KiB

peru

#include "peru.h"
#include <bits/stdc++.h>
#define X first
#define Y second

typedef long long llint;
using namespace std;

const int mod = 1e9+7;
const int maxn = 25e5+10;

struct node {
    int ind;
    int first;
    llint second;

    node(int ind, int first, llint second) {
        this->ind = ind;
        this->first = first;
        this->second = second;
    }
    pair<int, llint> p() {return {first, second};}
};

llint dp[maxn];
deque< node > s;
stack< llint > l, r;

int mul(int a, int b) {
    llint out = (llint)a * b;
    return out % mod;
}

void rebuild() {
    while (!l.empty()) l.pop();
    while (!r.empty()) r.pop();
    deque< node > c = s;
    int kol = c.size() / 2;

    stack< llint > t;
    for (int i = 0; i < kol; i++) {
        t.push(c.front().X + c.front().Y);
        c.pop_front();
    }
    while (!t.empty()) {
        if (l.empty() || l.top() >= t.top()) l.push(t.top());
        t.pop();
    }

    while (!c.empty()) {
        t.push(c.back().X + c.back().Y);
        c.pop_back();
    }
    while (!t.empty()) {
        if (r.empty() || r.top() >= t.top()) r.push(t.top());
        t.pop();
    }
}

void pop_right() {
    //printf("poppin\n");
    llint x = s.back().X + s.back().Y;
    s.pop_back();
    if (r.empty()) rebuild();
    else if (r.top() == x) r.pop();
}

void pop_left(int y) {
    node tr = s.front();
    int ind = tr.ind;
    llint x = tr.X + tr.Y;

    s.pop_front();
    if (l.empty()) rebuild();
    else if (l.top() == x) l.pop();

    if (y < ind) {
        tr.Y = dp[y + 1];
        if (l.empty() || l.top() >= tr.X + tr.Y) l.push(tr.X + tr.Y);
        s.push_front(tr);
    }
}

bool cmp(pair<int, llint> a, pair<int, llint> b) {
    if (a.X == b.X) return a.Y < b.Y;
    else return a.X > b.X;
}

void push_right(int h, llint val, int ind) {
    while (!s.empty() && cmp({h, val}, s.back().p())) {
        val = min(val, s.back().Y);
        pop_right();
    }
    s.push_back(node(ind, h, val));
    if (r.empty() || r.top() >= h + val) r.push(h + val);
}

void debug() {
    printf("deque: ");
    for (auto iter : s) printf("(%d %lld, %d) ", iter.X, iter.Y, iter.ind);
    printf("\n");
}

llint get_min() {
    llint out = 1LL << 60;
    if (!l.empty()) out = min(out, l.top());
    if (!r.empty()) out = min(out, r.top());
    return out;
}

int solve(int n, int k, int* v){
    push_right(v[0], 0, 0);
    for (int i = 1; i <= n; i++) {
        dp[i] = get_min();
        //debug();
        //printf("dp %d: %lld\n", i, dp[i]);
        if (i < n) push_right(v[i], dp[i], i);
        if (i >= k) pop_left(i - k);
    }
    printf("\n");

    int sol = 0;
    int pot = 1;
    for (int i = n; i >= 0; i--) {
        sol += mul(dp[i] % mod, pot), sol %= mod;
        pot = mul(pot, 23);
    }
    return sol;
}

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