Submission #872598

#	Time	Username	Problem	Language	Result	Execution time	Memory
872598		sleepntsheep	Peru (RMI20_peru)	C++17	100 / 100	140 ms	44184 KiB

peru

#include "peru.h"
#include <utility>
#include <cassert>
#include <tuple>
#include <utility>
#include <iostream>
#include <algorithm>
#include <stack>

#if 0
struct minstack {
	stack<pair<int, int>> st;
	int getmin() {return st.top().second;}
	bool empty() {return st.empty();}
	int size() {return st.size();}
	void push(int x) {
		int mn = x;
		if (!empty()) mn = min(mn, getmin());
		st.push({x, mn});
	}
	void pop() {st.pop();}
	int top() {return st.top().first;}
	void swap(minstack &x) {st.swap(x.st);}
};

struct mindeque {
	minstack l, r, t;
	void rebalance() {
		bool f = false;
		if (r.empty()) {f = true; l.swap(r);}
		int sz = r.size() / 2;
		while (sz--) {t.push(r.top()); r.pop();}
		while (!r.empty()) {l.push(r.top()); r.pop();}
		while (!t.empty()) {r.push(t.top()); t.pop();}
		if (f) l.swap(r);
	}
	int getmin() {
		if (l.empty()) return r.getmin();
		if (r.empty()) return l.getmin();
		return min(l.getmin(), r.getmin());
	}
	bool empty() {return l.empty() && r.empty();}
	int size() {return l.size() + r.size();}
	void push_front(int x) {l.push(x);}
	void push_back(int x) {r.push(x);}
	void pop_front() {if (l.empty()) rebalance(); l.pop();}
	void pop_back() {if (r.empty()) rebalance(); r.pop();}
	int front() {if (l.empty()) rebalance(); return l.top();}
	int back() {if (r.empty()) rebalance(); return r.top();}
	void swap(mindeque &x) {l.swap(x.l); r.swap(x.r);}
};
#endif

#if 1
template <typename T, const T& (*F)(const T&, const T&)>
struct stack
{
    std::stack<std::pair<T, T>> a;

    void push(const T &v)
    {
        if (a.empty()) a.push({v, v});
        else a.push({v, F(a.top().second, v)});
    }

    bool empty()
    {
        return a.empty();
    }

    size_t size()
    {
        return a.size();
    }

    T top()
    {
        return a.top().first;
    }

    T op()
    {
        return a.top().second;
    }

    void pop()
    {
        a.pop();
    }

    void swap(stack &x) {a.swap(x.a);}
};

template <typename T, const T& (*F)(const T&, const T&)>
struct deque
{
    stack<T, F> f, b, t;

    deque() { }

    void rebalance() {
        bool a = false;
        if (b.empty()) {a = true; f.swap(b);}
        int sz = b.size() / 2;
        while (sz--) {t.push(b.top()); b.pop();}
        while (!b.empty()) {f.push(b.top()); b.pop();}
        while (!t.empty()) {b.push(t.top()); t.pop();}
        if (a) f.swap(b);
    }

    void push_back(const T &v)
    {
        b.push(v);
    }

    void pop_front()
    {
        if (f.empty()) rebalance();
        f.pop();
    }

    void pop_back()
    {
        if (b.empty()) rebalance();
        b.pop();
    }

    T front()
    {
        if (f.empty()) rebalance();
        return f.top();
    }

    T back()
    {
        if (b.empty()) rebalance();
        return b.top();
    }

    T op()
    {
        if (f.empty()) return b.op();
        if (b.empty()) return f.op();
        return F(f.op(), b.op());
    }

    size_t size()
    {
        return f.size() + b.size();
    }
};
#else

template <typename T, const T& (*F)(const T&, const T&)>
struct deque :std::deque<T>
{
    T op()
    {
        T x = this->front();
        for (auto y : *this) x = F(x, y);
        return x;
    }
};
#endif

using i64 = long long;
using u64 = unsigned long long;

int solve(int n, int k, int* v)
{
    i64 *dp = new i64[n];

    std::deque<int> dq;
    deque<i64, std::min> qry;

    for (int i = 0; i < n; ++i)
    {
        while (dq.size() && v[dq.back()] <= v[i])
        {
            dq.pop_back();
            if (dq.size()) qry.pop_back();
        }

        if (dq.size()) qry.push_back(dp[dq.back()] + v[i]);
        dq.push_back(i);

        if (dq.size() && dq.front() + k == i)
        {
            dq.pop_front();
            if (dq.size()) qry.pop_front();
        }

        if (i >= k) dp[i] = dp[i-k] + v[dq.front()];
        else dp[i] = v[dq.front()];
        if (qry.size()) dp[i] = std::min(dp[i], qry.op());
    }

    constexpr const i64 M = 1000000007;
    i64 x = 0;
    for (size_t i = 0; i < n; ++i) x = (x * 23ll % M + dp[i]) % M;
    
    delete []dp;

    return int(x);
}

Compilation message (stderr)

peru.cpp: In function 'int solve(int, int, int*)':
peru.cpp:200:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  200 |     for (size_t i = 0; i < n; ++i) x = (x * 23ll % M + dp[i]) % M;
      |                        ~~^~~

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