fork download

copy

struct convex_hull {
	deque <pi> dq;
	ll f(pi line, ll x) { //y = mx + c;
		return line.f * x + line.s;
	}
	ll query(ll x) {
		while(dq.size() > 1) {
			if(f(dq[0], x) < f(dq[1], x)) dq.pop_front();
			else break;
		}
		return f(dq[0], x);
	}
	ld intersect(ll m1, ll c1, ll m2, ll c2) {
		return (ld)(c2-c1)/(ld)(m1-m2);
	}
	ld intersect(pi line1, pi line2) {
		return intersect(line1.f, line1.s, line2.f, line2.s);
	}
	void insert(ll m, ll c) {
		pi line = pi(m, c);
		while(dq.size() > 1) {
			ll s = dq.size();
			if(intersect(dq[s-1], line) <= intersect(dq[s-2], line)) dq.pop_back();
			else break;
		}
		dq.pb(line);
	}
} ch;
 
// and my insert and query part was something like this:
sort(g.begin(), g.end(), [](pair<ll,ll> x,pair<ll,ll> y){
    if(x.s^y.s)return x.s<y.s;
    else return x.f>y.f;
});
ch.insert(0,-LLINF);
for(auto i:g) {
    ans=max(ans,i.f + n*i.s - i.s*i.s + ch.query(-2*i.s));
    ch.insert(i.s, i.f + n*i.s - i.s*i.s);
}

prog.cpp:2:2: error: ‘deque’ does not name a type
  deque <pi> dq;
  ^~~~~
prog.cpp:3:2: error: ‘ll’ does not name a type
  ll f(pi line, ll x) { //y = mx + c;
  ^~
prog.cpp:6:2: error: ‘ll’ does not name a type
  ll query(ll x) {
  ^~
prog.cpp:13:2: error: ‘ld’ does not name a type
  ld intersect(ll m1, ll c1, ll m2, ll c2) {
  ^~
prog.cpp:16:2: error: ‘ld’ does not name a type
  ld intersect(pi line1, pi line2) {
  ^~
prog.cpp:19:14: error: ‘ll’ has not been declared
  void insert(ll m, ll c) {
              ^~
prog.cpp:19:20: error: ‘ll’ has not been declared
  void insert(ll m, ll c) {
                    ^~
prog.cpp: In member function ‘void convex_hull::insert(int, int)’:
prog.cpp:20:3: error: ‘pi’ was not declared in this scope
   pi line = pi(m, c);
   ^~
prog.cpp:21:9: error: ‘dq’ was not declared in this scope
   while(dq.size() > 1) {
         ^~
prog.cpp:22:4: error: ‘ll’ was not declared in this scope
    ll s = dq.size();
    ^~
prog.cpp:23:20: error: ‘s’ was not declared in this scope
    if(intersect(dq[s-1], line) <= intersect(dq[s-2], line)) dq.pop_back();
                    ^
prog.cpp:23:26: error: ‘line’ was not declared in this scope
    if(intersect(dq[s-1], line) <= intersect(dq[s-2], line)) dq.pop_back();
                          ^~~~
prog.cpp:23:26: note: suggested alternative: ‘linux’
    if(intersect(dq[s-1], line) <= intersect(dq[s-2], line)) dq.pop_back();
                          ^~~~
                          linux
prog.cpp:23:7: error: ‘intersect’ was not declared in this scope
    if(intersect(dq[s-1], line) <= intersect(dq[s-2], line)) dq.pop_back();
       ^~~~~~~~~
prog.cpp:23:7: note: suggested alternative: ‘insert’
    if(intersect(dq[s-1], line) <= intersect(dq[s-2], line)) dq.pop_back();
       ^~~~~~~~~
       insert
prog.cpp:26:3: error: ‘dq’ was not declared in this scope
   dq.pb(line);
   ^~
prog.cpp:26:9: error: ‘line’ was not declared in this scope
   dq.pb(line);
         ^~~~
prog.cpp:26:9: note: suggested alternative: ‘linux’
   dq.pb(line);
         ^~~~
         linux
prog.cpp: At global scope:
prog.cpp:31:5: error: expected constructor, destructor, or type conversion before ‘(’ token
 sort(g.begin(), g.end(), [](pair<ll,ll> x,pair<ll,ll> y){
     ^
prog.cpp:34:2: error: expected unqualified-id before ‘)’ token
 });
  ^
prog.cpp:35:1: error: ‘ch’ does not name a type
 ch.insert(0,-LLINF);
 ^~
prog.cpp:36:1: error: expected unqualified-id before ‘for’
 for(auto i:g) {
 ^~~

Standard output is empty