QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#377151 | #149. Peru | ltunjic | Compile Error | / | / | C++14 | 2.3kb | 2024-04-04 23:18:21 | 2024-09-10 16:45:52 |
Judging History
This is the latest submission verdict.
- [2024-09-10 16:45:52]
- 管理员手动重测本题所有提交记录
- Verdict: Compile Error
- Time: 0ms
- Memory: 0kb
- [2024-04-04 23:18:21]
- Judged
- Verdict: Compile Error
- Time: 0ms
- Memory: 0kb
- [2024-04-04 23:18:21]
- Submitted
answer
#include <cstdio>
#include <deque>
#include <queue>
#include <stack>
using namespace std;
typedef long long ll;
const int N = 3e6 + 10;
const int MOD = 1e9 + 7;
const ll OO = 1e18;
int add(int a, int b) {
if(a + b < MOD) return a + b;
return a + b - MOD;
}
int mult(int a, int b) {
return (ll) a * b % MOD;
}
struct bit {
ll val, ind, mx;
bit(ll val, ll ind, ll mx) : val(val), ind(ind), mx(mx) {}
bool operator < (bit x) { return val < x.val; }
bool operator == (bit x) { return val == x.val && ind == x.ind && mx == x.mx; }
};
struct monotog {
deque<bit> D;
bool empty() { return D.empty(); }
ll get() { return D.empty() ? OO : D.back().val; }
void push(bit x) {
if(get() >= x.val) D.push_back(x);
else D.push_back(D.back());
}
void pop() { D.pop_back(); }
void clear() { for(; !D.empty(); pop()); }
};
struct monodeq {
monotog L, R;
deque<bit> D;
bool empty() { return D.empty(); }
ll get() { return min(L.get(), R.get()); }
void reload() {
L.clear();
R.clear();
int siz = (int) D.size() / 2;
for(int i = siz; i < D.size(); ++i) R.push(D[i]);
for(int i = siz - 1; i >= 0; --i) L.push(D[i]);
}
void push_front(bit x) { L.push(x); D.push_front(x); }
void push_back(bit x) { R.push(x); D.push_back(x); }
void pop_front() {
D.pop_front();
if(L.empty()) reload();
else L.pop();
}
void pop_back() {
D.pop_back();
if(R.empty()) reload();
else R.pop();
}
bit front() { return D.front(); }
};
int n, k;
ll DP[N];
deque<bit> Q;
monodeq D;
int main() {
scanf("%d%d", &n, &k);
for(int i = 1; i <= n; ++i) {
int x; scanf("%d", &x);
int ind = i - 1;
for(; !Q.empty() && Q.back().mx < x; Q.pop_back()) {
ind = Q.back().ind;
D.pop_back();
}
Q.push_back(bit(DP[ind] + x, ind, x));
D.push_back(Q.back());
// printf("%lld\n", D.get());
if(i > k) {
bit lst = D.front();
Q.pop_front();
D.pop_front();
if(D.empty() || lst.ind + 1 != D.front().ind) {
Q.push_front(bit(DP[lst.ind + 1] + lst.mx, lst.ind + 1, lst.mx));
D.push_front(Q.front());
}
}
DP[i] = D.get();
// printf("%d %lld\n", i, DP[i]);
}
int ans = 0, p = 1;
for(int i = n; i >= 1; --i) {
ans = add(ans, mult(DP[i] % MOD, p));
p = mult(p, 23);
}
printf("%d\n", ans);
return 0;
}
Details
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; | ~~~~~^~~~~~~~~~~~~~~~~~~~~~~ answer.code: In function ‘int main()’: answer.code:77:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 77 | scanf("%d%d", &n, &k); | ~~~~~^~~~~~~~~~~~~~~~ answer.code:79:29: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 79 | int x; scanf("%d", &x); | ~~~~~^~~~~~~~~~ /usr/bin/ld: /tmp/ccuz5oj0.o: in function `main': answer.code:(.text.startup+0x0): multiple definition of `main'; /tmp/ccV4bIqZ.o:implementer.cpp:(.text.startup+0x0): first defined here /usr/bin/ld: /tmp/ccV4bIqZ.o: in function `main': implementer.cpp:(.text.startup+0x151): undefined reference to `solve(int, int, int*)' collect2: error: ld returned 1 exit status