結果
問題 | No.457 (^^*) |
ユーザー |
|
提出日時 | 2016-12-08 22:15:42 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 3 ms / 2,000 ms |
コード長 | 927 bytes |
コンパイル時間 | 462 ms |
コンパイル使用メモリ | 55,040 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-11-28 15:32:49 |
合計ジャッジ時間 | 1,148 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 20 |
ソースコード
#include <vector> #include <algorithm> #include <cstdio> #include <cstring> using namespace std; int solve(char *s,int len){ vector<int>al; vector<int>ar; vector<int>ah(len); vector<int>ast; for(int i=0;i<len;i++){ if(s[i]=='('){ al.push_back(i); }else if(s[i]==')'){ ar.push_back(i); }else if(s[i]=='^'){ ah[i]++; }else if(s[i]=='*'){ ast.push_back(i); } } for(int i=1;i<len;i++)ah[i]+=ah[i-1]; int ret=0; auto ist=ast.begin(); auto ir=ar.begin(); for(auto &l:al){ int hidx=lower_bound(ah.begin()+l,ah.end(),ah[l]+2)-ah.begin(); ist=lower_bound(ist,ast.end(),hidx); if(ist==ast.end())break; ret+=ar.end()-(ir=lower_bound(ir,ar.end(),*ist)); } return ret; } char s[10001]; int main(){ scanf("%s",s); int len=strlen(s); printf("%d ",solve(s,len)); reverse(s,s+len); for(int i=0;i<len;i++){ if(s[i]=='(')s[i]=')'; else if(s[i]==')')s[i]='('; } printf("%d\n",solve(s,len)); }