oj.uz

Submission #689855

# Submission time Handle Problem Language Result Execution time Memory
689855 2023-01-29T14:43:42 Z Antekb Bodyguard (JOI21_bodyguard) C++14
28 / 100
 3282 ms 648408 KB 
#include<bits/stdc++.h>
 
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("trapv")
 
#define st first
#define nd second
#define pb push_back
#define eb emplace_back
#define pp(x) pop_back(x)
#define mp(a, b) make_pair(a, b)
#define all(x) (x).begin(), (x).end()
#define rev(x) reverse(all(x))
#define sor(x) sort(all(x))
#define sz(x) (int)(x).size()
#define rsz(x) resize(x)
 
using namespace std;
 
///~~~~~~~~~~~~~~~~~~~~~~~~~~
 
template <typename H, typename T> 
ostream& operator<<(ostream& os, pair<H, T> m){
	return os <<"("<< m.st<<", "<<m.nd<<")";
}
template <typename H> 
ostream& operator<<(ostream& os, vector<H> V){
	os<<"{";
	for(int i=0; i<V.size(); i++){
		if(i)os<<" ";
		os<<V[i];
	}
	os<<"}";
	return os;
}
 
void debug(){cerr<<"\n";}
template <typename H, typename... T>
void debug(H h, T... t) {cerr<<h; if (sizeof...(t)) cerr << ", "; debug(t...);}
#define deb(x...) cerr<<#x<<" = ";debug(x);
 
///~~~~~~~~~~~~~~~~~~~~~~~~~
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<pii > vii;
typedef vector<ll> vl;
typedef vector<pll> vll;
typedef string str;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template <typename T>
using ordered_set =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

 
#define BOOST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
 
//mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
 
const int N=10005, INF=1e9+5, mod=1e9+7, mod2=998244353;

