Submission #3246161
Source Code Expand
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
#include<queue>
#include<cmath>
#include<cstdlib>
#include<map>
#define LL long long
#define LD long double
using namespace std;
const int NN=250000 +117;
const int MM= +117;
int read(){
int fl=1,x;char c;
for(c=getchar();(c<'0'||c>'9')&&c!='-';c=getchar());
if(c=='-'){fl=-1;c=getchar();}
for(x=0;c>='0'&&c<='9';c=getchar())
x=(x<<3)+(x<<1)+c-'0';
return x*fl;
}
void open(){
freopen("99f.in","r",stdin);
//freopen(".out","w",stdout);
}
void close(){
fclose(stdin);
fclose(stdout);
}
int m,n;
map<pair<LL,LL>,int> a;
char s[NN]={};
LL mod[2]={998244353,2281701377};
LL ksm(LL a,LL b,LL mod){
LL ret=1;
while(b){
if(b&1){
ret*=a;
ret%=mod;
}
a*=a;
a%=mod;
b>>=1;
}
return ret;
}
inline void mop(LL &x,LL y,LL mod){
x=(x+y>=mod?x+y-mod:x+y);
}
int main(){
//open();
n=read();
scanf("%s",s);
LL res[2]={0,0};
LL rev[2];
rev[0]=ksm(mod[0],mod[1]-2,mod[1]);
rev[1]=ksm(mod[1],mod[0]-2,mod[0]);
LL p[2]={1,1};
for(int i=0;i<n;++i){
if(s[i]=='+'){
for(int i=0;i<2;++i){
mop(res[i],p[i],mod[i]);
}
}
else if(s[i]=='-'){
for(int i=0;i<2;++i){
mop(res[i],mod[i]-p[i],mod[i]);
}
}
else if(s[i]=='<'){
for(int i=0;i<2;++i){
p[i]*=rev[i^1];
p[i]%=mod[i];
}
}
else if(s[i]=='>'){
for(int i=0;i<2;++i){
p[i]*=mod[i^1];
p[i]%=mod[i];
}
}
}
p[0]=1;
p[1]=1;
LL tp[2]={0,0};
LL ans=0;
for(int i=0;i<n;++i){
a[make_pair((tp[0]+p[0]*res[0])%mod[0],(tp[1]+p[1]*res[1])%mod[1])]++;;
if(s[i]=='+'){
for(int i=0;i<2;++i){
mop(tp[i],p[i],mod[i]);
}
}
else if(s[i]=='-'){
for(int i=0;i<2;++i){
mop(tp[i],mod[i]-p[i],mod[i]);
}
}
else if(s[i]=='<'){
for(int i=0;i<2;++i){
p[i]*=rev[i^1];
p[i]%=mod[i];
}
}
else if(s[i]=='>'){
for(int i=0;i<2;++i){
p[i]*=mod[i^1];
p[i]%=mod[i];
}
}
ans+=a[make_pair(tp[0],tp[1])];
}
printf("%lld\n",ans);
close();
return 0;
}
Submission Info
Submission Time
2018-09-23 01:44:24+0900
Task
C - Minimization
User
Hercier
Language
C++14 (GCC 5.4.1)
Score
0
Code Size
2131 Byte
Status
WA
Exec Time
4 ms
Memory
256 KB
Compile Error
./Main.cpp: In function ‘void open()’:
./Main.cpp:24:29: warning: ignoring return value of ‘FILE* freopen(const char*, const char*, FILE*)’, declared with attribute warn_unused_result [-Wunused-result]
freopen("99f.in","r",stdin);
^
./Main.cpp: In function ‘int main()’:
./Main.cpp:56:15: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%s",s);
^
Judge Result
Set Name
Sample
All
Score / Max Score
0 / 0
0 / 300
Status
Set Name
Test Cases
Sample
sample1.txt, sample2.txt, sample3.txt
All
sample1.txt, sample2.txt, sample3.txt, 1.txt, 10.txt, 2.txt, 3.txt, 4.txt, 5.txt, 6.txt, 7.txt, 8.txt, 9.txt, sample1.txt, sample2.txt, sample3.txt
Case Name
Status
Exec Time
Memory
1.txt
WA
3 ms
256 KB
10.txt
WA
4 ms
256 KB
2.txt
WA
4 ms
256 KB
3.txt
WA
3 ms
256 KB
4.txt
WA
4 ms
256 KB
5.txt
WA
4 ms
256 KB
6.txt
WA
4 ms
256 KB
7.txt
WA
1 ms
256 KB
8.txt
WA
4 ms
256 KB
9.txt
WA
1 ms
256 KB
sample1.txt
WA
1 ms
256 KB
sample2.txt
WA
1 ms
256 KB
sample3.txt
WA
1 ms
256 KB