QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#354339 | #7106. Infinite Parenthesis Sequence | Graphcity | WA | 536ms | 3956kb | C++20 | 1.6kb | 2024-03-15 10:14:26 | 2024-03-15 10:14:26 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rof(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
const int Maxn=1e5,inf=1e9+7;
int n,m,q; char s[Maxn+5];
int rk[Maxn+5],st[Maxn+5][20];
inline int Count(int l,int r)
{
int len=__lg(r-l+1);
return min(st[l][len],st[r-(1<<len)+1][len]);
}
inline ll Find(int k,int x)
{
int p=(x%m+m)%m,r=min(m-1,p+k);
ll res=Count(p,r)+1ll*n*((x-p)/m)+2*p;
// printf("%d %d: %d %d: %lld\n",k,x,p,r,res);
if(p+k>=m)
{
r=min(m-1,p+k-m);
res=min(res,Count(0,r)+1ll*n*((x-p)/m+1)-2*(m-p));
} return res+k;
}
inline int Get(int k,int x)
{
int l=-inf,r=inf;
while(l<r)
{
int mid=l+(r-l+1)/2;
if(Find(k,mid)<=x) l=mid; else r=mid-1;
} return l;
}
inline void Solve()
{
scanf("%s%d",s,&q),n=strlen(s); int flg=0;
m=0; For(i,0,n-1) if(s[i]=='(') rk[m++]=i;
if(!m) {while(q--) {int k,l,r; cin>>k>>l>>r; puts("0");} return;}
if(m==n) {while(q--) {int k,l,r; cin>>l>>l>>r; printf("%d\n",r-l+1);} return;}
if(m>n/2)
{
reverse(s,s+n),m=0,flg=1;
For(i,0,n-1) if(s[i]==')') rk[m++]=i;
}
For(i,0,m-1) st[i][0]=rk[i]-2*i;
For(j,1,19) for(int i=0;i+(1<<j)<=m;++i)
st[i][j]=min(st[i][j-1],st[i+(1<<j-1)][j-1]);
while(q--)
{
int k,l,r; cin>>k>>l>>r;
int b=Get(k,r),a=Get(k,l-1);
if(!flg) printf("%d\n",b-a);
else printf("%d\n",r-l+1-(b-a));
}
}
int main()
{
// freopen("1.in","r",stdin);
int T; cin>>T;
while(T--) Solve();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3904kb
input:
3 (()) 3 0 -3 2 1 -2 3 2 0 0 ))()( 3 0 -3 4 2 1 3 3 -4 -1 ))()(()( 4 1234 -5678 9012 123 -456 789 12 -34 56 1 -2 3
output:
3 3 0 4 1 1 7345 623 45 3
result:
ok 10 lines
Test #2:
score: -100
Wrong Answer
time: 536ms
memory: 3956kb
input:
5564 ()()(((() 16 0 -825489608 537105171 0 481386502 824237183 0 -32590250 515314371 0 -634830457 908018223 3 -494274112 299679416 125527658 81646800 208166552 632660143 -774899605 -551752339 4 -874787302 127206822 4 -102348267 122390255 2 -881139944 898929361 0 -656262874 -233671414 111787130 -5925...
output:
908396520 228567122 365269749 1028565787 529302353 84346503 148764844 667996083 149825682 1186712870 281727641 995600518 63752581 740373707 867951695 27044667 530591271 345487788 415550919 701803793 413364407 187916462 386485771 125057026 296666742 470522533 367131179 635722815 58970215 379425066 18...
result:
wrong answer 2nd lines differ - expected: '228567121', found: '228567122'