oj.uz

Submission #639758

# Submission time Handle Problem Language Result Execution time Memory
639758 2022-09-11T14:35:37 Z maomao90 IOI Fever (JOI21_fever) C++17
6 / 100
 68 ms 125724 KB 
// 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;
	    }
	    cerr << mn.FI << ' ' << mn.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;
		if (s <= e) {
		    cerr << ' ' << ax << ' ' << s << ' ' << e << '\n';
		    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) {
		cerr << "HI\n";
		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 57 ms 125528 KB Output is correct
2 Correct 58 ms 125468 KB Output is correct
3 Correct 57 ms 125460 KB Output is correct
4 Correct 59 ms 125556 KB Output is correct
5 Correct 59 ms 125608 KB Output is correct
6 Correct 63 ms 125592 KB Output is correct
7 Correct 58 ms 125588 KB Output is correct
8 Correct 58 ms 125580 KB Output is correct
9 Correct 59 ms 125512 KB Output is correct
10 Correct 58 ms 125516 KB Output is correct
11 Correct 59 ms 125572 KB Output is correct
12 Correct 65 ms 125688 KB Output is correct
13 Correct 59 ms 125516 KB Output is correct
14 Correct 60 ms 125516 KB Output is correct
15 Correct 59 ms 125588 KB Output is correct
16 Correct 59 ms 125552 KB Output is correct
17 Correct 60 ms 125544 KB Output is correct
18 Correct 59 ms 125528 KB Output is correct
19 Correct 60 ms 125596 KB Output is correct
20 Correct 60 ms 125580 KB Output is correct
21 Correct 63 ms 125528 KB Output is correct
22 Correct 59 ms 125516 KB Output is correct
23 Correct 59 ms 125552 KB Output is correct
24 Correct 59 ms 125564 KB Output is correct
25 Correct 68 ms 125568 KB Output is correct
26 Correct 59 ms 125724 KB Output is correct
27 Correct 59 ms 125552 KB Output is correct
28 Correct 59 ms 125536 KB Output is correct
29 Incorrect 59 ms 125516 KB Output isn't correct
30 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 125528 KB Output is correct
2 Correct 58 ms 125468 KB Output is correct
3 Correct 57 ms 125460 KB Output is correct
4 Correct 59 ms 125556 KB Output is correct
5 Correct 59 ms 125608 KB Output is correct
6 Correct 63 ms 125592 KB Output is correct
7 Correct 58 ms 125588 KB Output is correct
8 Correct 58 ms 125580 KB Output is correct
9 Correct 59 ms 125512 KB Output is correct
10 Correct 58 ms 125516 KB Output is correct
11 Correct 59 ms 125572 KB Output is correct
12 Correct 65 ms 125688 KB Output is correct
13 Correct 59 ms 125516 KB Output is correct
14 Correct 60 ms 125516 KB Output is correct
15 Correct 59 ms 125588 KB Output is correct
16 Correct 59 ms 125552 KB Output is correct
17 Correct 60 ms 125544 KB Output is correct
18 Correct 59 ms 125528 KB Output is correct
19 Correct 60 ms 125596 KB Output is correct
20 Correct 60 ms 125580 KB Output is correct
21 Correct 63 ms 125528 KB Output is correct
22 Correct 59 ms 125516 KB Output is correct
23 Correct 59 ms 125552 KB Output is correct
24 Correct 59 ms 125564 KB Output is correct
25 Correct 68 ms 125568 KB Output is correct
26 Correct 59 ms 125724 KB Output is correct
27 Correct 59 ms 125552 KB Output is correct
28 Correct 59 ms 125536 KB Output is correct
29 Incorrect 59 ms 125516 KB Output isn't correct
30 Halted 0 ms 0 KB -

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 125632 KB Output is correct
2 Correct 62 ms 125624 KB Output is correct
3 Correct 60 ms 125552 KB Output is correct
4 Correct 65 ms 125640 KB Output is correct
5 Correct 60 ms 125560 KB Output is correct
6 Correct 60 ms 125516 KB Output is correct
7 Correct 59 ms 125524 KB Output is correct
8 Correct 61 ms 125516 KB Output is correct

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 125528 KB Output is correct
2 Correct 58 ms 125468 KB Output is correct
3 Correct 57 ms 125460 KB Output is correct
4 Correct 59 ms 125556 KB Output is correct
5 Correct 59 ms 125608 KB Output is correct
6 Correct 63 ms 125592 KB Output is correct
7 Correct 58 ms 125588 KB Output is correct
8 Correct 58 ms 125580 KB Output is correct
9 Correct 59 ms 125512 KB Output is correct
10 Correct 58 ms 125516 KB Output is correct
11 Correct 59 ms 125572 KB Output is correct
12 Correct 65 ms 125688 KB Output is correct
13 Correct 59 ms 125516 KB Output is correct
14 Correct 60 ms 125516 KB Output is correct
15 Correct 59 ms 125588 KB Output is correct
16 Correct 59 ms 125552 KB Output is correct
17 Correct 60 ms 125544 KB Output is correct
18 Correct 59 ms 125528 KB Output is correct
19 Correct 60 ms 125596 KB Output is correct
20 Correct 60 ms 125580 KB Output is correct
21 Correct 63 ms 125528 KB Output is correct
22 Correct 59 ms 125516 KB Output is correct
23 Correct 59 ms 125552 KB Output is correct
24 Correct 59 ms 125564 KB Output is correct
25 Correct 68 ms 125568 KB Output is correct
26 Correct 59 ms 125724 KB Output is correct
27 Correct 59 ms 125552 KB Output is correct
28 Correct 59 ms 125536 KB Output is correct
29 Incorrect 59 ms 125516 KB Output isn't correct
30 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 125528 KB Output is correct
2 Correct 58 ms 125468 KB Output is correct
3 Correct 57 ms 125460 KB Output is correct
4 Correct 59 ms 125556 KB Output is correct
5 Correct 59 ms 125608 KB Output is correct
6 Correct 63 ms 125592 KB Output is correct
7 Correct 58 ms 125588 KB Output is correct
8 Correct 58 ms 125580 KB Output is correct
9 Correct 59 ms 125512 KB Output is correct
10 Correct 58 ms 125516 KB Output is correct
11 Correct 59 ms 125572 KB Output is correct
12 Correct 65 ms 125688 KB Output is correct
13 Correct 59 ms 125516 KB Output is correct
14 Correct 60 ms 125516 KB Output is correct
15 Correct 59 ms 125588 KB Output is correct
16 Correct 59 ms 125552 KB Output is correct
17 Correct 60 ms 125544 KB Output is correct
18 Correct 59 ms 125528 KB Output is correct
19 Correct 60 ms 125596 KB Output is correct
20 Correct 60 ms 125580 KB Output is correct
21 Correct 63 ms 125528 KB Output is correct
22 Correct 59 ms 125516 KB Output is correct
23 Correct 59 ms 125552 KB Output is correct
24 Correct 59 ms 125564 KB Output is correct
25 Correct 68 ms 125568 KB Output is correct
26 Correct 59 ms 125724 KB Output is correct
27 Correct 59 ms 125552 KB Output is correct
28 Correct 59 ms 125536 KB Output is correct
29 Incorrect 59 ms 125516 KB Output isn't correct
30 Halted 0 ms 0 KB -

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 125528 KB Output is correct
2 Correct 58 ms 125468 KB Output is correct
3 Correct 57 ms 125460 KB Output is correct
4 Correct 59 ms 125556 KB Output is correct
5 Correct 59 ms 125608 KB Output is correct
6 Correct 63 ms 125592 KB Output is correct
7 Correct 58 ms 125588 KB Output is correct
8 Correct 58 ms 125580 KB Output is correct
9 Correct 59 ms 125512 KB Output is correct
10 Correct 58 ms 125516 KB Output is correct
11 Correct 59 ms 125572 KB Output is correct
12 Correct 65 ms 125688 KB Output is correct
13 Correct 59 ms 125516 KB Output is correct
14 Correct 60 ms 125516 KB Output is correct
15 Correct 59 ms 125588 KB Output is correct
16 Correct 59 ms 125552 KB Output is correct
17 Correct 60 ms 125544 KB Output is correct
18 Correct 59 ms 125528 KB Output is correct
19 Correct 60 ms 125596 KB Output is correct
20 Correct 60 ms 125580 KB Output is correct
21 Correct 63 ms 125528 KB Output is correct
22 Correct 59 ms 125516 KB Output is correct
23 Correct 59 ms 125552 KB Output is correct
24 Correct 59 ms 125564 KB Output is correct
25 Correct 68 ms 125568 KB Output is correct
26 Correct 59 ms 125724 KB Output is correct
27 Correct 59 ms 125552 KB Output is correct
28 Correct 59 ms 125536 KB Output is correct
29 Incorrect 59 ms 125516 KB Output isn't correct
30 Halted 0 ms 0 KB -

Subtask #7
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 125528 KB Output is correct
2 Correct 58 ms 125468 KB Output is correct
3 Correct 57 ms 125460 KB Output is correct
4 Correct 59 ms 125556 KB Output is correct
5 Correct 59 ms 125608 KB Output is correct
6 Correct 63 ms 125592 KB Output is correct
7 Correct 58 ms 125588 KB Output is correct
8 Correct 58 ms 125580 KB Output is correct
9 Correct 59 ms 125512 KB Output is correct
10 Correct 58 ms 125516 KB Output is correct
11 Correct 59 ms 125572 KB Output is correct
12 Correct 65 ms 125688 KB Output is correct
13 Correct 59 ms 125516 KB Output is correct
14 Correct 60 ms 125516 KB Output is correct
15 Correct 59 ms 125588 KB Output is correct
16 Correct 59 ms 125552 KB Output is correct
17 Correct 60 ms 125544 KB Output is correct
18 Correct 59 ms 125528 KB Output is correct
19 Correct 60 ms 125596 KB Output is correct
20 Correct 60 ms 125580 KB Output is correct
21 Correct 63 ms 125528 KB Output is correct
22 Correct 59 ms 125516 KB Output is correct
23 Correct 59 ms 125552 KB Output is correct
24 Correct 59 ms 125564 KB Output is correct
25 Correct 68 ms 125568 KB Output is correct
26 Correct 59 ms 125724 KB Output is correct
27 Correct 59 ms 125552 KB Output is correct
28 Correct 59 ms 125536 KB Output is correct
29 Incorrect 59 ms 125516 KB Output isn't correct
30 Halted 0 ms 0 KB -