oj.uz

Submission #66368

# Submission time Handle Problem Language Result Execution time Memory
66368 2018-08-10T10:29:37 Z quoriess Zagrade (COI17_zagrade) C++14
30 / 100
 1968 ms 44268 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 1620 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 851 ms 30052 KB Output is correct
2 Correct 1198 ms 41556 KB Output is correct
3 Correct 955 ms 41556 KB Output is correct
4 Correct 1124 ms 41556 KB Output is correct
5 Correct 949 ms 41556 KB Output is correct
6 Correct 1047 ms 41556 KB Output is correct
7 Correct 905 ms 41556 KB Output is correct
8 Correct 1061 ms 41556 KB Output is correct
9 Correct 883 ms 41556 KB Output is correct
10 Correct 1968 ms 44268 KB Output is correct
11 Correct 996 ms 44268 KB Output is correct

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 1620 KB Output isn't correct
2 Halted 0 ms 0 KB -