Submission #1104465

#TimeUTC-0UsernameProblemLanguageResultExecution timeMemory
11044652024-10-23 20:51:30BF001Split the sequence (APIO14_sequence)C++17
71 / 100
336 ms131072 KiB
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define N 100005
#define oo 1e18
#define int long long
typedef pair<int, long long> ii;
typedef pair<int, pair<long long, long long>> iii;
struct cht{
deque<iii> q;
long long get(ii tmp, long long x){
return tmp.fi * x + tmp.se;
}
bool cal(ii a, ii b, ii c){
return ((long long) 1ll * (c.se - a.se) * (b.fi - c.fi) >= 1ll * (c.se - b.se) * (a.fi - c.fi));
}
void add(long long a, long long b, int pos){
iii nw = {pos, {a, b}};
while ((int) q.size() >= 2 && cal(q[(int)q.size() - 2].se, q[(int)q.size() - 1].se, nw.se)) q.pop_back();
q.push_back(nw);
}
ii get(long long pos){
if (!(int) q.size()) return {0, -oo};
while ((int) q.size() >= 2 && get(q[0].se, pos) <= get(q[1].se, pos)) q.pop_front();
return {q[0].fi, get(q[0].se, pos)};
}
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:69:39: warning: unused variable 'nn' [-Wunused-variable]
   69 |     long long res = -oo; int pos = 0, nn = k;
      |                                       ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...