ZOJ 3726 RMQ+二分法

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5072
ゾーンマッチの話題
通過率が一番高い問題は半分以下でOKです. そしてWAは思い切って他にint不要long long WA
久しぶりにRMQのデバッグも時間がかかりました.
up per-boundはxより大きい一番目の数の下付きです.最大はもちろんendの位置に戻ります.
注意したいのですが、印刷が必要な枚数はxです.             s[i]=#include <cstdio> #include <cstring> #include <algorithm> #include <queue> #include <iostream> #include <cmath> using namespace std; const int MAXN = 1e5+100; #define IN(s) freopen(s,"r",stdin) #define ll long long #define ull unsigned long long const ll INF = ((ull)(-1))>>1; ll s[MAXN],p[MAXN],tot[MAXN]; int n,m; ll d[20]; ll st[MAXN][20]; void init() { for(int i=0;i<n;i++)st[i][0]=tot[i+1]; int k = (int)( log(double(n*1.0)/log(2.0)) ) +1; for(int j=1;j<k;j++) for(int i=0;i<n;i++) { if(i + d[j-1]-1 <n) { st[i][j] = min( st[i][j-1], st[i+d[j-1]][j-1] ); } else break; } } void query(int q) { int y=n-1; for(int i=0;i<q;i++) { int x,k; scanf("%d",&x); int id= upper_bound(s+1,s+1+n,x)-(s+1); if(id>=n) { printf("%lld
",p[n]*x); continue; } ll ans=INF; ans=min(ans,p[id]*x); k=int( log(double(y-id+1)/log(2.0)) ); ans=min(ans,min(st[id][k],st[y-d[k]+1][k])); printf("%lld
",ans); } } int main() { //IN("zoj3726.txt"); d[0]=1; for(int i=1;i<21;i++)d[i]=2*d[i-1]; int ncase; scanf("%d",&ncase); while(ncase--) { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { scanf("%lld%lld",&s[i],&p[i]); tot[i]=s[i]*p[i]; } init(); query(m); } return 0; } 著作権声明:このブログのオリジナル記事.ブログは、同意なしに転載してはいけません.