結果
問題 | No.1496 不思議な数え上げ |
ユーザー |
|
提出日時 | 2021-04-30 23:30:58 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 195 ms / 3,000 ms |
コード長 | 4,454 bytes |
コンパイル時間 | 2,036 ms |
コンパイル使用メモリ | 204,140 KB |
最終ジャッジ日時 | 2025-01-21 04:45:47 |
ジャッジサーバーID (参考情報) |
judge2 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 39 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define rep(i, n) for(int i = 0; i < n; i++)#define rep2(i, x, n) for(int i = x; i <= n; i++)#define rep3(i, x, n) for(int i = x; i >= n; i--)#define each(e, v) for(auto &e: v)#define pb push_back#define eb emplace_back#define all(x) x.begin(), x.end()#define rall(x) x.rbegin(), x.rend()#define sz(x) (int)x.size()using ll = long long;using pii = pair<int, int>;using pil = pair<int, ll>;using pli = pair<ll, int>;using pll = pair<ll, ll>;const int MOD = 1000000007;//const int MOD = 998244353;const int inf = (1<<30)-1;const ll INF = (1LL<<60)-1;template<typename T> bool chmax(T &x, const T &y) {return (x < y)? (x = y, true) : false;};template<typename T> bool chmin(T &x, const T &y) {return (x > y)? (x = y, true) : false;};struct io_setup{io_setup(){ios_base::sync_with_stdio(false);cin.tie(NULL);cout << fixed << setprecision(15);}} io_setup;template<typename Monoid>struct Segment_Tree{using F = function<Monoid(Monoid, Monoid)>;int n;vector<Monoid> seg;const F f;const Monoid e1;Segment_Tree(const vector<Monoid> &v, const F &f, const Monoid &e1) : f(f), e1(e1){int m = v.size();n = 1;while(n < m) n <<= 1;seg.assign(2*n, e1);copy(begin(v), end(v), begin(seg)+n);for(int i = n-1; i > 0; i--) seg[i] = f(seg[2*i], seg[2*i+1]);}void change(int i, const Monoid &x){seg[i += n] = x;while(i >>= 1){seg[i] = f(seg[2*i], seg[2*i+1]);}}Monoid query(int l, int r) const{Monoid L = e1, R = e1;l += n, r += n;while(l < r){if(l&1) L = f(L, seg[l++]);if(r&1) R = f(seg[--r], R);l >>= 1, r >>= 1;}return f(L, R);}Monoid operator [] (int i) const {return seg[n+i];}template<typename C>int find_subtree(int i, const C &check, const Monoid &x, Monoid &M, bool type) const{while(i < n){Monoid nxt = type? f(seg[2*i+type], M) : f(M, seg[2*i+type]);if(check(nxt, x)) i = 2*i+type;else M = nxt, i = 2*i+(type^1);}return i-n;}template<typename C>int find_first(int l, const C &check, const Monoid &x) const{Monoid L = e1;int a = l+n, b = n+n;while(a < b){if(a&1){Monoid nxt = f(L, seg[a]);if(check(nxt, x)) return find_subtree(a, check, x, L, false);L = nxt, a++;}a >>= 1, b >>= 1;}return n;}template<typename C>int find_last(int r, const C &check, const Monoid &x) const{Monoid R = e1;int a = n, b = r+n;while(a < b){if(b&1 || a == 1){Monoid nxt = f(seg[--b], R);if(check(nxt, x)) return find_subtree(b, check, x, R, true);R = nxt;}a >>= 1, b >>= 1;}return -1;}};int main(){int N; cin >> N;vector<int> p(N), id(N);rep(i, N) {cin >> p[i]; id[--p[i]] = i;}vector<ll> A(N);rep(i, N) cin >> A[i];auto f = [](int a, int b) {return max(a, b);};auto c = [](int a, int b) {return a >= b;};Segment_Tree<int> seg(vector<int>(N, 0), f, 0);vector<ll> s(N+1, 0);rep(i, N) s[i+1] = s[i]+p[i]+1;rep(i, N){int m = id[i];int l = seg.find_last(m, c, 1)+1;int r = min(N-1, seg.find_first(m, c, 1)-1);ll ans = 0;//cout << l << ' ' << m << ' ' << r << '\n';if(r-m < m-l){rep2(j, m, r){ll S = s[j+1]-s[m+1];int L = l-1, R = m+1; //(L,R]while(R-L > 1){int M = (L+R)/2;if(S+s[m+1]-s[M] > A[i]) L = M;else R = M;}ans += m-R+1;}}else{rep3(j, m, l){ll S = s[m]-s[j];int L = m-1, R = r+1; //[L,R)while(R-L > 1){int M = (L+R)/2;if(S+s[M+1]-s[m] > A[i]) R = M;else L = M;}ans += L-m+1;}}seg.change(m, 1);cout << ans << '\n';}}