Submission #150893

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
150893	2019-09-01 10:12:14	dragoon	Organizing the Best Squad (FXCUP4_squad)	C++17	100 / 100	1034 ms	55460 KiB

squad

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 "squad.h"
#include<vector>
#include<algorithm>
#include<assert.h>
#include<utility>
using namespace std;
typedef long long LL;
//StaticCHT<LL> cht;
//cht.InsertLine({ id, m, c });
//auto ret = cht.SlidingEval(x);
template<class T = LL>
struct Line {
  int id;
  // y = mx + c
  T m, c;
  // The line starts from start_x.
  static const LL MIN_START_X = 0;
  long double start_x;
  LL Eval(LL x) { return m * x + c; }
  long double Eval(long double x) { return m * x + c; }
  long double Intersect(const Line& other) {
    // mx + c = other.m * x + other.c
    long double num = other.c - c;
    long double den = m - other.m;
    assert(m != other.m);
    return num / den;
  }
};
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

squad.cpp: In instantiation of 'std::vector<int> StaticCHT<T>::Eval(double, int) [with T = long long int]':
squad.cpp:136:44:   required from here
squad.cpp:88:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (qmode && lo + 1 < ch.size()) V.push_back(ch[lo + 1].id);

• Subtask 1: 19 / 19
• Subtask 2: 28 / 28
• Subtask 3: 53 / 53