Submission #13080323

---

Source Code Expand

#pragma GCC optimize("O3")
#pragma GCC target("sse4")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const double PI=acos(-1.0);
#define t1(x)             cerr<<#x<<"="<<x<<endl
#define t2(x, y)          cerr<<#x<<"="<<x<<" "<<#y<<"="<<y<<endl
#define t3(x, y, z)       cerr<<#x<<"=" <<x<<" "<<#y<<"="<<y<<" "<<#z<<"="<<z<<endl
#define t4(a,b,c,d)       cerr<<#a<<"="<<a<<" "<<#b<<"="<<b<<" "<<#c<<"="<<c<<" "<<#d<<"="<<d<<endl
#define t5(a,b,c,d,e)     cerr<<#a<<"="<<a<<" "<<#b<<"="<<b<<" "<<#c<<"="<<c<<" "<<#d<<"="<<d<<" "<<#e<<"="<<e<<endl
#define t6(a,b,c,d,e,f)   cerr<<#a<<"="<<a<<" "<<#b<<"="<<b<<" "<<#c<<"="<<c<<" "<<#d<<"="<<d<<" "<<#e<<"="<<e<<" "<<#f<<"="<<f<<endl
#define GET_MACRO(_1,_2,_3,_4,_5,_6,NAME,...) NAME
#define tr(...) GET_MACRO(__VA_ARGS__,t6,t5, t4, t3, t2, t1)(__VA_ARGS__)
#define __ freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
#define fastio() ios::sync_with_stdio(0);cin.tie(0)
#define MEMS(x,t) memset(x,t,sizeof(x));
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
/*-------------------------------------------------------------------------------------------------------------------------------------*/
//#define MOD 1000000007
#define endl "\n" 
#define int long long

#define ld long double
/*-------------------------------------------------------------------------------------------------------------------------------------*/


struct dat
{
	//Use required attributes
	int mn;
	int idx2;
	//Default Values
	dat() : mn(-1e9),idx2(-1) {};
};

struct SegTree
{
	int N;
	vector<dat> st;
	vector<bool> cLazy;
	vector<int> lazy;

	void init(int n)
	{
		N = n;
		st.resize(4 * N + 5);
		cLazy.assign(4 * N + 5, false);
		lazy.assign(4 * N + 5, 0);
	}
	//Write reqd merge functions
	void merge(dat &cur, dat &l, dat &r) 
	{
		if(l.mn>=r.mn)
		{
			cur.mn=l.mn;
			cur.idx2=l.idx2;
		}
		else
		{
			cur.mn=r.mn;
			cur.idx2=r.idx2;
		}
	}
	
	//	Handle lazy propagation appriopriately
	// 	think what should happen if clazy[2*node] is already 1 before propagate is called
	void propagate(int node, int L, int R)
	{
		if(L != R)
		{
			cLazy[node*2] = 1;
			cLazy[node*2 + 1] = 1;
			lazy[node*2] = lazy[node];
			lazy[node*2 + 1] = lazy[node]; 
		}
		st[node].mn = lazy[node];
		cLazy[node] = 0;
	}

	
	dat Query(int node, int L, int R, int i, int j)
	{
		if(cLazy[node])
			propagate(node, L, R);
		if(j<L || i>R)
			return dat();
		if(i<=L && R<=j)
			return st[node];
		int M = (L + R)/2;
		dat left=Query(node*2, L, M, i, j);
		dat right=Query(node*2 + 1, M + 1, R, i, j);
		dat cur;
		merge(cur, left, right);
		return cur;
	}

	dat pQuery(int node, int L, int R, int pos)
	{
		if(cLazy[node])
			propagate(node, L, R);
		if(L == R)
			return st[node];
		int M = (L + R)/2;
		if(pos <= M)
			return pQuery(node*2, L, M, pos);
		else
			return pQuery(node*2 + 1, M + 1, R, pos);
	}	

	

	void pUpdate(int node, int L, int R, int pos, int val)
	{
		if(cLazy[node])
			propagate(node, L, R);
		if(L == R)
		{
			st[node].mn=val;
			st[node].idx2=L;
			return;
		}
		int M = (L + R)/2;
		if(pos <= M)
			pUpdate(node*2, L, M, pos, val);
		else
			pUpdate(node*2 + 1, M + 1, R, pos, val);
		merge(st[node], st[node*2], st[node*2 + 1]);
	}

	dat query(int pos)
	{
		return pQuery(1, 1, N, pos);
	}

	dat query(int l, int r)
	{
		return Query(1, 1, N, l, r);
	}

	void update(int pos, int val)
	{
		pUpdate(1, 1, N, pos, val);
	}

	
};

struct info
{
	int idx,mi,sum;
};
bool cmp(info a,info b)
{
	return a.mi<b.mi;
}
SegTree st;
int32_t main()
{
	fastio();
	int n;
	cin>>n;
	st.init(n+5);
	string s[n];
	info inf[n];
	for(int i=0;i<n;i++)
	{
		cin>>s[i];
		int mi=0;
		int cur=0;
		for(int j=0;j<s[i].length();j++)
		{
			if(s[i][j]=='(')cur++;
			else cur--;
			mi=min(mi,cur);
		}
		inf[i]={i,mi,cur};
	}
	sort(inf,inf+n,cmp);
	int temp[n];
	for(int i=0;i<n;i++)
	{
		temp[i]=inf[i].mi;
		st.update(i+1,inf[i].sum);
	}	
	string str;
	int cur=0;
	for(int cc=0;cc<n;cc++)
	{
		if(cur<0)
		{
			cout<<"No\n";
			return 0;
		}
		int pt=lower_bound(temp,temp+n,-cur)-temp;
		dat tmp=st.query(pt+1,n);
		st.update(tmp.idx2,-1000000000);
		cur+=tmp.mn;
	}
	if(cur==0)
	{
		cout<<"Yes\n";
	}
	else
	{
		cout<<"No\n";
	}
}

Submission Info

Compile Error

./Main.cpp: In function ‘int32_t main()’:
./Main.cpp:171:16: warning: comparison of integer expressions of different signedness: ‘long long int’ and ‘std::__cxx11::basic_string<char>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  171 |   for(int j=0;j<s[i].length();j++)
      |               ~^~~~~~~~~~~~~~

Judge Result