제출 #207665

#제출 시각아이디문제언어결과실행 시간메모리
207665MercenaryTwo Antennas (JOI19_antennas)C++14
100 / 100
818 ms47736 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...