北京八十中集训——day1

比赛总结

预计：？+0+0
实际：70+0+0

考试过程

想了会儿T1，感觉好像会做，于是就写了，写了到两个半小时左右的时候，一直调，调了几个bug。最后的bug是找到最小的合法的斜率和最大的合法的斜率。
最后11:30的时候，想先去写暴力，但是想到调出了就100，不调了的话就可能0分了，于是又继续调，终于到12:00发现不太会这个东西，于是就想去写T2,T3，结果比赛结束了，一直以为12:30结束。。。

总结：
注意一下时间，分配好时间
可以先打暴力。

T1

幸亏数据水，不然爆零了。。。
最后的判断最小最大的斜率，可以用旋转卡壳，回去再学学这个东西。

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iostream>
#include<cmath>
#include<cctype>
#include<set>
#include<vector>
#include<queue>
#include<map>
using namespace std;
typedef long long LL;
inline int read() {
    int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
}
const int N = 300005;
const int INF = 1e9 + 10;
struct Node {
    int k, b, l, r;
    Node() {}
    Node(int _k,int _b,int _l,int _r) { k = _k, b = _b, l = _l, r = _r; }
}s1[N], s2[N];
int u[N], d[N];
double Slope(int i,int x1,int j,int x2) {
    return 1.0 * (x2 - x1) / (1.0 * (j - i));
}
double jiao(const Node &A,const Node &B) {
    return (1.0 * (B.b - A.b)) / (1.0 * (A.k - B.k));
}
inline LL dc(int a1,int d,int n) {
    return 1ll * n * a1 + 1ll * (n * (n - 1)) / 2 * d;
}
inline LL qz(int a,const Node &A) {
    return 1ll * A.k * a + A.b;
}
LL Calc(int l,int r,const Node &A,const Node &B) {
    if (l > r) return 0;
    LL n1 = dc(qz(l, A), A.k, r - l + 1);
    LL n2 = dc(qz(l, B), B.k, r - l + 1);
    if (n1 - n2 + 1ll * (r - l + 1) < 0) return 0;
    return n1 - n2 + 1ll * (r - l + 1);
//  return dc(qz(l, A), A.k, r - l + 1) - dc(qz(l, B), B.k, r - l + 1) + 1ll * (r - l + 1);
}
void de(Node A) {
    cout << A.k << " " << A.b << " " << A.l << " " << A.r << "\n";
}
int main() {
//  freopen("2.txt", "r", stdin);
    int n = read();
    for (int i = 1; i <= n; ++i) d[i] = read(), u[i] = read();
//  for (int i = 1; i <= n; ++i) u[i] = read();
//  double Mx = Slope(1, d[1], 2, u[2]);
//  for (int i = 3; i <= n; ++i) Mx = min(Mx, Slope(1, d[1], i, u[i]));
//  double Mn = Slope(1, u[1], 2, d[2]);
//  for (int i = 3; i <= n; ++i) Mn = max(Mn, Slope(1, u[1], i, d[i]));
//  int mx = floor(Mx), mn = ceil(Mn);
//  cout << Mx << " " << Mn << "\n";
//  if (Mn > Mx) { cout << 0; return 0; }
    int top = 0; s1[++top] = Node(0, u[1], -INF, INF); //de(s1[top]);
    for (int i = 2; i <= n; ++i) {
        Node now = Node(-(i - 1), u[i], -INF, INF);
        while (top) {
            double t = jiao(s1[top], now);
            if (t <= 1.0 * s1[top].l) now.l = s1[top].l, top --;
            else if (t > 1.0 * s1[top].l && t <= 1.0 * s1[top].r) {
                int p = ceil(t); s1[top].r = p - 1, now.l = p; break;
            }
            else break;
        }
//      de(s1[top]); de(now);
        s1[++top] = now;
    }
    int cnt1 = top;
    top = 0; s2[++top] = Node(0, d[1], -INF, INF); //de(s2[top]);
    int xl = -1;
    for (int i = 2; i <= n ; ++i) {
        Node now = Node(xl, d[i], -INF, INF); xl --;
        while (top) {
            double t = jiao(s2[top], now);
            if (t >= 1.0 * s2[top].r) now.r = s2[top].r, top --;
            else if (t < 1.0 * s2[top].r && t >= 1.0 * s2[top].l) {
                int p = floor(t); s2[top].l = p + 1, now.r = p; break;
            }
            else break;
        }
//      de(s2[top]); de(now);
        s2[++top] = now;
    }
    int cnt2 = top;
//  puts("");
//  for (int i = 1; i <= cnt1; ++i) de(s1[i]);puts("");
//  for (int i = 1; i <= cnt2; ++i) de(s2[i]);puts("");
    int mn = ceil(jiao(s1[1], s2[cnt2])); 
    int mx = floor(jiao(s1[cnt1], s2[1]));
    int last = mn, p1 = 1, p2 = cnt2;
    LL ans = 0;
    while (p1 <= cnt1 && p2 >= 1) {
        if (s1[p1].l > s1[p1].r) { p1 ++; continue ; }
        if (s2[p2].l > s2[p2].r) { p2 --; continue ; }
        if (s1[p1].r < mn) { p1 ++; continue ; }
        if (s2[p2].r < mn) { p2 --; continue ; }
        if (s1[p1].r <= s2[p2].r) {
            ans += Calc(last, min(mx, s1[p1].r), s1[p1], s2[p2]);
            last = s1[p1].r + 1;
            p1 ++;
        }
        else {
            ans += Calc(last, min(mx, s2[p2].r), s1[p1], s2[p2]);
            last = s2[p2].r + 1;
            p2 --;
        }
    }
//  while (p1 <= cnt1) {
//      ans += 
//  }
//  if (ans < 0) { cout << 0; return 0; }
    cout << ans;
    return 0;
}