Submission #74227713

---

Source Code Expand

#include <algorithm>
#include <cstdint>
#include <iostream>
#include <set>
#include <utility>
using namespace std;
typedef long long ll;
typedef pair<int,int> pp;
typedef pair<ll,ll> pll;
void cppio(){ ios_base::sync_with_stdio(0); cin.tie(0); }
template<typename T,typename U>
istream& operator>>(istream& i, pair<T,U>& p) { i >> p.first >> p.second; return i; }
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define eb emplace_back
#define x first
#define y second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define sz(x) (int)(x).size()
#define XY(t) t.x, t.y
#define dbg if (0)

const int maxn = int(5e5) + 10;

ll f_axis_segment(int l, int r) { // l <= r
    if (l < 0 && r < 0) return f_axis_segment(-r, -l);
    if (l < 0) return f_axis_segment(0, -l) + f_axis_segment(0, r) - 1;
    if (l > 0) return f_axis_segment(0, r) - f_axis_segment(0, l-1);
    // now l == 0 <= r
    return 1 + r/2;
}

ll f(int l, int r, int d, int u) { // l <= r, d <= u
    if (d < 0 && u < 0) return f(l, r, -u, -d);
    if (d < 0) return f(l, r, 0, -d) + f(l, r, 0, u) - f_axis_segment(l, r);
    if (d > 0) return f(l, r, 0, u) - f(l, r, 0, d-1);
    // now d == 0 <= u

    if (l < 0 && r < 0) return f(-r, -l, d, u);
    if (l < 0) return f(0, -l, d, u) + f(0, r, d, u) - f_axis_segment(d, u);
    if (l > 0) return f(0, r, d, u) - f(0, l-1, d, u);
    // now l == 0 <= r

    // now r and u matters only.
    if (u > r) swap(r, u);
    // now u <= r.

    if (r%2 == 1) --r;
    if (u%2 == 1) return f(l, r, d, u-1) + f_axis_segment(u+1, r);

/*
square part:
u=0. y=1
u=2. y=6
u=4. y=15
u=6. y=28

 4a + 2b = 5
16a + 4b = 14
36a + 6b = 27

a = 1/2
b = 3/2
*/
    ll square_part = u*1ll*u/2 + u*3/2 + 1;
    ll line_part = f_axis_segment(u+2, r) * (u+1);

    return square_part + line_part;
}

int main()
{
    cppio();

    int l, r, d, u; cin >> l >> r >> d >> u;

    cout << f(l,r,d,u) << '\n';

	return 0;
}

Submission Info

Judge Result