Submission #689848

#TimeUsernameProblemLanguageResultExecution timeMemory
689848AntekbBodyguard (JOI21_bodyguard)C++14
0 / 100
1666 ms238156 KiB
#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=5605, 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]; } 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, 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), t+b+abs(a-b))-cy.begin(); //deb(x1, y1, x2, y2, c); 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]/2<<"\n"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...