Submission #656823

#TimeUsernameProblemLanguageResultExecution timeMemory
656823lovrotPeru (RMI20_peru)C++17
Compilation error
0 ms0 KiB
#include <bits/stdc++.h> #include "peru.h" #define X first #define Y second #define ll long long #define pii pair<ll, ll> using namespace std; const ll INF = 1e18; const ll MOD = 1e9 + 7; const int N = 2500010; ll dp[N]; ll d[2 * N + 10]; int l_ind = N, r_ind = N + 1; stack<pii> hist; stack<pii> l, r; ll add(ll a, ll b){ if(a + b < MOD) return a + b; return a + b - MOD; } ll mult(ll a, ll b){ return (ll) a * b % MOD; } ll eval(int n){ ll res = 0; ll prod = 1; for(int i = n - 1; i >= 0; i--){ res = add(res, mult(dp[i], prod)); prod = mult(prod, 23); } return res; } ////////////////////////////////////////////////// int histogram(int x, ll val){ int ret = 0; while(!hist.empty() && hist.top().X < val){ hist.pop(); } if(!hist.empty()) ret = hist.top().Y + 1; hist.push({val, x}); return ret; } void pop(stack<pii> &p){ //stack if(!p.empty()) p.pop(); } void push(stack<pii> &p, ll val){ //stack if(p.empty()) p.push({val, val}); else p.push({val, min(val, p.top().Y)}); } void build(){ //deck if(!l.empty() && !r.empty()) return; while(!l.empty()) pop(l); while(!r.empty()) pop(r); int mi = (l_ind + r_ind) / 2; for(int i = mi; i > l_ind; i--) push(l, d[i]); for(int i = mi + 1; i < r_ind; i++) push(r, d[i]); } void pop_left(){ l_ind++; pop(l); build(); } void pop_right(){ r_ind--; pop(r); build(); } void push_right(ll val){ d[r_ind] = val; r_ind++; push(r, val); } ll getMin(){ ll ret = INF; if(!l.empty()) ret = min(ret, l.top().Y); if(!r.empty()) ret = min(ret, r.top().Y); return ret; } int solve(int n, int k, int *s){ dp[0] = s[0]; push_right(dp[0]); histogram(0, s[0]); for(int i = 1; i < n; i++){ if(i >= k) pop_left(); int pos = max(histogram(i, s[i]), i - k + 1); //printf("%d: %d\n", i, pos); for(int j = pos; j < i; j++) pop_right(); for(int j = pos; j <= i; j++){ if(j > 0) push_right(dp[j - 1] + s[i]); else push_right(s[i]); } dp[i] = getMin(); } for(int i = 0; i < n; i++) printf("%lld ", dp[i]); printf("\n"); return eval(n); } int main(){ int n, k; scanf("%d%d", &n, &k); int arr[n]; for(int i = 0; i < n; i++) scanf("%d", &arr[i]); printf("%d\n", solve(n, k, arr)); return 0; }

Compilation message (stderr)

peru.cpp: In function 'int main()':
peru.cpp:117:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  117 |  scanf("%d%d", &n, &k);
      |  ~~~~~^~~~~~~~~~~~~~~~
peru.cpp:119:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  119 |  for(int i = 0; i < n; i++) scanf("%d", &arr[i]);
      |                             ~~~~~^~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/ccuElXl0.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccugISIX.o:peru.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status