Submission #639756

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
639756	2022-09-11T14:02:13 Z	maomao90	IOI Fever (JOI21_fever)	C++17	0 / 100	59 ms	125588 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] = 2 * 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] == 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] = 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;
    }
    // TODO: Change 1 to 4
    REP (z, 0, 4) {
	REP (k, 0, 8) {
	    man[k].clear();
	}
	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, {2 * LINF, get<2>(man[k][i])});
	    }
	}
	segs[0].rmn(rnk[0][0], rnk[0][0], 0);
	int res = 0;
	// TODO: Change to while loop
	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], {2 * LINF, 2 * 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;
	}
    }
    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	47 ms	125524 KB	Output is correct
2	Correct	48 ms	125552 KB	Output is correct
3	Correct	50 ms	125588 KB	Output is correct
4	Correct	46 ms	125516 KB	Output is correct
5	Correct	46 ms	125508 KB	Output is correct
6	Correct	56 ms	125568 KB	Output is correct
7	Correct	48 ms	125516 KB	Output is correct
8	Correct	57 ms	125560 KB	Output is correct
9	Correct	48 ms	125552 KB	Output is correct
10	Correct	48 ms	125572 KB	Output is correct
11	Correct	52 ms	125564 KB	Output is correct
12	Correct	48 ms	125580 KB	Output is correct
13	Correct	58 ms	125580 KB	Output is correct
14	Correct	59 ms	125468 KB	Output is correct
15	Correct	47 ms	125504 KB	Output is correct
16	Incorrect	48 ms	125580 KB	Output isn't correct
17	Halted	0 ms	0 KB	-

Subtask #2

0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	47 ms	125524 KB	Output is correct
2	Correct	48 ms	125552 KB	Output is correct
3	Correct	50 ms	125588 KB	Output is correct
4	Correct	46 ms	125516 KB	Output is correct
5	Correct	46 ms	125508 KB	Output is correct
6	Correct	56 ms	125568 KB	Output is correct
7	Correct	48 ms	125516 KB	Output is correct
8	Correct	57 ms	125560 KB	Output is correct
9	Correct	48 ms	125552 KB	Output is correct
10	Correct	48 ms	125572 KB	Output is correct
11	Correct	52 ms	125564 KB	Output is correct
12	Correct	48 ms	125580 KB	Output is correct
13	Correct	58 ms	125580 KB	Output is correct
14	Correct	59 ms	125468 KB	Output is correct
15	Correct	47 ms	125504 KB	Output is correct
16	Incorrect	48 ms	125580 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	125524 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #4

0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	47 ms	125524 KB	Output is correct
2	Correct	48 ms	125552 KB	Output is correct
3	Correct	50 ms	125588 KB	Output is correct
4	Correct	46 ms	125516 KB	Output is correct
5	Correct	46 ms	125508 KB	Output is correct
6	Correct	56 ms	125568 KB	Output is correct
7	Correct	48 ms	125516 KB	Output is correct
8	Correct	57 ms	125560 KB	Output is correct
9	Correct	48 ms	125552 KB	Output is correct
10	Correct	48 ms	125572 KB	Output is correct
11	Correct	52 ms	125564 KB	Output is correct
12	Correct	48 ms	125580 KB	Output is correct
13	Correct	58 ms	125580 KB	Output is correct
14	Correct	59 ms	125468 KB	Output is correct
15	Correct	47 ms	125504 KB	Output is correct
16	Incorrect	48 ms	125580 KB	Output isn't correct
17	Halted	0 ms	0 KB	-

Subtask #5

0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	47 ms	125524 KB	Output is correct
2	Correct	48 ms	125552 KB	Output is correct
3	Correct	50 ms	125588 KB	Output is correct
4	Correct	46 ms	125516 KB	Output is correct
5	Correct	46 ms	125508 KB	Output is correct
6	Correct	56 ms	125568 KB	Output is correct
7	Correct	48 ms	125516 KB	Output is correct
8	Correct	57 ms	125560 KB	Output is correct
9	Correct	48 ms	125552 KB	Output is correct
10	Correct	48 ms	125572 KB	Output is correct
11	Correct	52 ms	125564 KB	Output is correct
12	Correct	48 ms	125580 KB	Output is correct
13	Correct	58 ms	125580 KB	Output is correct
14	Correct	59 ms	125468 KB	Output is correct
15	Correct	47 ms	125504 KB	Output is correct
16	Incorrect	48 ms	125580 KB	Output isn't correct
17	Halted	0 ms	0 KB	-

Subtask #6

0 / 32.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	47 ms	125524 KB	Output is correct
2	Correct	48 ms	125552 KB	Output is correct
3	Correct	50 ms	125588 KB	Output is correct
4	Correct	46 ms	125516 KB	Output is correct
5	Correct	46 ms	125508 KB	Output is correct
6	Correct	56 ms	125568 KB	Output is correct
7	Correct	48 ms	125516 KB	Output is correct
8	Correct	57 ms	125560 KB	Output is correct
9	Correct	48 ms	125552 KB	Output is correct
10	Correct	48 ms	125572 KB	Output is correct
11	Correct	52 ms	125564 KB	Output is correct
12	Correct	48 ms	125580 KB	Output is correct
13	Correct	58 ms	125580 KB	Output is correct
14	Correct	59 ms	125468 KB	Output is correct
15	Correct	47 ms	125504 KB	Output is correct
16	Incorrect	48 ms	125580 KB	Output isn't correct
17	Halted	0 ms	0 KB	-

Subtask #7

0 / 31.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	47 ms	125524 KB	Output is correct
2	Correct	48 ms	125552 KB	Output is correct
3	Correct	50 ms	125588 KB	Output is correct
4	Correct	46 ms	125516 KB	Output is correct
5	Correct	46 ms	125508 KB	Output is correct
6	Correct	56 ms	125568 KB	Output is correct
7	Correct	48 ms	125516 KB	Output is correct
8	Correct	57 ms	125560 KB	Output is correct
9	Correct	48 ms	125552 KB	Output is correct
10	Correct	48 ms	125572 KB	Output is correct
11	Correct	52 ms	125564 KB	Output is correct
12	Correct	48 ms	125580 KB	Output is correct
13	Correct	58 ms	125580 KB	Output is correct
14	Correct	59 ms	125468 KB	Output is correct
15	Correct	47 ms	125504 KB	Output is correct
16	Incorrect	48 ms	125580 KB	Output isn't correct
17	Halted	0 ms	0 KB	-