oj.uz

Submission #639759

# Submission time Handle Problem Language Result Execution time Memory
639759 2022-09-11T14:37:41 Z maomao90 IOI Fever (JOI21_fever) C++17
6 / 100
 76 ms 125644 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;
    }
    REP (z, 0, 4) {
	auto [tx, ty] = xy[0];
	RREP (i, n - 1, 0) {
	    xy[i].FI -= tx;
	    xy[i].SE -= ty;
	}
	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);
	RREP (i, n - 1, 0) {
	    xy[i].FI += tx;
	    xy[i].SE += ty;
	}
	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 62 ms 125588 KB Output is correct
2 Correct 69 ms 125484 KB Output is correct
3 Correct 75 ms 125552 KB Output is correct
4 Correct 65 ms 125472 KB Output is correct
5 Correct 65 ms 125540 KB Output is correct
6 Correct 68 ms 125512 KB Output is correct
7 Correct 76 ms 125584 KB Output is correct
8 Correct 69 ms 125644 KB Output is correct
9 Correct 65 ms 125496 KB Output is correct
10 Correct 69 ms 125540 KB Output is correct
11 Correct 66 ms 125516 KB Output is correct
12 Correct 66 ms 125524 KB Output is correct
13 Correct 61 ms 125564 KB Output is correct
14 Correct 61 ms 125556 KB Output is correct
15 Correct 60 ms 125552 KB Output is correct
16 Correct 67 ms 125564 KB Output is correct
17 Correct 59 ms 125516 KB Output is correct
18 Correct 72 ms 125576 KB Output is correct
19 Correct 62 ms 125592 KB Output is correct
20 Correct 60 ms 125552 KB Output is correct
21 Correct 59 ms 125536 KB Output is correct
22 Correct 65 ms 125592 KB Output is correct
23 Correct 61 ms 125588 KB Output is correct
24 Correct 60 ms 125472 KB Output is correct
25 Correct 69 ms 125476 KB Output is correct
26 Correct 65 ms 125516 KB Output is correct
27 Correct 60 ms 125516 KB Output is correct
28 Correct 63 ms 125592 KB Output is correct
29 Incorrect 60 ms 125564 KB Output isn't correct
30 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 125588 KB Output is correct
2 Correct 69 ms 125484 KB Output is correct
3 Correct 75 ms 125552 KB Output is correct
4 Correct 65 ms 125472 KB Output is correct
5 Correct 65 ms 125540 KB Output is correct
6 Correct 68 ms 125512 KB Output is correct
7 Correct 76 ms 125584 KB Output is correct
8 Correct 69 ms 125644 KB Output is correct
9 Correct 65 ms 125496 KB Output is correct
10 Correct 69 ms 125540 KB Output is correct
11 Correct 66 ms 125516 KB Output is correct
12 Correct 66 ms 125524 KB Output is correct
13 Correct 61 ms 125564 KB Output is correct
14 Correct 61 ms 125556 KB Output is correct
15 Correct 60 ms 125552 KB Output is correct
16 Correct 67 ms 125564 KB Output is correct
17 Correct 59 ms 125516 KB Output is correct
18 Correct 72 ms 125576 KB Output is correct
19 Correct 62 ms 125592 KB Output is correct
20 Correct 60 ms 125552 KB Output is correct
21 Correct 59 ms 125536 KB Output is correct
22 Correct 65 ms 125592 KB Output is correct
23 Correct 61 ms 125588 KB Output is correct
24 Correct 60 ms 125472 KB Output is correct
25 Correct 69 ms 125476 KB Output is correct
26 Correct 65 ms 125516 KB Output is correct
27 Correct 60 ms 125516 KB Output is correct
28 Correct 63 ms 125592 KB Output is correct
29 Incorrect 60 ms 125564 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 63 ms 125544 KB Output is correct
2 Correct 67 ms 125556 KB Output is correct
3 Correct 63 ms 125588 KB Output is correct
4 Correct 59 ms 125632 KB Output is correct
5 Correct 62 ms 125644 KB Output is correct
6 Correct 64 ms 125632 KB Output is correct
7 Correct 64 ms 125632 KB Output is correct
8 Correct 61 ms 125576 KB Output is correct

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 125588 KB Output is correct
2 Correct 69 ms 125484 KB Output is correct
3 Correct 75 ms 125552 KB Output is correct
4 Correct 65 ms 125472 KB Output is correct
5 Correct 65 ms 125540 KB Output is correct
6 Correct 68 ms 125512 KB Output is correct
7 Correct 76 ms 125584 KB Output is correct
8 Correct 69 ms 125644 KB Output is correct
9 Correct 65 ms 125496 KB Output is correct
10 Correct 69 ms 125540 KB Output is correct
11 Correct 66 ms 125516 KB Output is correct
12 Correct 66 ms 125524 KB Output is correct
13 Correct 61 ms 125564 KB Output is correct
14 Correct 61 ms 125556 KB Output is correct
15 Correct 60 ms 125552 KB Output is correct
16 Correct 67 ms 125564 KB Output is correct
17 Correct 59 ms 125516 KB Output is correct
18 Correct 72 ms 125576 KB Output is correct
19 Correct 62 ms 125592 KB Output is correct
20 Correct 60 ms 125552 KB Output is correct
21 Correct 59 ms 125536 KB Output is correct
22 Correct 65 ms 125592 KB Output is correct
23 Correct 61 ms 125588 KB Output is correct
24 Correct 60 ms 125472 KB Output is correct
25 Correct 69 ms 125476 KB Output is correct
26 Correct 65 ms 125516 KB Output is correct
27 Correct 60 ms 125516 KB Output is correct
28 Correct 63 ms 125592 KB Output is correct
29 Incorrect 60 ms 125564 KB Output isn't correct
30 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 125588 KB Output is correct
2 Correct 69 ms 125484 KB Output is correct
3 Correct 75 ms 125552 KB Output is correct
4 Correct 65 ms 125472 KB Output is correct
5 Correct 65 ms 125540 KB Output is correct
6 Correct 68 ms 125512 KB Output is correct
7 Correct 76 ms 125584 KB Output is correct
8 Correct 69 ms 125644 KB Output is correct
9 Correct 65 ms 125496 KB Output is correct
10 Correct 69 ms 125540 KB Output is correct
11 Correct 66 ms 125516 KB Output is correct
12 Correct 66 ms 125524 KB Output is correct
13 Correct 61 ms 125564 KB Output is correct
14 Correct 61 ms 125556 KB Output is correct
15 Correct 60 ms 125552 KB Output is correct
16 Correct 67 ms 125564 KB Output is correct
17 Correct 59 ms 125516 KB Output is correct
18 Correct 72 ms 125576 KB Output is correct
19 Correct 62 ms 125592 KB Output is correct
20 Correct 60 ms 125552 KB Output is correct
21 Correct 59 ms 125536 KB Output is correct
22 Correct 65 ms 125592 KB Output is correct
23 Correct 61 ms 125588 KB Output is correct
24 Correct 60 ms 125472 KB Output is correct
25 Correct 69 ms 125476 KB Output is correct
26 Correct 65 ms 125516 KB Output is correct
27 Correct 60 ms 125516 KB Output is correct
28 Correct 63 ms 125592 KB Output is correct
29 Incorrect 60 ms 125564 KB Output isn't correct
30 Halted 0 ms 0 KB -

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 125588 KB Output is correct
2 Correct 69 ms 125484 KB Output is correct
3 Correct 75 ms 125552 KB Output is correct
4 Correct 65 ms 125472 KB Output is correct
5 Correct 65 ms 125540 KB Output is correct
6 Correct 68 ms 125512 KB Output is correct
7 Correct 76 ms 125584 KB Output is correct
8 Correct 69 ms 125644 KB Output is correct
9 Correct 65 ms 125496 KB Output is correct
10 Correct 69 ms 125540 KB Output is correct
11 Correct 66 ms 125516 KB Output is correct
12 Correct 66 ms 125524 KB Output is correct
13 Correct 61 ms 125564 KB Output is correct
14 Correct 61 ms 125556 KB Output is correct
15 Correct 60 ms 125552 KB Output is correct
16 Correct 67 ms 125564 KB Output is correct
17 Correct 59 ms 125516 KB Output is correct
18 Correct 72 ms 125576 KB Output is correct
19 Correct 62 ms 125592 KB Output is correct
20 Correct 60 ms 125552 KB Output is correct
21 Correct 59 ms 125536 KB Output is correct
22 Correct 65 ms 125592 KB Output is correct
23 Correct 61 ms 125588 KB Output is correct
24 Correct 60 ms 125472 KB Output is correct
25 Correct 69 ms 125476 KB Output is correct
26 Correct 65 ms 125516 KB Output is correct
27 Correct 60 ms 125516 KB Output is correct
28 Correct 63 ms 125592 KB Output is correct
29 Incorrect 60 ms 125564 KB Output isn't correct
30 Halted 0 ms 0 KB -