struct modint{
	int n=0;
	modint(){}
	modint(ll x){
		n=x%mod;
		if(n<0)n+=mod;
	}
	operator int(){
		return n;
	}
	modint operator+(modint a){a.n = n+a.n; if(a.n>=mod)a.n-=mod;return a;}
	modint operator+=(modint a){return (*this)=(*this)+a;}
	modint operator-(modint a){a.n = n-a.n; if(a.n<0)a.n+=mod;return a;}
	modint operator-=(modint a){return (*this)=(*this)-a;}
	modint operator*(modint a){a.n = (n*1ll*a.n)%mod; return a;}
	modint operator*=(modint a){return (*this)=(*this)*a;}
	modint operator^(const ll &m)const{
		modint a(1);
		if(m==0)return a;
		if(m==1)return (*this);
		a=(*this)^(m/2);
		a*=a;
		return a*((*this)^(m&1));
	}
	modint odw(){
		return (*this)^((ll)mod-2);
	}
	modint operator/(modint a){return (*this)*a.odw();}
	modint operator/=(modint a){return (*this)=(*this)/a;}
	bool operator==(modint a){return a.n==n;}
	friend ostream& operator<<(ostream& os, modint m) {
		return os << m.n; 
	}
};
modint fact[N], fact2[N];
typedef vector<modint> vm;
void factinit(){
    fact[0]=1;
    for(int i=1; i<N; i++){
        fact[i]=(fact[i-1]*modint(i))%mod;
    }
    fact2[N-1]=fact[N-1].odw();
    for(int i=N-2; i>=0; i--){
    	fact2[i]=(fact2[i+1]*modint(i+1))%mod;
    }
}
modint npok(int _n, int _k){
    return fact[_n]*fact2[_k]*fact2[_n-_k];
}
using uint=unsigned int;
const int M=3e6+5;
int edg[2][N][N], X[N], Y[N];
ll dp[N][N];
//vii co[2][N][N];
ll ans[M];
int main(){
	//factinit();
	//BOOST;
	int n, q;
	cin>>n>>q;
	vector<pair<pii, pii> > V;
	vector<int> cx;
	vector<uint> cy;
	for(int i=0; i<n; i++){
		int t, a, b, c;
		cin>>t>>a>>b>>c;
		V.eb(mp(t, c), mp(a, b));
		cx.pb(t-a);
		cx.pb(t-b+abs(a-b));
		cy.pb(t+a);
		cy.pb(t+b+abs(a-b));
	}
	vii Q;
	for(int i=0; i<q; i++){
		int t, x;
		cin>>t>>x;
		cx.pb(t-x);
		cy.pb(t+x);
		Q.eb(t-x, t+x);
	}
	//deb(cx, cy);
	sor(cx);
	cx.rsz(unique(all(cx))-cx.begin());
	sor(cy);
	cy.rsz(unique(all(cy))-cy.begin());
	int XX=cx.size(), YY=cy.size();
	for(int i=0; i<n; i++){
		int t=V[i].st.st, c=V[i].st.nd, a=V[i].nd.st, b=V[i].nd.nd;
		int x1=lower_bound(all(cx), t-a)-cx.begin();
		int x2=lower_bound(all(cx), t-b+abs(a-b))-cx.begin();
		int y1=lower_bound(all(cy), t+a)-cy.begin();
		int y2=lower_bound(all(cy), uint(t+b)+abs(a-b))-cy.begin();
		//deb(x1, y1, x2, y2, c);
		assert(y1<=y2);
		assert(x1<=x2);
		c/=2;
		if(x1==x2){
			for(int y=y1; y<y2; y++){
				edg[0][x1][y]=max(edg[0][x1][y], c);
			}
		}
		else{
			for(int x=x1; x<x2; x++){
				edg[1][x][y1]=max(edg[1][x][y1], c);
			}
		}
	}
	for(int x=XX-1; x>=0; x--){
		for(int y=YY-1; y>=0; y--){
			if(x+1!=XX)dp[x][y]=max(dp[x+1][y]+edg[1][x][y]*1ll*(cx[x+1]-cx[x]), dp[x][y]);
			if(y+1!=YY)dp[x][y]=max(dp[x][y+1]+edg[0][x][y]*1ll*(cy[y+1]-cy[y]), dp[x][y]);
		}
	}
	for(pii &i:Q){
		i.st=lower_bound(all(cx), i.st)-cx.begin();
		i.nd=lower_bound(all(cy), i.nd)-cy.begin();
		//deb(cx[i.st], cy[i.nd]);
		cout<<dp[i.st][i.nd]<<"\n";
	}
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3235 ms 543536 KB Output is correct
2 Correct 3282 ms 567616 KB Output is correct
3 Correct 2984 ms 448900 KB Output is correct
4 Correct 2976 ms 441320 KB Output is correct
5 Correct 3124 ms 604252 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 226 ms 240376 KB Output is correct
2 Correct 228 ms 240176 KB Output is correct
3 Correct 253 ms 239036 KB Output is correct
4 Correct 23 ms 35020 KB Output is correct
5 Correct 242 ms 209388 KB Output is correct
6 Correct 210 ms 194096 KB Output is correct
7 Correct 237 ms 209060 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 226 ms 240376 KB Output is correct
2 Correct 228 ms 240176 KB Output is correct
3 Correct 253 ms 239036 KB Output is correct
4 Correct 23 ms 35020 KB Output is correct
5 Correct 242 ms 209388 KB Output is correct
6 Correct 210 ms 194096 KB Output is correct
7 Correct 237 ms 209060 KB Output is correct
8 Correct 588 ms 648408 KB Output is correct
9 Correct 604 ms 647064 KB Output is correct
10 Correct 595 ms 586100 KB Output is correct
11 Correct 74 ms 75596 KB Output is correct
12 Correct 371 ms 357128 KB Output is correct
13 Correct 566 ms 519128 KB Output is correct
14 Correct 542 ms 489764 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 226 ms 240376 KB Output is correct
2 Correct 228 ms 240176 KB Output is correct
3 Correct 253 ms 239036 KB Output is correct
4 Correct 23 ms 35020 KB Output is correct
5 Correct 242 ms 209388 KB Output is correct
6 Correct 210 ms 194096 KB Output is correct
7 Correct 237 ms 209060 KB Output is correct
8 Correct 588 ms 648408 KB Output is correct
9 Correct 604 ms 647064 KB Output is correct
10 Correct 595 ms 586100 KB Output is correct
11 Correct 74 ms 75596 KB Output is correct
12 Correct 371 ms 357128 KB Output is correct
13 Correct 566 ms 519128 KB Output is correct
14 Correct 542 ms 489764 KB Output is correct
15 Runtime error 66 ms 2336 KB Execution killed with signal 11
16 Halted 0 ms 0 KB -

Subtask #5
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 3235 ms 543536 KB Output is correct
2 Correct 3282 ms 567616 KB Output is correct
3 Correct 2984 ms 448900 KB Output is correct
4 Correct 2976 ms 441320 KB Output is correct
5 Correct 3124 ms 604252 KB Output is correct
6 Correct 226 ms 240376 KB Output is correct
7 Correct 228 ms 240176 KB Output is correct
8 Correct 253 ms 239036 KB Output is correct
9 Correct 23 ms 35020 KB Output is correct
10 Correct 242 ms 209388 KB Output is correct
11 Correct 210 ms 194096 KB Output is correct
12 Correct 237 ms 209060 KB Output is correct
13 Correct 588 ms 648408 KB Output is correct
14 Correct 604 ms 647064 KB Output is correct
15 Correct 595 ms 586100 KB Output is correct
16 Correct 74 ms 75596 KB Output is correct
17 Correct 371 ms 357128 KB Output is correct
18 Correct 566 ms 519128 KB Output is correct
19 Correct 542 ms 489764 KB Output is correct
20 Runtime error 66 ms 2336 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -