fork download 
  1. /*
  2. * @Author: hungeazy
  3. * @Date:   2025-10-21 15:08:08
  4. * @Last Modified by:   hungeazy
  5. * @Last Modified time: 2025-10-22 21:27:26
  6. */
  7. #include <bits/stdc++.h>
  8. #include <ext/pb_ds/assoc_container.hpp> 
  9. #include <ext/pb_ds/tree_policy.hpp> 
  10. // #pragma GCC optimize("O3")  
  11. // #pragma GCC optimize("unroll-loops")  
  12. // #pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")  
  13. using namespace std;
  14. using namespace __gnu_pbds; 
  15. bool M1;
  16. #define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
  17. #define int long long
  18. #define ll long long 
  19. #define ull unsigned long long
  20. #define sz(x) x.size()
  21. #define sqr(x) (1LL * (x) * (x))
  22. #define all(x) x.begin(), x.end()
  23. #define fill(f,x) memset(f,x,sizeof(f))
  24. #define FOR(i,l,r) for(int i=l;i<=r;i++)
  25. #define FOD(i,r,l) for(int i=r;i>=l;i--)
  26. #define debug(x) cout << #x << " = " << x << '\n'
  27. #define ii pair<int,int>
  28. #define iii pair<int,ii>
  29. #define di pair<ii,ii>
  30. #define vi vector<int>
  31. #define vii vector<ii>
  32. #define mii map<int,int>
  33. #define fi first
  34. #define se second
  35. #define pb push_back
  36. #define MOD 1000000007
  37. #define __lcm(a,b) (1ll * ((a) / __gcd((a), (b))) * (b))
  38. #define YES cout << "YES\n"
  39. #define NO cout << "NO\n"
  40. #define MASK(i) (1LL << (i))
  41. #define c_bit(i) __builtin_popcountll(i)
  42. #define BIT(x,i) ((x) & MASK(i))
  43. #define SET_ON(x,i) ((x) | MASK(i))
  44. #define SET_OFF(x,i) ((x) & ~MASK(i))
  45. #define oo 1e18
  46. #define name ""
  47. #define endl '\n'
  48. #define memory() cerr << abs(&M2-&M1)/1024.0/1024 << " MB" << endl
  49. #define time() cerr << endl << "-------------Time:" << 1000.0 * clock() / CLOCKS_PER_SEC << "ms." << endl
  50. template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
  51. template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }
  52. template <class T> using ordered_set = tree <T, null_type, less_equal <T>, rb_tree_tag,tree_order_statistics_node_update>;
  53. const int N = (int)4e6+10;
  54. int n;
  55. string s;
  56.  
  57. namespace sub1 {
  58.  
  59. 	bool approved() {
  60. 		return n <= 500;
  61. 	}
  62.  
  63. 	bool check(string s) 
  64. 	{
  65. 		stack<char> st;
  66. 		for (char c : s)
  67. 			if (c == '(') st.push(c);
  68. 			else 
  69. 			{
  70. 				if (st.empty()) return false; 
  71. 				st.pop();
  72. 			}
  73. 		return st.empty();
  74. 	}
  75.  
  76. 	void solve(void)
  77. 	{
  78. 		int ans = 0;
  79. 		FOR(i,0,n-1)
  80. 			FOR(j,i,n-1)
  81. 			{
  82. 				string t = s;
  83. 				reverse(t.begin()+i,t.begin()+j+1);
  84. 				ans += check(t);
  85. 			}
  86. 		cout << ans;
  87. 	}
  88.  
  89. }
  90.  
  91. namespace sub3 {
  92.  
  93. 	const int M = (int)1e5+10;
  94. 	int pre[M],f[M][20],lo[M];
  95.  
  96. 	bool approved() {
  97. 		return n <= 15e3;
  98. 	}
  99.  
  100. 	void init(){
  101. 		lo[1] = 0;
  102. 		FOR(i,2,M-10) lo[i] = lo[i/2]+1;
  103. 		FOR(j,1,lo[n])
  104. 			FOR(i,0,n-MASK(j))
  105. 				f[i][j] = max(f[i][j-1],f[i+MASK(j-1)][j-1]);
  106. 	}
  107.  
  108. 	int getMax(int l, int r)
  109. 	{
  110. 		int k = lo[r-l+1];
  111. 		return max(f[l][k],f[r-MASK(k)+1][k]); 
  112. 	}
  113.  
  114. 	void solve(void)
  115. 	{
  116. 		FOR(i,1,n) pre[i] = pre[i-1]+(s[i-1] == '(' ? 1 : -1);
  117. 		FOR(i,0,n-1) f[i][0] = pre[i];
  118. 		init();
  119. 		int ans = 0;
  120. 		FOR(l,1,n)
  121. 			FOR(r,l,n)
  122. 			{
  123. 				int val = getMax(l-1,r-1);
  124. 				if (pre[r]+pre[l-1]-val >= 0) ans++;
  125. 			}
  126. 		cout << ans;
  127. 	}
  128.  
  129. }
  130.  
  131. namespace sub4 {
  132.  
  133. 	int pre[N];
  134. 	vi vec;
  135.  
  136. 	bool approved() {
  137. 		return n <= 3e5;
  138. 	}
  139.  
  140. 	struct FenwickTree {
  141. 		vi bit;
  142. 		int n;
  143. 		FenwickTree() {};
  144. 		FenwickTree(int _n):
  145. 			n(_n), bit(_n+1,0) {};
  146. 		void init() {
  147. 			FOR(i,1,n) bit[i] = 0;
  148. 		}
  149. 		void update(int id, int val)
  150. 		{
  151. 			while (id <= n)
  152. 			{
  153. 				bit[id] += val;
  154. 				id += (id&(-id));
  155. 			}
  156. 		}
  157. 		int get(int id)
  158. 		{
  159. 			int ans = 0;
  160. 			while (id)
  161. 			{
  162. 				ans += bit[id];
  163. 				id -= (id&(-id));
  164. 			}
  165. 			return ans;
  166. 		}
  167. 		int get(int l, int r) {
  168. 			if (l > r) return 0;
  169. 			return get(r)-get(l-1);
  170. 		}
  171. 	} BIT;
  172.  
  173. 	int getIndex(int x) {
  174. 		return lower_bound(all(vec),x)-vec.begin()+1;
  175. 	}
  176.  
  177. 	int DnC(int l, int r)
  178. 	{
  179. 		if (l == r) return 0;
  180. 		int mid = (l+r)>>1, ans = 0;
  181. 		ans += DnC(l,mid); ans += DnC(mid+1,r);
  182. 		vii left,right;
  183. 		int mx = -oo;
  184. 		FOD(i,mid,l)
  185. 		{
  186. 			maximize(mx,pre[i+1]);
  187. 			left.pb({mx,pre[i]});
  188. 		}
  189. 		mx = -oo;
  190. 		FOR(i,mid+1,r)
  191. 		{
  192. 			maximize(mx,pre[i]);
  193. 			right.pb({mx,pre[i]});
  194. 		}
  195. 		sort(all(left)); sort(all(right));
  196. 		int len = sz(vec);
  197. 		BIT = FenwickTree(len);
  198. 		int L = 0;
  199. 		for (auto x : right)
  200. 		{
  201. 			auto [mx,valR] = x;
  202. 			while (L < sz(left) and left[L].fi <= mx)
  203. 			{
  204. 				int valL = left[L].se, idx = getIndex(valL);
  205. 				BIT.update(idx,1);
  206. 				++L;
  207. 			}
  208. 			int cur = mx-valR, idx = getIndex(cur);
  209. 			ans += BIT.get(idx,len);
  210. 		}
  211. 		BIT.init();
  212. 		int R = 0;
  213. 		for (auto x : left)
  214. 		{
  215. 			auto [mx,valL] = x;
  216. 			while (R < sz(right) and right[R].fi < mx)
  217. 			{
  218. 				int valR = right[R].se, idx = getIndex(valR);
  219. 				BIT.update(idx,1);
  220. 				++R;
  221. 			}
  222. 			int cur = mx-valL, idx = getIndex(cur);
  223. 			ans += BIT.get(idx,len); 
  224. 		}
  225. 		return ans;
  226. 	}
  227.  
  228. 	void solve(void)
  229. 	{
  230. 		FOR(i,1,n) pre[i] = pre[i-1]+(s[i-1] == '(' ? 1 : -1);
  231. 		FOR(i,1,n) vec.pb(pre[i]);
  232. 		sort(all(vec));
  233. 		vec.erase(unique(all(vec)),vec.end());
  234. 		int ans = DnC(0,n);
  235. 		cout << ans;
  236. 	}
  237.  
  238. }
  239.  
  240. namespace sub5 {
  241.  
  242. 	const int base = 4e6;
  243. 	int pre[N],ans,sum[N<<1];
  244.  
  245. 	void DnC(int l, int r)
  246. 	{
  247. 		if (l == r) return;
  248. 		int mid = (l+r)>>1, cnt = 0, pos = mid+1;
  249. 		int mx = 0, in = 0;
  250. 		FOD(i,mid,l)
  251. 		{
  252. 			maximize(mx,pre[i-1]);
  253. 			int cur = mx-pre[i-1];
  254. 			while (in < cur)
  255. 			{
  256. 				cnt -= sum[in+base];
  257. 				in++;
  258. 			}
  259. 			while (in > cur)
  260. 			{
  261. 				in--;
  262. 				cnt += sum[in+base];
  263. 			}
  264. 			while (pos <= r and pre[pos-1] <= mx)
  265. 			{
  266. 				cnt += (pre[pos] >= in);
  267. 				sum[pre[pos]+base]++;
  268. 				pos++;
  269. 			}
  270. 			ans += cnt;
  271. 		}
  272. 		while (pos > mid) 
  273. 		{
  274. 			sum[pre[pos]+base] = 0;
  275. 			pos--;
  276. 		}
  277. 		mx = 0, in = 0, cnt = 0, pos = mid;
  278. 		FOR(i,mid+1,r)
  279. 		{
  280. 			maximize(mx,pre[i-1]);
  281. 			int cur = mx-pre[i];
  282. 			while (in < cur)
  283. 			{
  284. 				cnt -= sum[in+base];
  285. 				in++;
  286. 			}
  287. 			while (in > cur)
  288. 			{
  289. 				in--;
  290. 				cnt += sum[in+base];
  291. 			}
  292. 			while (pos >= l and pre[pos-1] < mx)
  293. 			{
  294. 				cnt += (pre[pos-1] >= in);
  295. 				sum[pre[pos-1]+base]++;
  296. 				pos--;
  297. 			}
  298. 			ans += cnt;
  299. 		}
  300. 		while (pos <= mid)
  301. 		{
  302. 			sum[pre[pos-1]+base] = 0;
  303. 			pos++;
  304. 		}
  305. 		DnC(l,mid);
  306. 		DnC(mid+1,r);
  307. 	}
  308.  
  309. 	void solve(void)
  310. 	{
  311. 		FOR(i,1,n) pre[i] = pre[i-1]+(s[i-1] == '(' ? 1 : -1);
  312. 		ans = n;
  313. 		DnC(1,n);
  314. 		cout << ans;
  315. 	}
  316.  
  317. }
  318.  
  319. bool M2;
  320. signed main()
  321. {
  322.     fast;
  323.     if (fopen(name".inp","r"))
  324.     {
  325.     	freopen(name".inp","r",stdin);
  326.     	freopen(name".out","w",stdout);
  327.     }
  328.     cin >> n >> s;
  329.     if (sub1::approved()) return sub1::solve(), time(), memory(), 0;
  330.     if (sub3::approved()) return sub3::solve(), time(), memory(), 0;
  331.     // if (sub4::approved()) return sub4::solve(), time(), memory(), 0;
  332.     sub5::solve();
  333.     time();
  334.     memory();
  335.     return 0;
  336. }
  337. // ██░ ██  █    ██  ███▄    █   ▄████
  338. //▓██░ ██▒ ██  ▓██▒ ██ ▀█   █  ██▒ ▀█▒
  339. //▒██▀▀██░▓██  ▒██░▓██  ▀█ ██▒▒██░▄▄▄░
  340. //░▓█ ░██ ▓▓█  ░██░▓██▒  ▐▌██▒░▓█  ██▓
  341. //░▓█▒░██▓▒▒█████▓ ▒██░   ▓██░░▒▓███▀▒
  342. // ▒ ░░▒░▒░▒▓▒ ▒ ▒ ░ ▒░   ▒ ▒  ░▒   ▒
  343. // ▒ ░▒░ ░░░▒░ ░ ░ ░ ░░   ░ ▒░  ░   ░
  344. // ░  ░░ ░ ░░░ ░ ░    ░   ░ ░ ░ ░   ░
  345. // ░  ░  ░   ░              ░       ░
Success #stdin #stdout #stderr 0.01s 5912KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
stderr 
-------------Time:7.392ms.
138.857 MB
https://ideone.com/fz7a0s
language:
C++14 (gcc 8.3)
created:
9 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!