oj.uz

Submission #577482

# Submission time Handle Problem Language Result Execution time Memory
577482 2022-06-14T20:29:02 Z inksamurai Bodyguard (JOI21_bodyguard) C++17
42 / 100
 8045 ms 1660472 KB 
#include <bits/stdc++.h>
#define int ll
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define rng(i,x,n) for(int i=x;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define vec(...) vector<__VA_ARGS__>
#define _3MJnHrA ios::sync_with_stdio(0),cin.tie(0)
typedef long long ll;
using pii=pair<int,int>;
using vi=vector<int>;
void print(){cout<<'\n';}
template<class h,class...t>
void print(const h&v,const t&...u){cout<<v<<' ',print(u...);}
// e

using T=pair<int,pair<pii,pii>>;

signed main(){
_3MJnHrA;
	int n,q;
	cin>>n>>q;

	vec(T) a(n);
	rep(i,n){
		int _t,_l,_r,_c;
		cin>>_t>>_l>>_r>>_c;
		pii s={_t,_l};
		pii t={_t+abs(_r-_l),_r};
		s={s.fi-s.se,s.fi+s.se};
		t={t.fi-t.se,t.fi+t.se};
		a[i]=T(_c,{s,t});
	}

	vi xys={(int)1e12};
	rep(i,n){
		pii s=a[i].se.fi,t=a[i].se.se;
		// print(s.fi,s.se,t.fi,t.se);
		xys.pb(s.fi);
		xys.pb(s.se);
		xys.pb(t.fi);
		xys.pb(t.se);
	}
	sort(xys.begin(), xys.end());
	xys.erase(unique(xys.begin(), xys.end()),xys.end());

	auto ced=[&](int x){
		return (int)(lower_bound(xys.begin(), xys.end(),x)-xys.begin());
	};

	int _n=sz(xys);
	vec(vi) movex(_n,vi(_n)),movey;
	movey=movex;
	{
		rep(i,n){
			int cosu=a[i].fi;
			pii s=a[i].se.fi,t=a[i].se.se;
			int type=s.fi==t.fi;
			s.fi=ced(s.fi);
			s.se=ced(s.se);
			t.fi=ced(t.fi);
			t.se=ced(t.se);
			// print(s.fi,s.se,t.fi,t.se);
			if(type){
				rng(j,s.se,t.se){
					movey[s.fi][j]=cosu;
				}
			}else{
				rng(j,s.fi,t.fi){
					movex[j][s.se]=cosu;
				}
			}
		}
	}

	vec(vi) dp(_n,vi(_n));
	per(i,_n){
		per(j,_n){
			if(i+1<_n){
				dp[i][j]=max(dp[i][j],dp[i+1][j]+(xys[i+1]-xys[i])*movex[i][j]);
			}
			if(j+1<_n){
				dp[i][j]=max(dp[i][j],dp[i][j+1]+(xys[j+1]-xys[j])*movey[i][j]);
			}
		}
	}

	// rep(i,_n){
	// 	print(xys[i]);
	// }

	// print(dp[1][4]);

	assert(n*q<=8e8);

	rep(_,q){
		int t,_x;
		cin>>t>>_x;
		pii p={t-_x,t+_x};
		int x=p.fi,y=p.se;
		// print(x,y);
		p.fi=ced(p.fi);
		p.se=ced(p.se);
		int ans=0;
		ans=dp[p.fi][p.se];
		if(p.se){
			rng(i,p.fi,_n){
				ans=max(ans,dp[i][p.se]+movey[i][p.se-1]*(xys[p.se]-y));
			}
		}
		if(p.fi){
			rng(j,p.se,_n){
				ans=max(ans,dp[p.fi][j]+movex[p.fi-1][j]*(xys[p.fi]-x));
			}
		}
		print(ans/2);
	}
//
	return 0;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Runtime error 829 ms 1161400 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1102 ms 1658868 KB Output is correct
2 Correct 1097 ms 1658864 KB Output is correct
3 Correct 1107 ms 1657908 KB Output is correct
4 Correct 122 ms 185040 KB Output is correct
5 Correct 803 ms 1152292 KB Output is correct
6 Correct 900 ms 1394092 KB Output is correct
7 Correct 1155 ms 1656460 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1102 ms 1658868 KB Output is correct
2 Correct 1097 ms 1658864 KB Output is correct
3 Correct 1107 ms 1657908 KB Output is correct
4 Correct 122 ms 185040 KB Output is correct
5 Correct 803 ms 1152292 KB Output is correct
6 Correct 900 ms 1394092 KB Output is correct
7 Correct 1155 ms 1656460 KB Output is correct
8 Correct 1613 ms 1658972 KB Output is correct
9 Correct 1659 ms 1658956 KB Output is correct
10 Correct 1489 ms 1657852 KB Output is correct
11 Correct 202 ms 185104 KB Output is correct
12 Correct 1114 ms 1152356 KB Output is correct
13 Correct 1337 ms 1394152 KB Output is correct
14 Correct 1175 ms 1152388 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1102 ms 1658868 KB Output is correct
2 Correct 1097 ms 1658864 KB Output is correct
3 Correct 1107 ms 1657908 KB Output is correct
4 Correct 122 ms 185040 KB Output is correct
5 Correct 803 ms 1152292 KB Output is correct
6 Correct 900 ms 1394092 KB Output is correct
7 Correct 1155 ms 1656460 KB Output is correct
8 Correct 1613 ms 1658972 KB Output is correct
9 Correct 1659 ms 1658956 KB Output is correct
10 Correct 1489 ms 1657852 KB Output is correct
11 Correct 202 ms 185104 KB Output is correct
12 Correct 1114 ms 1152356 KB Output is correct
13 Correct 1337 ms 1394152 KB Output is correct
14 Correct 1175 ms 1152388 KB Output is correct
15 Correct 8045 ms 1660472 KB Output is correct
16 Correct 7655 ms 1660456 KB Output is correct
17 Correct 5990 ms 1659252 KB Output is correct
18 Correct 900 ms 186212 KB Output is correct
19 Correct 5382 ms 1153364 KB Output is correct
20 Correct 6786 ms 1395208 KB Output is correct
21 Correct 1229 ms 1153252 KB Output is correct

Subtask #5
0 / 52.0

# Verdict Execution time Memory Grader output
1 Runtime error 829 ms 1161400 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -