이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>
#define pb push_back
#define mp make_pair
#define taskname "A"
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef pair<ll,int> ii;
typedef tree <int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
const int maxn = 2e5 + 5;
const int inf = 1e9 + 1;
struct segTree{
int mx[maxn * 4],lz[maxn * 4],ans[maxn * 4];
void reset(){
fill_n(mx,maxn*4,0);
fill_n(lz,maxn*4,inf);
fill_n(ans,maxn*4,-1);
}
void push(int x , bool key){
ans[x] = max(ans[x],mx[x]-lz[x]);
if(key)lz[x*2] = min(lz[x*2],lz[x]),lz[x*2+1] = min(lz[x * 2 + 1],lz[x]);
lz[x] = inf;
}
void updateP(int x , int l , int r , int pos , int val){
push(x,l != r);
if(l == r){
mx[x] = val;
return;
}
int mid = l + r >> 1;
if(pos <= mid)updateP(x*2,l,mid,pos,val);
else updateP(x*2+1,mid+1,r,pos,val);
ans[x] = max({ans[x],ans[x * 2],ans[x * 2 + 1]});
mx[x] = max(mx[x * 2] , mx[x * 2 + 1]);
}
void updateR(int x , int l , int r , int L , int R , int val){
push(x,l!=r);
if(l > R || L > r)return;
if(L <= l && r <= R){
lz[x] = min(lz[x],val);push(x,l!=r);return;
}
int mid = l + r >> 1;
updateR(x*2,l,mid,L,R,val);
updateR(x*2+1,mid+1,r,L,R,val);
ans[x] = max({ans[x],ans[x * 2],ans[x * 2 + 1]});
mx[x] = max(mx[x * 2],mx[x * 2 + 1]);
}
int query(int x , int l , int r , int L , int R){
push(x,l!=r);
if(l > R || L > r)return -1;
if(L <= l && r <= R)return ans[x];
int mid = l + r >> 1;
return max(query(x*2,l,mid,L,R),query(x*2+1,mid+1,r,L,R));
}
}s;
int n , q;
int a[maxn],b[maxn],h[maxn];
ii queries[maxn];
int ans[maxn];
vector<ii> Q[maxn];
vector<int> avai[maxn];
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
if(fopen(taskname".INP","r")){
freopen(taskname".INP", "r",stdin);
freopen(taskname".OUT", "w",stdout);
}
cin >> n;
for(int i = 1 ; i <= n ; ++i){
cin >> h[i] >> a[i] >> b[i];
}
cin >> q;
for(int i = 1 ; i <= q ; ++i){
cin >> queries[i].first >> queries[i].second;
ans[i] = -1;
}
{
//h[i] - h[j]
for(int i = 1 ; i <= q ; ++i){
Q[queries[i].second].pb(mp(queries[i].first,i));
}
s.reset();
for(int i = 1 ; i <= n ; ++i){
if(i + a[i] <= n){
avai[i + a[i]].pb(i);
}
if(i + b[i] + 1 <= n){
avai[i + b[i] + 1].pb(-i);
}
for(auto c : avai[i]){
if(c > 0)s.updateP(1,1,n,c,h[c]);
else s.updateP(1,1,n,-c,0);
}
avai[i].clear();
s.updateR(1,1,n,i-b[i],i-a[i],h[i]);
for(auto c : Q[i]){
ans[c.second] = max(ans[c.second],s.query(1,1,n,c.first,i));
}
Q[i].clear();
}
}
{
//-h[i] + h[j]
for(int i = 1 ; i <= q ; ++i){
Q[queries[i].first].pb(mp(queries[i].second,i));
}
s.reset();
for(int i = n ; i >= 1 ; --i){
if(i - a[i] >= 1){
avai[i - a[i]].pb(i);
}
if(i - b[i] - 1 >= 1){
avai[i - b[i] - 1].pb(-i);
}
for(auto c : avai[i]){
if(c > 0)s.updateP(1,1,n,c,h[c]);
else s.updateP(1,1,n,-c,0);
}
avai[i].clear();
s.updateR(1,1,n,i+a[i],i + b[i],h[i]);
for(auto c : Q[i]){
ans[c.second] = max(ans[c.second],s.query(1,1,n,i,c.first));
}
Q[i].clear();
}
}
for(int i = 1 ; i <= q ; ++i)cout << ans[i] << '\n';
}
컴파일 시 표준 에러 (stderr) 메시지
antennas.cpp: In member function 'void segTree::updateP(int, int, int, int, int)':
antennas.cpp:38:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = l + r >> 1;
~~^~~
antennas.cpp: In member function 'void segTree::updateR(int, int, int, int, int, int)':
antennas.cpp:50:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = l + r >> 1;
~~^~~
antennas.cpp: In member function 'int segTree::query(int, int, int, int, int)':
antennas.cpp:60:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = l + r >> 1;
~~^~~
antennas.cpp: In function 'int main()':
antennas.cpp:76:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen(taskname".INP", "r",stdin);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:77:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen(taskname".OUT", "w",stdout);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
# | 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... |