結果
問題 | No.1496 不思議な数え上げ |
ユーザー | tatananonano |
提出日時 | 2023-02-13 21:45:02 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 6,855 bytes |
コンパイル時間 | 5,502 ms |
コンパイル使用メモリ | 270,692 KB |
実行使用メモリ | 18,944 KB |
最終ジャッジ日時 | 2024-07-16 13:16:16 |
合計ジャッジ時間 | 15,369 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 3 TLE * 1 |
ソースコード
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")#pragma GCC optimize("Ofast")#pragma GCC optimize("unroll-loops")#include <vector>#include <algorithm>#include <cmath>#include <queue>#include <deque>#include <list>#include <unordered_map>#include <unordered_set>#include <iomanip>#include <set>#include <map>#include <ctime>#include <stack>#include <functional>#include <cstdio>#include <string>#include <iostream>#include <limits>#include <stdexcept>#include <numeric>#include <fstream>#include <chrono>#include <utility>#include <cassert>#include <random>#include <time.h>#include <bitset>using namespace std;#define overload4(_1, _2, _3, _4, name, ...) name#define rep0(a) for (ll _ = 0; _ < ll(a); ++_)#define rep1(i, n) for (ll i = 0; i < ll(n); ++i)#define rep2(i, s, n) for (ll i = ll(s); i < ll(n); ++i)#define rep3(i, s, n, d) for(ll i = ll(s); i < ll(n); i+=d)#define rep(...) overload4(__VA_ARGS__,rep3,rep2,rep1,rep0)(__VA_ARGS__)#define rrep0(a) for (ll _ = (a)-1; _ >= ll(0); -- _)#define rrep1(i, n) for (ll i = ll(n)-1; i >= 0; i--)#define rrep2(i, n, t) for (ll i = ll(n)-1; i >= (ll)t; i--)#define rrep3(i, n, t, d) for (ll i = ll(n)-1; i >= (ll)t; i-=d)#define drep(...) overload4(__VA_ARGS__,rrep3,rrep2,rrep1,rrep0)(__VA_ARGS__)typedef long long ll;typedef unsigned long long ull;typedef long double LD;typedef double D;typedef pair<ll,ll> P;typedef map<ll,ll> M;// /*#include <atcoder/all>using namespace atcoder;//using namespace internal;using mint =modint998244353;//using mint =modint1000000007;//using mint=static_modint<4649>;#define ip(x) atcoder::internal::is_prime_constexpr(x)istream &operator>>(istream &is, mint &a) { int v; cin >> v; a = v; return is; }ostream &operator<<(ostream &os, const mint &a) { return os << a.val(); }auto v_pow(ll n,ll base){vector<mint> v(n,1);rep(i,n-1){v[i+1]*=base*v[i];}return v;}// */template<typename T> istream &operator>>(istream &is, vector<T> &v) { for (auto &e : v) is >> e; return is; }template<typename T> ostream &operator<<(ostream &os, const vector<T> &v) { for (auto &e : v) os << e << ' '; return os; }template<class S, class T>istream &operator>>(istream &is, pair<S, T> &p) { return is >> p.first >> p.second; }template<class S, class T>ostream &operator<<(ostream &os, const pair<S, T> &p) { return os << '{' << p.first << ", " << p.second << '}'; }template<class S, class T, class U>istream &operator>>(istream &is, tuple<S, T, U> &t) { return is >> get<0>(t) >> get<1>(t) >> get<2>(t); }template<class S, class T, class U>ostream &operator<<(ostream &os, const tuple<S, T, U> &t) {return os << '{' << get<0>(t) << ", " << get<1>(t) << ", " << get<2>(t) << '}';}#define YES(n) cout << ((n) ? "YES" : "NO" ) << endl#define Yes(n) cout << ((n) ? "Yes" : "No" ) << endltemplate <typename F>ll binary_search(F check,ll ok,ll ng) {/*binary_search(bool_func,okな値,ngな値)*///しっかり区間内に...assert(check(ok));while(abs(ok-ng)>1){auto x=(ng+ok)/2;tie(ok,ng)=(check(x)?make_pair(x, ng):make_pair(ok, x));}return ok;}template <typename F>double binary_search_real(F check,double ok,double ng,ll iter = 100) {rep(iter) {double x=(ok+ng)/2;tie(ok,ng)=(check(x)?make_pair(x,ng):make_pair(ok,x));}return (ok+ng)/2;}void tatananonano() {ios::sync_with_stdio(false);std::cin.tie(nullptr);cout<< fixed << setprecision(10);}#define LL(...) ll __VA_ARGS__; IN(__VA_ARGS__)#define INT(...) int __VA_ARGS__; IN(__VA_ARGS__)#define STR(...) string __VA_ARGS__; IN(__VA_ARGS__)#define CHR(...) char __VA_ARGS__;IN(__VA_ARGS__)#define LDL(...) LD __VA_ARGS__;IN(__VA_ARGS__)#define vv(type, name, h, ...) \vector<vector<type>> name(h, vector<type>(__VA_ARGS__))#define vvv(type, name, h, w, ...) \vector<vector<vector<type>>> name( \h, vector<vector<type>>(w, vector<type>(__VA_ARGS__)))//#define MINT(...) mint __VA_ARGS__;IN(__VA_ARGS__)template <class T> void scan(T &a) { cin >> a; }void IN() {}template <class Head, class... Tail> void IN(Head &head, Tail &...tail) {scan(head);IN(tail...);}#define overload2(_1, _2, _3,name, ...) name#define out1(x) cout<<x<<'\n'#define out2(x,y) cout<<x<<" "<<y<<'\n'#define out3(x,y,z) cout<<x<<" "<<y<<" "<<z<<'\n'#define out4(x,y,z,w) cout<<x<<" "<<y<<" "<<z<<" "<<w<<'\n'#define out(...) overload4(__VA_ARGS__,out4,out3,out2,out1)(__VA_ARGS__)#define print1(x) cout<<x<<'\n'#define print2(x,n) cout<<fixed<<setprecision(n)<<x<<endl#define print3(x,n,empty) cout<<fixed<<setprecision(n)<<x<<" "#define print(...) overload2(__VA_ARGS__,print3,print2,print1)(__VA_ARGS__)#define bool_print(x,y1,y2) cout<<(x?y1:y2)<<'\n';#define all(x) (x).begin(),(x).end()#define MAX(a) *max_element(all(a));#define MIN(a) *min_element(all(a));#define pb push_back#define lb lower_bound#define ub upper_bound#define len(x) ll(x.size())#define uni(x) sort(all(x));x.erase(unique(all(x)),x.end())#define TFU(s) transform(all(s),begin(s),::toupper);//大文字にする#define TFL(s) transform(all(s),begin(s),::tolower);//小文字にする#define replace(s,a,A) replace(s,'a','A')//str(s)のaをAにする#define ROT(s,i) rotate(s.begin(),s.begin()+i,s.end())//sのi番目から後ろを前にする#define PQ priority_queue#define PQD PQ<P,vector<P>,greater<P>>//小さい順#define PQS PQ<ll,vec,greater<ll>>#define fi first#define se second#define bit(n,k) ((n>>k)&1LL)#define popcount(n) __builtin_popcountll(n)template<class T> inline bool chmax(T& a,T b){if(a < b){a=b;return 1;}return 0;}template<class T> inline bool chmin(T& a,T b){if(a > b){a=b;return 1;}return 0;}bool in_rect(ll i,ll j,ll h,ll w) {return 0 <= i and i < h and 0 <= j and j < w;}typedef vector<ll> vec;typedef vector<string> vs;typedef vector<vec> mat;const ll mod = 998244353;//const ll mod = 1000000007;const auto INF = (1LL<<(60));template <typename T, typename U>T ceil(T x, U y) {return (x > 0 ? (x + y - 1) / y : x / y);}template <typename T, typename U>T floor(T x, U y) {return (x > 0 ? x / y : (x - y + 1) / y);}int main(){tatananonano();LL(n);vec p(n);cin>>p;vec a(n);cin>>a;vec sum(n+1);vec rev(n);rep(i,n){sum[i+1]+=sum[i]+p[i];rev[--p[i]]=i;}set<ll> st;st.insert(-1);st.insert(n);rep(i,n){auto it=st.lb(rev[i]);ll right = *it;it--;ll left = *it;ll ans = 0;if(right-rev[i]<left-rev[i]){rep(r,rev[i],right){ll l=lb(all(sum),sum[r+1]-a[i])-sum.begin();chmax(l,left+1);chmin(l,rev[i]+1);ans+=rev[i]-l+1;}}else{rep(l,left+1,rev[i]+1){ll r=ub(all(sum),sum[l]+a[i])-sum.begin()-2;chmin(r,right-1);chmax(r,rev[i]-1);ans+=r-rev[i]+1;}}cout<<ans<<endl;st.insert(rev[i]);}}