Submission #66368

#	Time	Username	Problem	Language	Result	Execution time	Memory
66368		quoriess	Zagrade (COI17_zagrade)	C++14	30 / 100	1968 ms	44268 KiB

zagrade

#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]]++;
		dset.erase(pii(dp[i],i));
	}
	return snc;
	
}
/*
4
(())
*/
int main(){
	int n;
	cin>>n;
	vector<char> chain(n,0);
	/*srand(time(0));
	for (int i = 0; i < n; i++)
	{
		chain.push_back(rand()%2?'(':')');
	}*/
	for (int i = 0; i < n; i++)
	{
		cin>>chain[i];
	}
	for (int i = 0; i < n-1; i++)
	{
		int a,b;
		cin>>a>>b;
	}
	/*for (int i = 0; i < n; i++)
	{
	}
	
	for (int i = n-1; i >=0; i--)
	{
		//cout << chain[i];
	}*/
	//cout<<"\n";
	lli snc=0;
	snc+=solve(chain);
	reverse(chain.begin(),chain.end());
	snc+=solve(chain);
	cout << snc;
	return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 30 / 30
• Subtask 3: 0 / 60