Submission #172798

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
172798	2020-01-02 16:14:54	RafaelSus	Split the sequence (APIO14_sequence)	C++14	71 / 100	2063 ms	125580 KiB

sequence

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
 
using namespace std;
const int N = 2e5 + 5;
typedef long long ll;
const ll inf=1e15;
#define pb push_back
const int INF=(0x3f3f3f3f);
 
vector<ll>m,b,idx;
int ptr;
 
void add(ll _m,ll _b,ll _idx){
  while(m.size()>=2){
    if((b.back()-_b)*(_m-m[m.size()-2])>=(b[b.size()-2]-_b)*(_m-m.back())){
      m.pop_back();
      b.pop_back();
      idx.pop_back();
    }
    else break;
  }
  m.pb(_m);
  b.pb(_b);
  idx.pb(_idx);
}
 
ll func(int pos,ll x){
  return m[pos]*x+b[pos];
}
 
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

sequence.cpp: In function 'std::pair<long long int, long long int> get(ll)':
sequence.cpp:32:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(ptr>=m.size())ptr=m.size()-1;
      ~~~^~~~~~~~~~
sequence.cpp:33:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(ptr+1<m.size()&&func(ptr,x)<=func(ptr+1,x))ptr++;
         ~~~~~^~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 17 / 17
• Subtask 5: 21 / 21
• Subtask 6: 0 / 29