結果
問題 | No.1965 Heavier |
ユーザー |
![]() |
提出日時 | 2023-05-15 22:22:30 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,650 bytes |
コンパイル時間 | 1,569 ms |
コンパイル使用メモリ | 126,116 KB |
最終ジャッジ日時 | 2025-02-13 00:42:11 |
ジャッジサーバーID (参考情報) |
judge2 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 10 WA * 16 |
ソースコード
#include <iostream>#include <vector>#include <cmath>#include <map>#include <set>#include <iomanip>#include <queue>#include <algorithm>#include <numeric>#include <deque>#include <complex>using namespace std;template<class S, S (*op)(S, S), S (*e)()>struct SegTree {vector<S> seg;long long N = 1;SegTree (long long n) : SegTree(vector<S>(n, e())) {}SegTree (const vector<S> &v){long long n = v.size();while (N < n) N *= 2;seg.resize(N*2-1, e());for (long long i=0; i<n; i++) seg[i+N-1] = v[i];for (long long i=N-2; i>=0; i--){seg[i] = op(seg[i*2+1], seg[i*2+2]);}}void set(long long loc, S val){loc += N-1;seg[loc] = val;while (loc != 0){loc = (loc-1)/2;seg[loc] = op(seg[loc*2+1], seg[loc*2+2]);}}//op(a[l], ..., a[r])S prod (long long l, long long r) const{return _prod(l, r, 0, 0, N-1);}S all_prod() const{return seg[0];}S _prod (long long l, long long r, long long idx, long long bitl, long long bitr) const{if (r < bitl || l > bitr) return e();if (l <= bitl && bitr <= r) return seg[idx];long long bitm = (bitl+bitr)/2;return op(_prod(l, r, idx*2+1, bitl, bitm), _prod(l, r, idx*2+2, bitm+1, bitr));}S get (long long i) const{return seg[i+N-1];}void show() const{for (int i=N-1; i<N*2-1; i++) cout << seg[i] << " ";cout << endl;}};long long op(long long a, long long b){return max(a, b);}const long long INF = (1LL<<62) - 1;long long e(){return -INF;}template <typename T>map<T, T> compress(vector<T> &A){map<T, T> comp;int N = A.size(), i=0;for (int i=0; i<N; i++) comp[A[i]];for (auto &e : comp){e.second = i;i++;}return comp;}using ll = long long;int main(){ll N, l=0, ans=0;cin >> N;vector<ll> A(N), B(N);for (int i=0; i<N; i++) cin >> A[i];for (int i=0; i<N; i++) cin >> B[i];map<ll, ll> mp = compress(B);SegTree<long long, op, e> mi(N+1), pl(N+1);auto judge = [&](auto a, auto b){return (pl.prod(mp[b]+1, N) < a+b) && (mi.prod(0, mp[b]-1) < a-b);};for (int r=0; r<N; r++){while(l<r && !judge(A[r], B[r])){mi.set(mp[B[l]], e());pl.set(mp[B[l]], e());l++;}if (judge(A[r], B[r])) ans += r-l;mi.set(mp[B[r]], A[r]-B[r]);pl.set(mp[B[r]], A[r]+B[r]);}cout << ans << endl;return 0;}