Subtask #7
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 125588 KB Output is correct
2 Correct 69 ms 125484 KB Output is correct
3 Correct 75 ms 125552 KB Output is correct
4 Correct 65 ms 125472 KB Output is correct
5 Correct 65 ms 125540 KB Output is correct
6 Correct 68 ms 125512 KB Output is correct
7 Correct 76 ms 125584 KB Output is correct
8 Correct 69 ms 125644 KB Output is correct
9 Correct 65 ms 125496 KB Output is correct
10 Correct 69 ms 125540 KB Output is correct
11 Correct 66 ms 125516 KB Output is correct
12 Correct 66 ms 125524 KB Output is correct
13 Correct 61 ms 125564 KB Output is correct
14 Correct 61 ms 125556 KB Output is correct
15 Correct 60 ms 125552 KB Output is correct
16 Correct 67 ms 125564 KB Output is correct
17 Correct 59 ms 125516 KB Output is correct
18 Correct 72 ms 125576 KB Output is correct
19 Correct 62 ms 125592 KB Output is correct
20 Correct 60 ms 125552 KB Output is correct
21 Correct 59 ms 125536 KB Output is correct
22 Correct 65 ms 125592 KB Output is correct
23 Correct 61 ms 125588 KB Output is correct
24 Correct 60 ms 125472 KB Output is correct
25 Correct 69 ms 125476 KB Output is correct
26 Correct 65 ms 125516 KB Output is correct
27 Correct 60 ms 125516 KB Output is correct
28 Correct 63 ms 125592 KB Output is correct
29 Incorrect 60 ms 125564 KB Output isn't correct
30 Halted 0 ms 0 KB -