QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#138942	#149. Peru	bashkort^#	Compile Error	/	/	C++20	2.5kb	2023-08-12 14:41:34	2024-07-04 01:37:59

Judging History

你现在查看的是测评时间为 2024-07-04 01:37:59 的历史记录

[2024-09-10 16:40:59]
管理员手动重测本题所有提交记录

测评结果：18
用时：2ms
内存：8024kb

查看

[2024-07-04 01:37:59]
评测

测评结果：Compile Error
用时：0ms
内存：0kb

查看

[2023-08-12 14:41:34]
提交

answer

#include "peru.h"
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

constexpr int MOD = 1e9 + 7;
constexpr ll infLL = 3e18;

namespace SegmentTree {
    vector<ll> t, tag;
    int sz = 1;

    void init(int n) {
        sz = 1 << __lg(n) + !!(n & (n - 1));
        t.assign(sz << 1, infLL);
        tag.assign(sz << 1, 0);
    }

    void apply(int x, ll tg) {
        t[x] += tg, tag[x] += tg;
    }

    void push(int x) {
        if (tag[x]) {
            apply(x << 1, tag[x]);
            apply(x << 1 | 1, tag[x]);
            tag[x] = 0;
        }
    }

    void pull(int x) {
        t[x] = min(t[x << 1], t[x << 1 | 1]);
    }

    void modify(int i, ll v, int x = 1, int lx = 0, int rx = sz) {
        if (lx + 1 == rx) {
            t[x] = v;
            return;
        }
        int mid = lx + rx >> 1;
        push(x);
        if (i < mid) {
            modify(i, v, x << 1, lx, mid);
        } else {
            modify(i, v, x << 1 | 1, mid, rx);
        }
        pull(x);
    }

    void rangeAdd(int l, int r, ll v, int x = 1, int lx = 0, int rx = sz) {
        if (l >= rx || lx >= r) {
            return;
        }
        if (l <= lx && rx <= r) {
            return apply(x, v);
        }
        int mid = lx + rx >> 1;
        push(x);
        rangeAdd(l, r, v, x << 1, lx, mid);
        rangeAdd(l, r, v, x << 1 | 1, mid, rx);
        pull(x);
    }

    ll rangeMin(int l, int r, int x = 1, int lx = 0, int rx = sz) {
        if (l >= rx || lx >= r) {
            return infLL;
        }
        if (l <= lx && rx <= r) {
            return t[x];
        }
        int mid = lx + rx >> 1;
        push(x);
        return min(rangeMin(l, r, x << 1, lx, mid), rangeMin(l, r, x << 1 | 1, mid, rx));
    }
};

constexpr int N = 2.5e6 + 7;

ll dp[N];
int stk[N], top = 0;

int solve(int n, int k, int a[]){
    SegmentTree::init(n + 1);
    SegmentTree::modify(0, 0);
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        while (top && a[stk[top - 1]] <= a[i]) {
            int l = top == 1 ? 0 : stk[top - 2] + 1;
            SegmentTree::rangeAdd(l, stk[top - 1] + 1, -a[stk[top - 1]]);
            --top;
        }
        stk[top++] = i;
        int l = top == 1 ? 0 : stk[top - 2] + 1;
        SegmentTree::rangeAdd(l, i + 1, a[i]);
        dp[i] = SegmentTree::rangeMin(max(0, i - k + 1), i + 1);
        SegmentTree::modify(i + 1, dp[i]);
        ans = (23LL * ans + dp[i]) % MOD;
    }
    return ans;
}

源文件, 语言: C++20

詳細信息

implementer.cpp: In function ‘int main()’:
implementer.cpp:34:13: error: ‘fout’ was not declared in this scope; did you mean ‘out’?
   34 |     fprintf(fout, "%d\n", sol);
      |             ^~~~
      |             out
implementer.cpp: In function ‘char nextch()’:
implementer.cpp:15:31: warning: ignoring return value of ‘size_t fread(void*, size_t, size_t, FILE*)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   15 |     if (pos == BUF_SIZE) fread(buf, BUF_SIZE, 1, fin), pos = 0;
      |                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~