Submission #66354

#TimeUsernameProblemLanguageResultExecution timeMemory
66354quoriessZagrade (COI17_zagrade)C++14
0 / 100
849 ms30132 KiB
#include <bits/stdc++.h> using namespace std; typedef long long int lli; vector<vector<int> > tree; 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)); } 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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...