Submission #13773

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
13773	2015-04-01 09:03:47	comet	Split the sequence (APIO14_sequence)	C++98	100 / 100	1247 ms	85484 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<cstdio>
#include<algorithm>
#include<deque>
using namespace std;
typedef long long ll;
typedef pair<ll,int> pp;
ll d[2][100010],s[100010],N,K;
int r[201][100001];
void f(int x,int y){
  if(x==1)return;
  f(x-1,r[x][y]);
  printf("%d ",r[x][y]);
}
struct convex{
  deque<ll> a,b;
  deque<int> c;
  void init(){a.clear();b.clear();c.clear();}
  void push(ll n,ll m,int v){
    while(a.size()>1&&(b[b.size()-2]-b.back())*(n-a.back())>=(b.back()-m)*(a.back()-a[a.size()-2])){
      a.pop_back();
      b.pop_back();
      c.pop_back();
    }
    a.push_back(n);
    b.push_back(m);
    c.push_back(v);
  }
  pp query(ll x){
    while(a.size()>1&&(a[1]-a[0])*x>(b[0]-b[1])){
      a.pop_front();
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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