Submission #639850

#	Time	Username	Problem	Language	Result	Execution time	Memory
639850		maomao90	IOI Fever (JOI21_fever)	C++17	100 / 100	3893 ms	144220 KiB

fever

// Hallelujah, praise the one who set me free
// Hallelujah, death has lost its grip on me
// You have broken every chain, There's salvation in your name
// Jesus Christ, my living hope
#include <bits/stdc++.h>
using namespace std;
 
#define REP(i, s, e) for (int i = (s); i < (e); i++)
#define RREP(i, s, e) for (int i = (s); i >= (e); i--)
template <class T>
inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;}
typedef long long ll;
typedef long double ld;
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> iii;
typedef tuple<int, int, int, int> iiii;
#define ALL(_a) _a.begin(), _a.end()
#define SZ(_a) (int) _a.size()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
typedef vector<iii> viii;
 
#ifndef DEBUG
#define cerr if (0) cerr
#endif
 
const int INF = 2000000005;
const ll LINF = 1000000000000000005ll;
const int MAXN = 100005;

int n;
ii xy[MAXN];
int rnk[8][MAXN];
vector<iiii> man[8];
int ans;

struct SegTree {
    pll mn[MAXN * 4], mnb[MAXN * 4];
    ll lz[MAXN * 4];
    SegTree() {
	REP (i, 0, MAXN * 4) {
	    lz[i] = 4 * LINF;
	}
    }
#define MLR int mid = lo + hi >> 1, lc = u << 1, rc = u << 1 ^ 1
    void propo(int u, int lo, int hi) {
	if (lo == hi || lz[u] == 4 * LINF) {
	    return;
	}
	MLR;
	if (mnto(mn[lc].FI, mnb[lc].FI + lz[u])) {
	    mn[lc].SE = mnb[lc].SE;
	}
	if (mnto(mn[rc].FI, mnb[rc].FI + lz[u])) {
	    mn[rc].SE = mnb[rc].SE;
	}
	mnto(lz[lc], lz[u]);
	mnto(lz[rc], lz[u]);
	lz[u] = 4 * LINF;
    }
    void upd(int p, pll v, int u = 1, int lo = 0, int hi = n - 1) {
	if (lo == hi) {
	    mn[u] = {v.FI + v.SE, lo};
	    mnb[u] = {v.SE, lo};
	    return;
	}
	propo(u, lo, hi);
	MLR;
	if (p <= mid) {
	    upd(p, v, lc, lo, mid);
	} else {
	    upd(p, v, rc, mid + 1, hi);
	}
	mn[u] = min(mn[lc], mn[rc]);
	mnb[u] = min(mnb[lc], mnb[rc]);
    }
    void rmn(int s, int e, ll v, int u = 1, int lo = 0, int hi = n - 1) {
	if (lo >= s && hi <= e) {
	    if (mnto(mn[u].FI, mnb[u].FI + v)) {
		mn[u].SE = mnb[u].SE;
	    }
	    mnto(lz[u], v);
	    return;
	}
	propo(u, lo, hi);
	MLR;
	if (s <= mid) {
	    rmn(s, e, v, lc, lo, mid);
	}
	if (e > mid) {
	    rmn(s, e, v, rc, mid + 1, hi);
	}
	mn[u] = min(mn[lc], mn[rc]);
	mnb[u] = min(mnb[lc], mnb[rc]);
    }
} segs[8];

