이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#define fr first
#define sc second
using namespace std;
typedef long long ll;
typedef long double ld;
template<class T>void umax(T &a,T b){if(a<b)a=b;}
template<class T>void umin(T &a,T b){if(b<a)a=b;}
#ifdef juggernaut
#define printl(args...) printf(args)
#else
#define printl(args...) 0
#endif
int h[200005];
int a[200005];
int b[200005];
int tree[800005];
const int inf=1e9;
int ans=-1;
void chmax(int v,int l,int r,int ql,int qr,int val){
if(ql<=l&&r<=qr){
umax(tree[v],val);
return;
}
if(qr<l||r<ql)return;
int mid=(l+r)>>1;
chmax(v<<1,l,mid,ql,qr,val);
chmax(v<<1|1,mid+1,r,ql,qr,val);
}
void upd(int v,int l,int r,int pos,int val=-inf){
umax(val,tree[v]);
if(l==r){
umax(ans,val-h[pos]);
return;
}
int mid=(l+r)>>1;
if(pos<=mid)upd(v<<1,l,mid,pos,val);
else upd(v<<1|1,mid+1,r,pos,val);
}
void st(int v,int l,int r,int pos){
if(l==r){
tree[v]=-inf;
return;
}else{
umax(tree[v<<1],tree[v]);
umax(tree[v<<1|1],tree[v]);
}
tree[v]=-inf;
int mid=(l+r)>>1;
if(pos<=mid)st(v<<1,l,mid,pos);
else st(v<<1|1,mid+1,r,pos);
}
int main(){
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d%d%d",&h[i],&a[i],&b[i]);
if(n<=2000&&false){
vector<vector<pair<int,int>>>query(n+1);
int q;
scanf("%d",&q);
vector<int>ans(q,0),arr(n+1,-1);
for(int i=0;i<q;i++){
int l,r;
scanf("%d%d",&l,&r);
query[l].emplace_back(r,i);
}
for(int i=n;i>0;i--){
for(int j=i+1;j<=n;j++){
if(max(a[i],a[j])<=j-i&&j-i<=min(b[i],b[j])){
umax(arr[j],abs(h[i]-h[j]));
}
umax(arr[j],arr[j-1]);
}
for(auto q:query[i])ans[q.sc]=arr[q.fr];
}
for(int i=0;i<q;i++)printf("%d\n",ans[i]);
}else{
{
vector<vector<int>>inc(n+1),exc(n+1);
for(int i=1;i<=n;i++){
if(i>a[i]){
exc[max(1,i-b[i])].push_back(i);
inc[i-a[i]].push_back(i);
}
}
for(int i=n;i;i--){
for(int idx:inc[i])st(1,1,n,idx);
if(i+a[i]<=n){
chmax(1,1,n,i+a[i],min(i+b[i],n),h[i]);
}
for(int idx:exc[i])upd(1,1,n,idx);
}
}
reverse(h+1,h+1+n);
reverse(a+1,a+1+n);
reverse(b+1,b+1+n);
memset(tree,0,sizeof tree);
{
vector<vector<int>>inc(n+1),exc(n+1);
for(int i=1;i<=n;i++){
if(i>a[i]){
exc[max(1,i-b[i])].push_back(i);
inc[i-a[i]].push_back(i);
}
}
for(int i=n;i;i--){
for(int idx:inc[i])st(1,1,n,idx);
if(i+a[i]<=n){
chmax(1,1,n,i+a[i],min(i+b[i],n),h[i]);
}
for(int idx:exc[i])upd(1,1,n,idx);
}
}
cout<<ans;
}
}
컴파일 시 표준 에러 (stderr) 메시지
antennas.cpp: In function 'int main()':
antennas.cpp:55:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
55 | scanf("%d",&n);
| ~~~~~^~~~~~~~~
antennas.cpp:56:28: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
56 | for(int i=1;i<=n;i++)scanf("%d%d%d",&h[i],&a[i],&b[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:60:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
60 | scanf("%d",&q);
| ~~~~~^~~~~~~~~
antennas.cpp:64:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
64 | scanf("%d%d",&l,&r);
| ~~~~~^~~~~~~~~~~~~~
# | 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... |