| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 596037 |
2022-07-14T09:27:46 Z |
조영욱(#8444) |
Bodyguard (JOI21_bodyguard) |
C++17 |
|
4679 ms |
401576 KB |
#include <bits/stdc++.h>
using namespace std;
int n,q;
vector<long long> px;
vector<long long> py;
typedef pair<long long,long long> P;
typedef pair<P,P> PP;
typedef pair<PP,int> PPi;
vector<PPi> v;
int arr[5600][5600][2]; //0:x�� 1:y��
long long dp[5600][5600];
struct Node {
P line;
int l,r;
};
const long long INF=1e9+7;
vector<Node> seg;
Node emp={P(0,-INF*INF),-1,-1};
long long f(P a,long long x) {
return a.first*x+a.second;
}
void insert(P x,int node=0,long long nodel=-INF,long long noder=INF){
P low=seg[node].line;
P high=x;
long long mid=(nodel+noder)/2;
if (f(low,nodel)>f(high,nodel)) {
swap(low,high);
}
if (f(high,noder)>=f(low,noder)) {
seg[node].line=high;
return;
}
if (f(low,mid)>=f(high,mid)) {
seg[node].line=low;
if (seg[node].l==-1) {
seg[node].l=seg.size();
seg.push_back(emp);
}
insert(high,seg[node].l,nodel,mid);
}
else {
seg[node].line=high;
if (seg[node].r==-1) {
seg[node].r=seg.size();
seg.push_back(emp);
}
insert(low,seg[node].r,mid+1,noder);
}
}
long long gety(long long x){
int node=0;
int nodel=-INF;
int noder=INF;
long long ret=-8e18;
while (node!=-1) {
ret=max(ret,f(seg[node].line,x));
long long mid=(nodel+noder)/2;
if (x<=mid){
node=seg[node].l;
noder=mid;
}
else {
node=seg[node].r;
nodel=mid+1;
}
}
return ret;
}
P query[3000000];
long long ret[3000000];
typedef pair<P,int> Pi;
vector<Pi> vec;
bool comp(Pi a,Pi b) {
if (a.first.second==b.first.second) {
if (a.first.first==b.first.first){
return a.second>b.second;
}
return a.first.first>b.first.first;
}
return a.first.second>b.first.second;
}
int main() {
scanf("%d %d",&n,&q);
for(int i=0;i<n;i++) {
long long t,a,b,c;
scanf("%lld %lld %lld %lld",&t,&a,&b,&c);
long long x1=t+a;
long long y1=t-a;
long long x2=t+abs(b-a)+b;
long long y2=t+abs(b-a)-b;
c/=2;
v.push_back(PPi(PP(P(x1,y1),P(x2,y2)),c));
px.push_back(x1);
px.push_back(x2);
py.push_back(y1);
py.push_back(y2);
}
sort(px.begin(),px.end());
px.erase(unique(px.begin(),px.end()),px.end());
sort(py.begin(),py.end());
py.erase(unique(py.begin(),py.end()),py.end());
for(int i=0;i<n;i++) {
v[i].first.first.first=lower_bound(px.begin(),px.end(),v[i].first.first.first)-px.begin();
v[i].first.first.second=lower_bound(py.begin(),py.end(),v[i].first.first.second)-py.begin();
v[i].first.second.first=lower_bound(px.begin(),px.end(),v[i].first.second.first)-px.begin();
v[i].first.second.second=lower_bound(py.begin(),py.end(),v[i].first.second.second)-py.begin();
if (v[i].first.first.second==v[i].first.second.second) {
for(int j=v[i].first.first.first;j<v[i].first.second.first;j++) {
arr[j][v[i].first.first.second][0]=max(arr[j][v[i].first.first.second][0],v[i].second);
}
}
else {
for(int j=v[i].first.first.second;j<v[i].first.second.second;j++) {
arr[v[i].first.first.first][j][1]=max(arr[v[i].first.first.first][j][1],v[i].second);
}
}
}
for(int i=px.size()-1;i>=0;i--) {
for(int j=py.size()-1;j>=0;j--) {
if (i+1<px.size()) {
dp[i][j]=max(dp[i][j],dp[i+1][j]+1LL*arr[i][j][0]*(px[i+1]-px[i]));
}
if (j+1<py.size()) {
dp[i][j]=max(dp[i][j],dp[i][j+1]+1LL*arr[i][j][1]*(py[j+1]-py[j]));
}
}
}
for(int i=0;i<q;i++) {
int t,pos;
scanf("%d %d",&t,&pos);
int x=t+pos;
int y=t-pos;
query[i]=P(x,y);
int xind=lower_bound(px.begin(),px.end(),x)-px.begin();
int yind=lower_bound(py.begin(),py.end(),y)-py.begin();
if (xind==px.size()||yind==py.size()) {
ret[i]=0;
continue;
}
vec.push_back(Pi(P(xind,yind),i));
ret[i]=dp[xind][yind];
}
sort(vec.begin(),vec.end());
reverse(vec.begin(),vec.end());
int ind=0;
for(int i=px.size()-1;i>0;i--) {
seg.clear();
seg.push_back(emp);
int pr=py.size();
while (ind<vec.size()&&vec[ind].first.first==i) {
for(int j=pr-1;j>=vec[ind].first.second;j--) {
insert(P(-arr[i-1][j][0],1LL*arr[i-1][j][0]*px[i]+dp[i][j]));
//printf(".%d %lld\n",-arr[i-1][j][0],1LL*arr[i-1][j][0]*px[i]+dp[i][j]);
}
pr=vec[ind].first.second;
int now=vec[ind].second;
//printf("%d %lld\n",now,gety(query[now].first));
ret[now]=max(ret[now],gety(query[now].first));
ind++;
}
}
sort(vec.begin(),vec.end(),comp);
ind=0;
for(int i=py.size()-1;i>0;i--) {
seg.clear();
seg.push_back(emp);
int pr=px.size();
while (ind<vec.size()&&vec[ind].first.second==i) {
for(int j=pr-1;j>=vec[ind].first.first;j--) {
insert(P(-arr[j][i-1][1],1LL*arr[j][i-1][1]*py[i]+dp[j][i]));
//printf("%lld %lld\n",-arr[j][i-1][1],1LL*arr[j][i-1][1]*py[i]+dp[j][i]);
}
pr=vec[ind].first.first;
int now=vec[ind].second;
ret[now]=max(ret[now],gety(query[now].second));
ind++;
}
}
for(int i=0;i<q;i++) {
printf("%lld\n",ret[i]);
}
return 0;
}
Compilation message
bodyguard.cpp: In function 'int main()':
bodyguard.cpp:130:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
130 | if (i+1<px.size()) {
| ~~~^~~~~~~~~~
bodyguard.cpp:133:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
133 | if (j+1<py.size()) {
| ~~~^~~~~~~~~~
bodyguard.cpp:146:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
146 | if (xind==px.size()||yind==py.size()) {
| ~~~~^~~~~~~~~~~
bodyguard.cpp:146:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
146 | if (xind==px.size()||yind==py.size()) {
| ~~~~^~~~~~~~~~~
bodyguard.cpp:160:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<long long int, long long int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
160 | while (ind<vec.size()&&vec[ind].first.first==i) {
| ~~~^~~~~~~~~~~
bodyguard.cpp:178:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<long long int, long long int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
178 | while (ind<vec.size()&&vec[ind].first.second==i) {
| ~~~^~~~~~~~~~~
bodyguard.cpp:93:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
93 | scanf("%d %d",&n,&q);
| ~~~~~^~~~~~~~~~~~~~~
bodyguard.cpp:96:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
96 | scanf("%lld %lld %lld %lld",&t,&a,&b,&c);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bodyguard.cpp:140:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
140 | scanf("%d %d",&t,&pos);
| ~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4370 ms |
322752 KB |
Output is correct |
| 2 |
Correct |
4679 ms |
324072 KB |
Output is correct |
| 3 |
Correct |
2571 ms |
205928 KB |
Output is correct |
| 4 |
Correct |
1650 ms |
132224 KB |
Output is correct |
| 5 |
Correct |
1638 ms |
401576 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
245 ms |
278848 KB |
Output is correct |
| 2 |
Incorrect |
266 ms |
278364 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
245 ms |
278848 KB |
Output is correct |
| 2 |
Incorrect |
266 ms |
278364 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
245 ms |
278848 KB |
Output is correct |
| 2 |
Incorrect |
266 ms |
278364 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4370 ms |
322752 KB |
Output is correct |
| 2 |
Correct |
4679 ms |
324072 KB |
Output is correct |
| 3 |
Correct |
2571 ms |
205928 KB |
Output is correct |
| 4 |
Correct |
1650 ms |
132224 KB |
Output is correct |
| 5 |
Correct |
1638 ms |
401576 KB |
Output is correct |
| 6 |
Correct |
245 ms |
278848 KB |
Output is correct |
| 7 |
Incorrect |
266 ms |
278364 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
