oj.uz

Submission #419664

# Submission time Handle Problem Language Result Execution time Memory
419664 2021-06-07T11:03:48 Z amoo_safar Bodyguard (JOI21_bodyguard) C++17
100 / 100
 16105 ms 1355424 KB 
// vaziat meshki-ghermeze !
#include <bits/stdc++.h>

#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'
// #define int ll

using namespace std;

typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;

const ll Mod = 1000000007LL;
const int N = 2 * (2802);
const int Q = 3e6 + 10;
const int Inf = 2'000'000'100;
const ll Log = 30;

// X : X + T;
// Y : X - T;

vector<ll> cx, cy;

void Add(ll x, ll y){ cx.pb(x); cy.pb(y); }
void Uni(vector<ll>& C){
	sort(all(C));
	C.resize(unique(all(C)) - C.begin());
}
void Init(){ Uni(cx); Uni(cy); }
pii Get(ll x, ll y){
	x = lower_bound(all(cx), x) - cx.begin();
	y = lower_bound(all(cy), y) - cy.begin();
	return {x, y};
}
ll T[N], T2[N], A[N], B[N], P[Q], X[Q];
ll C[N];

ll up[N][N], rt[N][N];
ll dp[N][N];

 
typedef pair < ll , ll > Line;
struct CHT{
    set < pair < Line , ll > > S;
    set < pair < ll , Line > > I;
    ll INF = 4e18;
    inline void Add(Line X)
    {
        ll t = -INF;
        auto it = S.lower_bound({X, -INF});
        while ((int)S.size())
        {
            if (it == S.begin())
                {t = -INF; break;}
            it --; ll r = Intersection(it->first, X);
            if (r <= it->second)
                I.erase({it->second, it->first}), it = S.erase(it);
            else
                {t = r; break;}
        }
        it = S.lower_bound({X, -INF});
        while ((int)S.size())
        {
            if (it == S.end())
                break;
            ll r = Intersection(X, it->first);
            Line Y = it->first;
            I.erase({it->second, it->first});
            it = S.erase(it);
            if (r <= t)
            {
                r = -INF;
                if (it != S.begin())
                    it --, r = Intersection(it->first, Y);
                S.insert({Y, r}); I.insert({r, Y}); return ;
            }
            if (it != S.end() && it->second <= r)
                continue;
            S.insert({Y, r}); I.insert({r, Y}); break;
        }
        S.insert({X, t}); I.insert({t, X});
    }
    inline ll GetMax(ll X)
    {
        auto it = I.upper_bound({X, {INF, INF}}); it --;
        return (X * it->second.first + it->second.second);
    }
    inline ll Intersection(Line X, Line Y)
    {
        if (X.first == Y.first && X.second <= Y.second)
            return (-INF);
        if (X.first == Y.first)
            return (INF);
        return ((X.second - Y.second) / (Y.first - X.first)) + ((X.second - Y.second) % (Y.first - X.first) > 0);
    }
};
CHT row[N], col[N];

ll zx[Q], zy[Q], ans[Q];
vector<int> V[N][N];

int32_t main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n, q;
	cin >> n >> q;
	// assert(q == 1);
	// for(int i = -3000; i <= 6000; i++) Add(i, i);

	// debug(Inf);
	for(int i = 1; i <= n; i++){
		cin >> T[i] >> A[i] >> B[i] >> C[i];
		T2[i] = abs(A[i] - B[i]) + T[i];
		C[i] /= 2;
		Add(T[i] + A[i], T[i] - A[i]);
		Add(T2[i]+ B[i],T2[i] - B[i]);
	}
	// Add(Q, Q);
	Add(Inf, Inf);
	Add(-Inf, -Inf);
	
	for(int i = 1; i <= q; i++){
		cin >> P[i] >> X[i];
		// Add(P[i] + X[i], P[i] - X[i]);
	}
	Init();
	for(int i = 1; i <= n; i++){
		pii st = Get(T[i] + A[i], T[i] - A[i]);
		pii fn = Get(T2[i]+ B[i],T2[i] - B[i]);
		// cerr << 
		if(st.F == fn.F){
			for(int _i = st.S; _i < fn.S; _i++)
				up[st.F][_i] = max(up[st.F][_i], C[i]);
		} else {	
			for(int _i = st.F; _i < fn.F; _i++)
				rt[_i][st.S] = max(rt[_i][st.S], C[i]);
		}
	}

	for(int i = 1; i <= q; i++){
		// if(abs(P[i] + X[i]) > 3000 || abs(P[i] - X[i]) > 3000){
		// 	cout << "0\n";
		// 	continue;
		// }
		pii st = Get(P[i] + X[i], P[i] - X[i]);
		// ll ans = dp[st.F][st.S];
		V[st.F][st.S].pb(i);
		// for(int j = st.F; j < nx; j++)
		// 	ans = max(ans, dp[j][st.S] + (cy[st.S] - (P[i] - X[i])) * up[j][st.S - 1]);
		zy[i] = (cy[st.S] - (P[i] - X[i]));
		// for(int j = st.S; j < ny; j++)
		// 	ans = max(ans, dp[st.F][j] + (cx[st.F] - (P[i] + X[i])) * rt[st.F - 1][j]);
		zx[i] = (cx[st.F] - (P[i] + X[i]));
		// assert(cx[st.F] == P[i] + X[i]);
		// assert(cy[st.S] == P[i] - X[i]);
		// cout << ans << '\n';
	}
	
	int nx = cx.size(), ny = cy.size();
	for(int i = nx - 1; i > 0; i--){
		for(int j = ny - 1; j > 0; j--){
			if(i != nx - 1 && j != ny - 1)
				dp[i][j] = max(1ll * up[i][j] * (cy[j + 1] - cy[j]) + dp[i][j + 1], 1ll * rt[i][j] * (cx[i + 1] - cx[i]) + dp[i + 1][j]);
			col[i].Add({rt[i - 1][j], dp[i][j]});
			row[j].Add({up[i][j - 1], dp[i][j]});
		
			for(auto q_id : V[i][j])
				ans[q_id] = max(row[j].GetMax(zy[q_id]), col[i].GetMax(zx[q_id]));
		}
	}
	for(int i = 1; i <= q; i++)
		cout << ans[i] << '\n';
	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11098 ms 1117716 KB Output is correct
