結果
問題 | No.1496 不思議な数え上げ |
ユーザー | 沙耶花 |
提出日時 | 2021-04-30 23:17:46 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 267 ms / 3,000 ms |
コード長 | 1,512 bytes |
コンパイル時間 | 4,371 ms |
コンパイル使用メモリ | 256,860 KB |
最終ジャッジ日時 | 2025-01-21 04:37:29 |
ジャッジサーバーID (参考情報) |
judge2 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 39 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:69:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 69 | scanf("%d",&P[i]); | ~~~~~^~~~~~~~~~~~ main.cpp:73:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 73 | scanf("%lld",&A[i]); | ~~~~~^~~~~~~~~~~~~~
ソースコード
#include <stdio.h>#include <atcoder/all>#include <bits/stdc++.h>using namespace std;using namespace atcoder;using mint = modint1000000007;#define rep(i,n) for (int i = 0; i < (n); ++i)#define Inf 1000000000int N;vector<int> P;vector<long long> A;vector<long long> ans;void check(vector<pair<int,long long>> X,vector<pair<int,long long>> Y){rep(i,X.size()){if(X[i].first == Inf)continue;int ok = -1,ng = Y.size();while(ng-ok>1){int mid = (ok+ng)/2;bool f = true;if(Y[mid].first < X[i].first)f=false;if(Y[mid].second+X[i].second > A[X[i].first-1])f=false;if(f)ok = mid;else ng = mid;}ans[X[i].first-1] += ok+1;}}void dfs(int l,int r){//cout<<l<<','<<r<<endl;if(r-l==1){if(A[P[l]-1]>=P[l])ans[P[l]-1]++;return;}if(r-l==0)return;int m = (l+r)/2;// cout<<l<<','<<r<<endl;vector<pair<int,long long>> R(1,make_pair(P[m],P[m]));for(int i=m+1;i<r;i++){R.emplace_back(min(R.back().first,P[i]),R.back().second + P[i]);}//cout<<l<<','<<r<<endl;vector<pair<int,long long>> L(1,make_pair(P[m-1],P[m-1]));for(int i=m-2;i>=l;i--){L.emplace_back(min(L.back().first,P[i]),L.back().second + P[i]);}//cout<<l<<','<<r<<endl;check(R,L);check(L,R);//cout<<l<<','<<r<<endl;dfs(l,m);dfs(m,r);}int main(){cin>>N;P.resize(N),A.resize(N),ans.resize(N,0);rep(i,N){scanf("%d",&P[i]);}rep(i,N){scanf("%lld",&A[i]);}dfs(0,N);rep(i,N){printf("%lld\n",ans[i]);}return 0;}