int main() {
#ifndef DEBUG
    ios::sync_with_stdio(0), cin.tie(0);
#endif
    cin >> n;
    REP (i, 0, n) {
	cin >> xy[i].FI >> xy[i].SE;
    }
    auto [tx, ty] = xy[0];
    RREP (i, n - 1, 0) {
	xy[i].FI -= tx;
	xy[i].SE -= ty;
    }
    REP (z, 0, 4) {
	REP (k, 0, 8) {
	    man[k].clear();
	    REP (i, 0, 4 * MAXN) {
		segs[k].lz[i] = 4 * LINF;
	    }
	}
	REP (i, 0, n) {
	    auto [x, y] = xy[i];
	    int nx = x - y, ny = x + y;
	    int d = -1;
	    if (ny > 0 && nx > 0) {
		// move towards WEST
		d = 2;
	    } else if (nx <= 0 && ny <= 0) {
		// move towards EAST
		d = 0;
	    } else if (nx <= 0 && ny > 0) {
		// move towards SOUTH
		d = 3;
	    } else if (ny <= 0 && nx > 0) {
		// move towards NORTH
		d = 1;
	    }
	    assert(d != -1);
	    man[0].pb({d, y, x, i});
	    man[1].pb({d, x, y, i});
	    man[2].pb({d, ny, nx, i});
	    man[3].pb({d, nx, ny, i});
	    man[4].pb({d, y, -x, i});
	    man[5].pb({d, x, -y, i});
	    man[6].pb({d, ny, -nx, i});
	    man[7].pb({d, nx, -ny, i});
	}
	REP (k, 0, 8) {
	    sort(ALL(man[k]));
	    REP (i, 0, n) {
		auto [d, h, p, id] = man[k][i];
		rnk[k][id] = i;
	    }
	}
	REP (k, 0, 8) {
	    REP (i, 0, n) {
		segs[k].upd(i, {4 * LINF, get<2>(man[k][i])});
	    }
	}
	segs[0].rmn(rnk[0][0], rnk[0][0], 0);
	int res = 0;
	while (1) {
	    pll mn = {LINF, LINF};
	    REP (k, 0, 8) {
		if (mnto(mn, segs[k].mn[1])) {
		    mn.SE = get<3>(man[k][mn.SE]);
		}
	    }
	    if (mn.FI == LINF) {
		break;
	    }
	    cerr << mn.FI << ' ' << mn.SE << ' ' << xy[mn.SE].FI << ' ' << xy[mn.SE].SE << '\n';
	    res++;
	    REP (k, 0, 8) {
		segs[k].upd(rnk[k][mn.SE], {4 * LINF, 4 * LINF});
	    }
	    auto doUpd = [&] (int ax, int d) {
		auto [_, h, p, __] = man[ax][rnk[ax][mn.SE]];
		int s = lower_bound(ALL(man[ax]), iiii(d, h, p + mn.FI, -INF)) -
		    man[ax].begin();
		int e = upper_bound(ALL(man[ax]), iiii(d, h, INF, INF)) -
		    man[ax].begin() - 1;
		cerr << ' ' << ax << ' ' << d << ' ' << s << ' ' << e << '\n';
		if (s <= e) {
		    segs[ax].rmn(s, e, -p);
		}
	    };
	    int d = get<0>(man[0][rnk[0][mn.SE]]);
	    if (d == 0) {
		doUpd(2, 1);
		doUpd(0, 2);
		doUpd(3, 3);
	    } else if (d == 1) {
		doUpd(3, 2);
		doUpd(1, 3);
		doUpd(6, 0);
	    } else if (d == 2) {
		doUpd(6, 3);
		doUpd(4, 0);
		doUpd(7, 1);
	    } else if (d == 3) {
		doUpd(7, 0);
		doUpd(5, 1);
		doUpd(2, 2);
	    } else {
		assert(0);
	    }
	}
	mxto(ans, res);
	REP (i, 0, n) {
	    auto [x, y] = xy[i];
	    xy[i].FI = -y;
	    xy[i].SE = x;
	}
    }
    cout << ans << '\n';
    return 0;
}

Compilation message (stderr)

fever.cpp: In member function 'void SegTree::propo(int, int, int)':
fever.cpp:52:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   52 | #define MLR int mid = lo + hi >> 1, lc = u << 1, rc = u << 1 ^ 1
      |                       ~~~^~~~
fever.cpp:57:2: note: in expansion of macro 'MLR'
   57 |  MLR;
      |  ^~~
fever.cpp:52:17: warning: unused variable 'mid' [-Wunused-variable]
   52 | #define MLR int mid = lo + hi >> 1, lc = u << 1, rc = u << 1 ^ 1
      |                 ^~~
fever.cpp:57:2: note: in expansion of macro 'MLR'
   57 |  MLR;
      |  ^~~
fever.cpp: In member function 'void SegTree::upd(int, pll, int, int, int)':
fever.cpp:52:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   52 | #define MLR int mid = lo + hi >> 1, lc = u << 1, rc = u << 1 ^ 1
      |                       ~~~^~~~
fever.cpp:75:2: note: in expansion of macro 'MLR'
   75 |  MLR;
      |  ^~~
fever.cpp: In member function 'void SegTree::rmn(int, int, ll, int, int, int)':
fever.cpp:52:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   52 | #define MLR int mid = lo + hi >> 1, lc = u << 1, rc = u << 1 ^ 1
      |                       ~~~^~~~
fever.cpp:93:2: note: in expansion of macro 'MLR'
   93 |  MLR;
      |  ^~~

• Subtask 1: 5 / 5
• Subtask 2: 8 / 8
• Subtask 3: 6 / 6
• Subtask 4: 6 / 6
• Subtask 5: 12 / 12
• Subtask 6: 32 / 32
• Subtask 7: 31 / 31