2 Correct 9847 ms 1121224 KB Output is correct
3 Correct 3667 ms 964736 KB Output is correct
4 Correct 2005 ms 899308 KB Output is correct
5 Correct 9141 ms 1156488 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 10978 ms 1046928 KB Output is correct
2 Correct 10748 ms 1046640 KB Output is correct
3 Correct 10569 ms 1050168 KB Output is correct
4 Correct 458 ms 740036 KB Output is correct
5 Correct 8642 ms 1221520 KB Output is correct
6 Correct 7575 ms 1011140 KB Output is correct
7 Correct 5266 ms 980292 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10978 ms 1046928 KB Output is correct
2 Correct 10748 ms 1046640 KB Output is correct
3 Correct 10569 ms 1050168 KB Output is correct
4 Correct 458 ms 740036 KB Output is correct
5 Correct 8642 ms 1221520 KB Output is correct
6 Correct 7575 ms 1011140 KB Output is correct
7 Correct 5266 ms 980292 KB Output is correct
8 Correct 11075 ms 1047120 KB Output is correct
9 Correct 11003 ms 1046900 KB Output is correct
10 Correct 10344 ms 1049112 KB Output is correct
11 Correct 471 ms 740420 KB Output is correct
12 Correct 8725 ms 1221828 KB Output is correct
13 Correct 7846 ms 1011472 KB Output is correct
14 Correct 8066 ms 984196 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10978 ms 1046928 KB Output is correct
2 Correct 10748 ms 1046640 KB Output is correct
3 Correct 10569 ms 1050168 KB Output is correct
4 Correct 458 ms 740036 KB Output is correct
5 Correct 8642 ms 1221520 KB Output is correct
6 Correct 7575 ms 1011140 KB Output is correct
7 Correct 5266 ms 980292 KB Output is correct
8 Correct 11075 ms 1047120 KB Output is correct
9 Correct 11003 ms 1046900 KB Output is correct
10 Correct 10344 ms 1049112 KB Output is correct
11 Correct 471 ms 740420 KB Output is correct
12 Correct 8725 ms 1221828 KB Output is correct
13 Correct 7846 ms 1011472 KB Output is correct
14 Correct 8066 ms 984196 KB Output is correct
15 Correct 11416 ms 1050208 KB Output is correct
16 Correct 12097 ms 1050948 KB Output is correct
17 Correct 11193 ms 1054604 KB Output is correct
18 Correct 466 ms 742980 KB Output is correct
19 Correct 8554 ms 1224492 KB Output is correct
20 Correct 7640 ms 1014164 KB Output is correct
21 Correct 8026 ms 986476 KB Output is correct

Subtask #5
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 11098 ms 1117716 KB Output is correct
2 Correct 9847 ms 1121224 KB Output is correct
3 Correct 3667 ms 964736 KB Output is correct
4 Correct 2005 ms 899308 KB Output is correct
5 Correct 9141 ms 1156488 KB Output is correct
6 Correct 10978 ms 1046928 KB Output is correct
7 Correct 10748 ms 1046640 KB Output is correct
8 Correct 10569 ms 1050168 KB Output is correct
9 Correct 458 ms 740036 KB Output is correct
10 Correct 8642 ms 1221520 KB Output is correct
11 Correct 7575 ms 1011140 KB Output is correct
12 Correct 5266 ms 980292 KB Output is correct
13 Correct 11075 ms 1047120 KB Output is correct
14 Correct 11003 ms 1046900 KB Output is correct
15 Correct 10344 ms 1049112 KB Output is correct
16 Correct 471 ms 740420 KB Output is correct
17 Correct 8725 ms 1221828 KB Output is correct
18 Correct 7846 ms 1011472 KB Output is correct
19 Correct 8066 ms 984196 KB Output is correct
20 Correct 11416 ms 1050208 KB Output is correct
21 Correct 12097 ms 1050948 KB Output is correct
22 Correct 11193 ms 1054604 KB Output is correct
23 Correct 466 ms 742980 KB Output is correct
24 Correct 8554 ms 1224492 KB Output is correct
25 Correct 7640 ms 1014164 KB Output is correct
26 Correct 8026 ms 986476 KB Output is correct
27 Correct 15995 ms 1338204 KB Output is correct
28 Correct 16105 ms 1330740 KB Output is correct
29 Correct 13048 ms 1286344 KB Output is correct
30 Correct 1700 ms 946336 KB Output is correct
31 Correct 9898 ms 1355424 KB Output is correct
32 Correct 10011 ms 1234676 KB Output is correct
33 Correct 9066 ms 1192712 KB Output is correct