#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
vector<vector<int> > tree;
vector<lli> harray,larray;
const lli MAX=3*1e5+5;
int val(char c){
if(c=='(')return 1;
else if(c==')')return -1;
else return -1123214;
}
typedef pair<int,int> pii;
lli solve(vector<char>& chain){
int len=(int)chain.size();
map<int,int> freq;
vector<int> dp(MAX,0);
dp[0]=0;
int bul=0;
lli snc=0;
set<pii> dset;
map<int,set<pii> > ipf;
/*
freq ayarla
1'den n'e:
bul'dan küçük olan ilk elemanı bul = gind
ipf[bul]'da gind'den küçük olanları bul
bul'u arttır
* */
for (int i = 1; i <= len ; i++)
{
dp[i]=dp[i-1]+val(chain[i-1]);
if(ipf.find(dp[i])==ipf.end()){
ipf[dp[i]]=set<pii>();
}
ipf[dp[i]].insert(pii(i,ipf[dp[i]].size()));
dset.insert(pii(dp[i],i));
}
for (int i = 0; i <= 2; i++)
{
//cout <<"i: "<<i<<" ";
for (auto c: ipf[i])
{
//cout << c.first<<"-"<<c.second<<" ";
}
//cout<<"\n";
}
map<int,int> freqRem;
for (int i = 1; i <=len ; i++)
{
int gind=0;
set<pii>::iterator it=dset.lower_bound(pii(bul-1,-1));
if(it==dset.end()){
gind=len;
}
else if(it->first!=bul-1)gind=len;
else gind=it->second;
//cout <<"gind: "<< gind<<"\n";
//gind'den küçük eşitleri bul
set<pii>::iterator git=ipf[bul].lower_bound(pii(gind+1,-1));
if(git==ipf[bul].begin()){
snc+=0;//:)
}
else{
git--;
//cout << "buldu: "<<git->first<<"-"<<git->second<<"\n";
snc+=git->second+1-freqRem[bul];
}
//cout <<snc<<" snc \n";
bul+=val(chain[i-1]);
set<pii>::iterator sil=ipf[dp[i]].lower_bound(pii(i,-1));
ipf[dp[i]].erase(sil);
if(freqRem.find(dp[i])==freqRem.end())freqRem[dp[i]]=0;
freqRem[dp[i]]++;
}
return snc;
}
/*
4
(())
*/
int main(){
int n;
cin>>n;
vector<char> chain(n,0);
for (int i = 0; i < n; i++)
{
cin>>chain[i];
}
for (int i = 0; i < n-1; i++)
{
int a,b;
cin>>a>>b;
}
lli snc=0;
snc+=solve(chain);
reverse(chain.begin(),chain.end());
snc+=solve(chain);
cout << snc;
return 0;
}
Compilation message
zagrade.cpp: In function 'lli solve(std::vector<char>&)':
zagrade.cpp:41:13: warning: variable 'c' set but not used [-Wunused-but-set-variable]
for (auto c: ipf[i])
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
1624 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
891 ms |
30276 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
1624 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
