Submission #206891

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
206891	2020-03-05 17:30:01	tuna	Split the sequence (APIO14_sequence)	C++11	11 / 100	79 ms	131076 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;
#define int long long
typedef pair <int, int> ii;
 
const int N = 1e5 + 5, oo = 1e18, K = 200;
int a[N], suf[N], pref[N], n, dp[2][N], trace[N][K];
 
struct Line {
  int a, b, id;
  Line() {}
  Line(int _a, int _b, int _id) : a(_a), b(_b), id(_id) {}
  int val(int x) {
    return a * x + b;
  }
};
 
struct CHT {
  vector <Line> st;
  CHT() {st.clear();}
  bool bad(Line a, Line b, Line c) {
    return (1.0 * (c.b - a.b) / (a.a - c.a) < 1.0 * (c.b - b.b) / (b.a - c.a));
  }
  void addLine(Line d) {
    while (st.size() >= 2 && bad(d, st.back(), st[st.size() - 2])) {
      // cerr << "delete Line y = " << st.back().a << "x + " << st.back().b << endl;
      st.pop_back();
    }
    // cerr << "addLine y = " << d.a << "x + " << d.b << endl;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

sequence.cpp: In member function 'ii CHT::query(long long int)':
sequence.cpp:39:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (mid != st.size() - 1 && st[mid + 1].val(x) > cur) l = mid + 1;
        ~~~~^~~~~~~~~~~~~~~~

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