Submission #639757

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
639757	2022-09-11T14:26:55 Z	maomao90	IOI Fever (JOI21_fever)	C++17	0 / 100	65 ms	125736 KB

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;
    }
    RREP (i, n - 1, 0) {
	xy[i].FI -= xy[0].FI;
	xy[i].SE -= xy[0].SE;
    }
    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;
	    }
	    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, -INF)) -
		    man[ax].begin();
		int e = upper_bound(ALL(man[ax]), iiii(d, h, INF, INF)) -
		    man[ax].begin() - 1;
		if (s <= e) {
		    segs[ax].rmn(s, e, mn.FI - 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;
	}
	cerr << res << '\n';
    }
    cout << ans << '\n';
    return 0;
}

Compilation message

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

0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	56 ms	125516 KB	Output is correct
2	Correct	60 ms	125552 KB	Output is correct
3	Correct	56 ms	125500 KB	Output is correct
4	Correct	65 ms	125580 KB	Output is correct
5	Correct	64 ms	125476 KB	Output is correct
6	Correct	58 ms	125460 KB	Output is correct
7	Correct	57 ms	125508 KB	Output is correct
8	Correct	57 ms	125516 KB	Output is correct
9	Correct	57 ms	125516 KB	Output is correct
10	Correct	58 ms	125556 KB	Output is correct
11	Correct	59 ms	125516 KB	Output is correct
12	Correct	57 ms	125464 KB	Output is correct
13	Correct	58 ms	125556 KB	Output is correct
14	Correct	57 ms	125600 KB	Output is correct
15	Correct	58 ms	125532 KB	Output is correct
16	Incorrect	60 ms	125496 KB	Output isn't correct
17	Halted	0 ms	0 KB	-

Subtask #2

0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	56 ms	125516 KB	Output is correct
2	Correct	60 ms	125552 KB	Output is correct
3	Correct	56 ms	125500 KB	Output is correct
4	Correct	65 ms	125580 KB	Output is correct
5	Correct	64 ms	125476 KB	Output is correct
6	Correct	58 ms	125460 KB	Output is correct
7	Correct	57 ms	125508 KB	Output is correct
8	Correct	57 ms	125516 KB	Output is correct
9	Correct	57 ms	125516 KB	Output is correct
10	Correct	58 ms	125556 KB	Output is correct
11	Correct	59 ms	125516 KB	Output is correct
12	Correct	57 ms	125464 KB	Output is correct
13	Correct	58 ms	125556 KB	Output is correct
14	Correct	57 ms	125600 KB	Output is correct
15	Correct	58 ms	125532 KB	Output is correct
16	Incorrect	60 ms	125496 KB	Output isn't correct
17	Halted	0 ms	0 KB	-

Subtask #3

0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	58 ms	125736 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #4

0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	56 ms	125516 KB	Output is correct
2	Correct	60 ms	125552 KB	Output is correct
3	Correct	56 ms	125500 KB	Output is correct
4	Correct	65 ms	125580 KB	Output is correct
5	Correct	64 ms	125476 KB	Output is correct
6	Correct	58 ms	125460 KB	Output is correct
7	Correct	57 ms	125508 KB	Output is correct
8	Correct	57 ms	125516 KB	Output is correct
9	Correct	57 ms	125516 KB	Output is correct
10	Correct	58 ms	125556 KB	Output is correct
11	Correct	59 ms	125516 KB	Output is correct
12	Correct	57 ms	125464 KB	Output is correct
13	Correct	58 ms	125556 KB	Output is correct
14	Correct	57 ms	125600 KB	Output is correct
15	Correct	58 ms	125532 KB	Output is correct
16	Incorrect	60 ms	125496 KB	Output isn't correct
17	Halted	0 ms	0 KB	-

Subtask #5

0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	56 ms	125516 KB	Output is correct
2	Correct	60 ms	125552 KB	Output is correct
3	Correct	56 ms	125500 KB	Output is correct
4	Correct	65 ms	125580 KB	Output is correct
5	Correct	64 ms	125476 KB	Output is correct
6	Correct	58 ms	125460 KB	Output is correct
7	Correct	57 ms	125508 KB	Output is correct
8	Correct	57 ms	125516 KB	Output is correct
9	Correct	57 ms	125516 KB	Output is correct
10	Correct	58 ms	125556 KB	Output is correct
11	Correct	59 ms	125516 KB	Output is correct
12	Correct	57 ms	125464 KB	Output is correct
13	Correct	58 ms	125556 KB	Output is correct
14	Correct	57 ms	125600 KB	Output is correct
15	Correct	58 ms	125532 KB	Output is correct
16	Incorrect	60 ms	125496 KB	Output isn't correct
17	Halted	0 ms	0 KB	-

Subtask #6

0 / 32.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	56 ms	125516 KB	Output is correct
2	Correct	60 ms	125552 KB	Output is correct
3	Correct	56 ms	125500 KB	Output is correct
4	Correct	65 ms	125580 KB	Output is correct
5	Correct	64 ms	125476 KB	Output is correct
6	Correct	58 ms	125460 KB	Output is correct
7	Correct	57 ms	125508 KB	Output is correct
8	Correct	57 ms	125516 KB	Output is correct
9	Correct	57 ms	125516 KB	Output is correct
10	Correct	58 ms	125556 KB	Output is correct
11	Correct	59 ms	125516 KB	Output is correct
12	Correct	57 ms	125464 KB	Output is correct
13	Correct	58 ms	125556 KB	Output is correct
14	Correct	57 ms	125600 KB	Output is correct
15	Correct	58 ms	125532 KB	Output is correct
16	Incorrect	60 ms	125496 KB	Output isn't correct
17	Halted	0 ms	0 KB	-

Subtask #7

0 / 31.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	56 ms	125516 KB	Output is correct
2	Correct	60 ms	125552 KB	Output is correct
3	Correct	56 ms	125500 KB	Output is correct
4	Correct	65 ms	125580 KB	Output is correct
5	Correct	64 ms	125476 KB	Output is correct
6	Correct	58 ms	125460 KB	Output is correct
7	Correct	57 ms	125508 KB	Output is correct
8	Correct	57 ms	125516 KB	Output is correct
9	Correct	57 ms	125516 KB	Output is correct
10	Correct	58 ms	125556 KB	Output is correct
11	Correct	59 ms	125516 KB	Output is correct
12	Correct	57 ms	125464 KB	Output is correct
13	Correct	58 ms	125556 KB	Output is correct
14	Correct	57 ms	125600 KB	Output is correct
15	Correct	58 ms	125532 KB	Output is correct
16	Incorrect	60 ms	125496 KB	Output isn't correct
17	Halted	0 ms	0 KB	-