이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
const int N=2e5+2;
const int inf=1e9+7;
using namespace std;
vector<int> que_lis[N];
vector<pair<int,bool> > event[N];
int c[4*N],d[4*N],lazy[4*N],ar[N],ans[N],ranl[N],ranr[N];
pair<int,int> que[N];
void init(int idx,int l,int r){
c[idx]=-inf;
d[idx]=-inf;
lazy[idx]=-inf;
if(l==r){
return;
}
int mid=(l+r)>>1;
init(idx<<1,l,mid);
init(idx<<1|1,mid+1,r);
}
void push(int idx,int l,int r){
lazy[idx<<1]=max(lazy[idx<<1],lazy[idx]);
lazy[idx<<1|1]=max(lazy[idx<<1|1],lazy[idx]);
d[idx<<1]=max(c[idx<<1]+lazy[idx<<1],d[idx<<1]);
d[idx<<1|1]=max(c[idx<<1|1]+lazy[idx<<1|1],d[idx<<1|1]);
lazy[idx]=-inf;
}
void upd(int idx,int l,int r,int pos,bool haiz){
if(l>pos||r<pos){
return;
}
if(l==r){
if(haiz){
c[idx]=ar[pos];
}
else{
d[idx]=max(d[idx],c[idx]+lazy[idx]);
c[idx]=-inf;
}
lazy[idx]=-inf;
return;
}
if(lazy[idx]!=-inf){
push(idx,l,r);
}
int mid=(l+r)>>1;
upd(idx<<1,l,mid,pos,haiz);
upd(idx<<1|1,mid+1,r,pos,haiz);
c[idx]=max(c[idx<<1],c[idx<<1|1]);
d[idx]=max(max(c[idx]+lazy[idx],d[idx]),max(d[idx<<1],d[idx<<1|1]));
}
void upd1(int idx,int l,int r,int lef,int rig,int val){
if(l>rig||r<lef){
return;
}
if(l>=lef&&r<=rig){
lazy[idx]=max(lazy[idx],val);
val=-inf;
if(l!=r){
val=max(d[idx<<1],d[idx<<1|1]);
}
d[idx]=max(max(c[idx]+lazy[idx],d[idx]),val);
return;
}
if(lazy[idx]!=-inf){
push(idx,l,r);
}
int mid=(l+r)>>1;
upd1(idx<<1,l,mid,lef,rig,val);
upd1(idx<<1|1,mid+1,r,lef,rig,val);
d[idx]=max(max(c[idx]+lazy[idx],d[idx]),max(d[idx<<1],d[idx<<1|1]));
}
int getmax(int idx,int l,int r,int lef,int rig){
if(l>rig||r<lef){
return -inf;
}
if(l>=lef&&r<=rig){
return d[idx];
}
if(lazy[idx]!=-inf){
push(idx,l,r);
}
int mid=(l+r)>>1;
return max(getmax(idx<<1,l,mid,lef,rig),getmax(idx<<1|1,mid+1,r,lef,rig));
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n,i,j,k,l,q;
cin>>n;
init(1,1,n);
for(i=1;i<=n;i++){
cin>>ar[i]>>ranl[i]>>ranr[i];
ranr[i]++;
if(i+ranl[i]<=n){
event[i+ranl[i]].push_back({i,true});
}
if(i+ranr[i]<=n){
event[i+ranr[i]].push_back({i,false});
}
}
cin>>q;
for(i=1;i<=q;i++){
ans[i]=-1;
cin>>que[i].first>>que[i].second;
que_lis[que[i].second].push_back(i);
}
for(i=1;i<=n;i++){
for(j=0;j<event[i].size();j++){
upd(1,1,n,event[i][j].first,event[i][j].second);
}
if(i-ranl[i]>0){
upd1(1,1,n,max(1,i-ranr[i]+1),i-ranl[i],-ar[i]);
}
for(j=0;j<que_lis[i].size();j++){
// cout<<que_lis[i][j]<<' '<<getmax(1,1,n,que[que_lis[i][j]].first,i)<<endl;
ans[que_lis[i][j]]=max(ans[que_lis[i][j]],getmax(1,1,n,que[que_lis[i][j]].first,i));
}
event[i].clear();
que_lis[i].clear();
}
init(1,1,n);
for(i=n;i>=1;i--){
if(i-ranl[i]>0){
event[i-ranl[i]].push_back({i,true});
}
if(i-ranr[i]>0){
event[i-ranr[i]].push_back({i,false});
}
}
for(i=1;i<=q;i++){
que_lis[que[i].first].push_back(i);
}
for(i=n;i>=1;i--){
for(j=0;j<event[i].size();j++){
upd(1,1,n,event[i][j].first,event[i][j].second);
}
if(i+ranl[i]<=n){
upd1(1,1,n,i+ranl[i],min(i+ranr[i]-1,n),-ar[i]);
}
for(j=0;j<que_lis[i].size();j++){
ans[que_lis[i][j]]=max(ans[que_lis[i][j]],getmax(1,1,n,i,que[que_lis[i][j]].second));
}
}
for(i=1;i<=q;i++){
cout<<ans[i]<<'\n';
}
}
/*
5
10 2 4
1 1 1
2 1 3
1 1 1
100 1 1
5
1 2
2 3
1 3
1 4
1 5
*/
컴파일 시 표준 에러 (stderr) 메시지
antennas.cpp: In function 'int main()':
antennas.cpp:108:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(j=0;j<event[i].size();j++){
~^~~~~~~~~~~~~~~~
antennas.cpp:114:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(j=0;j<que_lis[i].size();j++){
~^~~~~~~~~~~~~~~~~~
antennas.cpp:134:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(j=0;j<event[i].size();j++){
~^~~~~~~~~~~~~~~~
antennas.cpp:140:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(j=0;j<que_lis[i].size();j++){
~^~~~~~~~~~~~~~~~~~
antennas.cpp:88:12: warning: unused variable 'k' [-Wunused-variable]
int n,i,j,k,l,q;
^
antennas.cpp:88:14: warning: unused variable 'l' [-Wunused-variable]
int n,i,j,k,l,q;
^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |