Submission #35633

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
35633	2017-11-26 13:32:29	szawinis	Building Bridges (CEOI17_building)	C++14	100 / 100	189 ms	13900 KiB

building

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;
typedef long long ll;
const ll MOD = (1e9)+7, INF = 1e18;
const int MAX = (1e5)+1;
struct line {
  ll m, c;
  mutable function<const line*()> succ;
  ll getVal(ll x) { return m*x + c; }
  bool operator<(const line& rhs) const {
    if(rhs.c != -INF) return m > rhs.m;
    const line* s = succ();
    if(!s) return false;
    return ((double) c - s->c > (double) (s->m - m)*rhs.m);
  }
};
class MinHull : public multiset<line> {
  bool bad(iterator it) {
    auto nxt = next(it);
    if(it == begin()) {
      if(nxt != end()) return nxt->m == it->m && nxt->c <= it->c;
      else return false;
    }
    auto pre = prev(it);
    if(nxt == end()) return pre->m == it->m && pre->c <= it->c;
    line l1 = *pre, l2 = *it, l3 = *nxt;
    return (double) (l3.c-l1.c)*(l1.m-l2.m) <= (double) (l2.c-l1.c)*(l1.m-l3.m);
  }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40