fork download
copy 
  1. /*
  2. * @Author: hungeazy
  3. * @Date:   2025-10-21 15:08:08
  4. * @Last Modified by:   hungeazy
  5. * @Last Modified time: 2025-10-22 09:34:04
  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)1e5+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. 	int pre[N],f[N][20],lo[N];
  94.  
  95. 	bool approved() {
  96. 		return n <= 15e3;
  97. 	}
  98.  
  99. 	void init(){
  100. 		lo[1] = 0;
  101. 		FOR(i,2,N-10) lo[i] = lo[i/2]+1;
  102. 		FOR(j,1,lo[n])
  103. 			FOR(i,0,n-MASK(j))
  104. 				f[i][j] = max(f[i][j-1],f[i+MASK(j-1)][j-1]);
  105. 	}
  106.  
  107. 	int getMax(int l, int r)
  108. 	{
  109. 		int k = lo[r-l+1];
  110. 		return max(f[l][k],f[r-MASK(k)+1][k]); 
  111. 	}
  112.  
  113. 	void solve(void)
  114. 	{
  115. 		FOR(i,1,n) pre[i] = pre[i-1]+(s[i-1] == '(' ? 1 : -1);
  116. 		FOR(i,0,n-1) f[i][0] = pre[i];
  117. 		init();
  118. 		int ans = 0;
  119. 		FOR(l,1,n)
  120. 			FOR(r,l,n)
  121. 			{
  122. 				int val = getMax(l-1,r-1);
  123. 				if (pre[r]+pre[l-1]-val >= 0) ans++;
  124. 			}
  125. 		cout << ans;
  126. 	}
  127.  
  128. }
  129.  
  130. namespace sub4 {
  131.  
  132. 	int pre[N];
  133. 	vi vec;
  134.  
  135. 	bool approved() {
  136. 		return n <= 3e5;
  137. 	}
  138.  
  139. 	struct FenwickTree {
  140. 		vi bit;
  141. 		int n;
  142. 		FenwickTree() {};
  143. 		FenwickTree(int _n):
  144. 			n(_n), bit(_n+1,0) {};
  145. 		void init() {
  146. 			FOR(i,1,n) bit[i] = 0;
  147. 		}
  148. 		void update(int id, int val)
  149. 		{
  150. 			while (id <= n)
  151. 			{
  152. 				bit[id] += val;
  153. 				id += (id&(-id));
  154. 			}
  155. 		}
  156. 		int get(int id)
  157. 		{
  158. 			int ans = 0;
  159. 			while (id)
  160. 			{
  161. 				ans += bit[id];
  162. 				id -= (id&(-id));
  163. 			}
  164. 			return ans;
  165. 		}
  166. 		int get(int l, int r) {
  167. 			if (l > r) return 0;
  168. 			return get(r)-get(l-1);
  169. 		}
  170. 	} BIT;
  171.  
  172. 	int getIndex(int x) {
  173. 		return lower_bound(all(vec),x)-vec.begin()+1;
  174. 	}
  175.  
  176. 	int DnC(int l, int r)
  177. 	{
  178. 		if (l == r) return 0;
  179. 		int mid = (l+r)>>1, ans = 0;
  180. 		ans += DnC(l,mid); ans += DnC(mid+1,r);
  181. 		vii left,right;
  182. 		int mx = -oo;
  183. 		FOD(i,mid,l)
  184. 		{
  185. 			maximize(mx,pre[i+1]);
  186. 			left.pb({mx,pre[i]});
  187. 		}
  188. 		mx = -oo;
  189. 		FOR(i,mid+1,r)
  190. 		{
  191. 			maximize(mx,pre[i]);
  192. 			right.pb({mx,pre[i]});
  193. 		}
  194. 		sort(all(left)); sort(all(right));
  195. 		int len = sz(vec);
  196. 		BIT = FenwickTree(len);
  197. 		int L = 0;
  198. 		for (auto x : right)
  199. 		{
  200. 			auto [mx,valR] = x;
  201. 			while (L < sz(left) and left[L].fi <= mx)
  202. 			{
  203. 				int valL = left[L].se, idx = getIndex(valL);
  204. 				BIT.update(idx,1);
  205. 				++L;
  206. 			}
  207. 			int cur = mx-valR, idx = lower_bound(all(vec),cur)-vec.begin()+1;
  208. 			ans += BIT.get(idx,len);
  209. 		}
  210. 		BIT.init();
  211. 		int R = 0;
  212. 		for (auto x : left)
  213. 		{
  214. 			auto [mx,valL] = x;
  215. 			while (R < sz(right) and right[R].fi < mx)
  216. 			{
  217. 				int valR = right[R].se, idx = getIndex(valR);
  218. 				BIT.update(idx,1);
  219. 				++R;
  220. 			}
  221. 			int cur = mx-valL, idx = lower_bound(all(vec),cur)-vec.begin()+1;
  222. 			ans += BIT.get(idx,len); 
  223. 		}
  224. 		return ans;
  225. 	}
  226.  
  227. 	void solve(void)
  228. 	{
  229. 		FOR(i,1,n) pre[i] = pre[i-1]+(s[i-1] == '(' ? 1 : -1);
  230. 		FOR(i,1,n) vec.pb(pre[i]);
  231. 		sort(all(vec));
  232. 		vec.erase(unique(all(vec)),vec.end());
  233. 		int ans = DnC(0,n);
  234. 		cout << ans;
  235. 	}
  236.  
  237. }
  238.  
  239. bool M2;
  240. signed main()
  241. {
  242.     fast;
  243.     if (fopen(name".inp","r"))
  244.     {
  245.     	freopen(name".inp","r",stdin);
  246.     	freopen(name".out","w",stdout);
  247.     }
  248.     cin >> n >> s;
  249.     // if (sub1::approved()) return sub1::solve(), time(), memory(), 0;
  250.     // if (sub3::approved()) return sub3::solve(), time(), memory(), 0;
  251.     if (sub4::approved()) return sub4::solve(), time(), memory(), 0;
  252.     time();
  253.     memory();
  254.     return 0;
  255. }
  256. // ██░ ██  █    ██  ███▄    █   ▄████
  257. //▓██░ ██▒ ██  ▓██▒ ██ ▀█   █  ██▒ ▀█▒
  258. //▒██▀▀██░▓██  ▒██░▓██  ▀█ ██▒▒██░▄▄▄░
  259. //░▓█ ░██ ▓▓█  ░██░▓██▒  ▐▌██▒░▓█  ██▓
  260. //░▓█▒░██▓▒▒█████▓ ▒██░   ▓██░░▒▓███▀▒
  261. // ▒ ░░▒░▒░▒▓▒ ▒ ▒ ░ ▒░   ▒ ▒  ░▒   ▒
  262. // ▒ ░▒░ ░░░▒░ ░ ░ ░ ░░   ░ ▒░  ░   ░
  263. // ░  ░░ ░ ░░░ ░ ░    ░   ░ ░ ░ ░   ░
  264. // ░  ░  ░   ░              ░       ░
Success #stdin #stdout #stderr 0.01s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
-------------Time:6.253ms.
17.5495 MB
https://ideone.com/d7ONyT
language:
C++14 (gcc 8.3)
created:
13 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!