API tools faq
paste
Sayach8

Untitled

Sayach8
Oct 9th, 2021
14
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 14.31 KB | None | 0 0
raw download clone embed print report
  1. #include <bits/stdc++.h>
  2. #include<ext/pb_ds/assoc_container.hpp>
  3. #define gp __gnu_pbds
  4. #define iset(T) gp::tree<T,gp::null_type,less<T>,gp::rb_tree_tag,gp::tree_order_statistics_node_update>
  5. using namespace std;
  6.  
  7. #define SQ(x) ((x)*(x))
  8. #define u unsigned
  9. #define ull unsigned long long
  10. #define ll long long
  11. #define ld long double
  12. #define test(x) cerr<<"here "<<#x<<endl;
  13. #define putpls(x) #x
  14. #define casing(x,y) cout<<"Case #"<<x<<": "<<y<<'\n';
  15. #define inputstl(v) for(auto& x:v) cin>>x;
  16. #define input(arr,n) for(ull i=0;i<n;++i){cin>>(arr)[i];}
  17. #define print(arr,n) for(ull i=0;i<n;++i){cout<<(arr)[i]<<" ";}cout<<'\n';
  18. #define printall(x) {for(auto y:x){cout<<y<<' ';}cout<<'\n';}
  19. #define printallpii(x) for(auto y:x){cout<<y.fi<<','<<y.se<<' ';}cout<<'\n';
  20. #define print_err(arr,n) for(ull i=0;i<n;++i){cerr<<(arr)[i]<<" ";}cerr<<'\n';
  21. #define printall_err(x) for(auto y:x){cerr<<y<<' ';}cerr<<'\n';
  22. #define printallpii_err(x) for(auto y:x){cerr<<y.fi<<','<<y.se<<' ';}cerr<<'\n';
  23. #define fi first
  24. #define se second
  25. #define pb push_back
  26. #define eb emplace_back
  27. #define mp make_pair
  28. #define mt make_tuple
  29. #define pii pair<int,int>
  30. #define pll pair<long long,long long>
  31. #define fastio ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
  32.  
  33. #define SENSITIVITY 1e-9
  34. #define EQUAL(xx1,xx2) [](auto x1,auto x2){double ep=0.0001;double pos=x1-x2;if(pos<0){pos=-pos;}double maxi=(x1>x2)?(x1):(x2);if(pos/(maxi*ep)<SENSITIVITY)return true;else return false;}(xx1,xx2)
  35. #define pack(x) x.begin(),x.end()
  36.  
  37. constexpr int64_t mod=1e9+7;
  38.  
  39. struct timer
  40. {
  41. private:
  42. static int __timer_number;
  43. public:
  44. int timer_number;
  45. chrono::high_resolution_clock::time_point t1;
  46. timer(): t1(chrono::high_resolution_clock::now()),timer_number(__timer_number++)
  47. {
  48. cout<<"timer number "<<timer_number<<" init\n";
  49.  
  50. }
  51. timer(const timer& t):t1(t.t1),timer_number(__timer_number++)
  52. {
  53. cout<<"timer number "<<timer_number<<" init\n";
  54.  
  55. }
  56. template<class T=chrono::milliseconds>
  57. auto give_time()
  58. {
  59. chrono::high_resolution_clock::time_point t2;
  60. t2=chrono::high_resolution_clock::now();
  61. return chrono::duration_cast<T>(t2-t1);
  62. }
  63. template<class T=chrono::milliseconds>
  64. void print_time()
  65. {
  66. chrono::high_resolution_clock::time_point t2;
  67. t2=chrono::high_resolution_clock::now();
  68. auto d=chrono::duration_cast<T>(t2-t1);
  69. cout<<"time (default:milli) until now by timer "<<timer_number<<" : "<<d.count()<<'\n';
  70. }
  71. ~timer()
  72. {
  73. __timer_number--;
  74. }
  75. };
  76. int timer::__timer_number=0;
  77.  
  78. //this does not support . character matching (globbing)
  79. //to do that add the code from your solution of leetcode 211
  80. //add a new static element to the node, named defaulter and use that for globbing
  81.  
  82. template<class T>
  83. class trie{
  84. private:
  85. vector<T> hold;
  86. int hold_size;
  87. int found;
  88. int _size;
  89. struct node{
  90. map<T,node*> link;
  91. int ending;
  92. node():link(map<T,node*>()),ending(0)
  93. {
  94.  
  95. }
  96. ~node()
  97. {
  98.  
  99. }
  100. };
  101. node root;
  102. void __traverse(node* const p,int index)
  103. {
  104. if(index==hold_size)
  105. {
  106. // if(p->ending>0)
  107. // found=;
  108. found=p->ending;
  109. return ;
  110. }
  111. // if(hold[index]=='.')
  112. // {
  113. // for(auto& x:p->link)
  114. // {
  115. // traverse(x.second,index+1);
  116. // if(found)
  117. // return ;
  118. // }
  119. // }
  120. // else
  121. // {
  122. auto it=p->link.find(hold[index]);
  123. if(it!=p->link.end())
  124. {
  125. __traverse(it->second,index+1);
  126. }
  127. // }
  128. }
  129. bool __del_traverse(node* const p,int index)
  130. {
  131. if(index==hold_size)
  132. {
  133. if(!p->ending)
  134. {
  135. --p->ending;
  136. return 1;
  137. }
  138. return 0;
  139. }
  140. auto it=p->link.find(hold[index]);
  141. if(it!=p->link.end())
  142. {
  143. return __del_traverse(it->second,index+1);
  144. }
  145. return 0;
  146. }
  147. void __dfs_clear(node* const p)
  148. {
  149. for(auto& x:p->link)
  150. {
  151. __dfs_clear(x.second);
  152.  
  153. delete x.second;
  154. }
  155.  
  156. }
  157. public:
  158. trie():_size(0)
  159. {
  160.  
  161. }
  162. void add_stuff(const vector<T>& v)
  163. {
  164. hold.assign(v.begin(),v.end());
  165. hold_size=v.size();
  166. int index=0;
  167. node* cur=&root;
  168. while(index!=hold_size)
  169. {
  170. auto it=cur->link.find(hold[index]);
  171. if(it==cur->link.end())
  172. {
  173. // test(1);
  174. cur->link[hold[index]]=new node();
  175. // cur=cur->link[hold[index]];
  176. }
  177. cur=cur->link[hold[index]];
  178. ++index;
  179. }
  180. ++(cur->ending);
  181. ++_size;
  182. }
  183. int find_stuff(const vector<T>& v)
  184. {
  185. found=0;
  186. hold.assign(v.begin(),v.end());
  187. hold_size=v.size();
  188. __traverse(&root,0);
  189. return found;
  190. }
  191. bool delete_stuff(const vector<T>& v)
  192. {
  193. hold.assign(v.begin(),v.end());
  194. hold_size=v.size();
  195. auto val=__del_traverse(&root,0);
  196. if(val)
  197. --_size;
  198. return val;
  199. }
  200. void clear()
  201. {
  202. __dfs_clear(&root);
  203. root.link.clear();
  204. _size=0;
  205. }
  206. int size()
  207. {
  208. return _size;
  209. }
  210. ~trie()
  211. {
  212. clear();
  213. }
  214. };
  215.  
  216.  
  217.  
  218.  
  219.  
  220.  
  221. template<class A>
  222. void ____internal__print(string s,A a)
  223. {
  224. auto index=s.find(',');
  225.  
  226. cerr<<s.substr(0,index)<<": "<<a<<'\n';
  227. }
  228. template<class A,class ... B>
  229. void ____internal__print(string s,A a,B... b)
  230. {
  231. auto index=s.find(',');
  232.  
  233. cerr<<s.substr(0,index)<<": "<<a<<", ";
  234. ____internal__print(s.substr(index+1,(int)s.length()-index-1),b...);
  235. }
  236.  
  237. #define debug(...) \
  238. {string __debug__s__=string(#__VA_ARGS__)+",";____internal__print(__debug__s__,__VA_ARGS__);}
  239.  
  240. bool isPrime(ll a)
  241. {
  242. if(a==1)
  243. return false;
  244. for(ll i=2; i*i<=a; ++i)
  245. {
  246. if(a%i==0)
  247. {
  248. return false;
  249. }
  250. }
  251. return true;
  252. }
  253. bool isPali(string s)
  254. {
  255. int _size=(s.length())/2;
  256. for(int i=0; i<_size; ++i)
  257. {
  258. if(s.at(i)!=s.at(s.length()-1-i))
  259. {
  260. return false;
  261. }
  262. }
  263. return true;
  264. }
  265. int gcd(int a,int b)
  266. {
  267. if(a==0)
  268. {
  269. return b;
  270. }
  271. else if(b==0)
  272. {
  273. return a;
  274. }
  275. else
  276. {
  277. int shift=__builtin_ctz(a|b);
  278. a>>=__builtin_ctz(a);
  279. do
  280. {
  281. b>>=__builtin_ctz(b);
  282. if(a>b)
  283. {
  284. a=a^b;
  285. b=a^b;
  286. a=a^b;
  287. }
  288. b-=a;
  289. }
  290. while(b);
  291. return a<<shift;
  292. }
  293. }
  294. ll gcdll(ll a,ll b)
  295. {
  296. if(a==0)
  297. {
  298. return b;
  299. }
  300. else if(b==0)
  301. {
  302. return a;
  303. }
  304. else
  305. {
  306. ll shift=__builtin_ctzll(a|b);
  307. a>>=__builtin_ctzll(a);
  308. do
  309. {
  310. b>>=__builtin_ctzll(b);
  311. if(a>b)
  312. {
  313. a=a^b;
  314. b=a^b;
  315. a=a^b;
  316. }
  317. b-=a;
  318. }
  319. while(b);
  320. return a<<shift;
  321. }
  322. }
  323. ll power(ll a,ll b,ll _mod)
  324.  
  325. {
  326. a%=_mod;
  327. ll temp=a;
  328. ll ans=1;
  329. if(!b)
  330. return 1;
  331. int limit=63-__builtin_clzll(b);
  332. int index=0;
  333. while(index<=limit)
  334. {
  335. if(b&(1ll<<index))
  336. {
  337. ans=(ans*temp)%_mod;
  338. }
  339. ++index;
  340. temp=(temp*temp)%_mod;
  341. }
  342. return ans;
  343. }
  344. template<class T>
  345. inline void swapper(const T& d1,const T& d2)
  346. {
  347. for(int i=0;i<sizeof(T);++i)
  348. {
  349. *((char*)(&d1)+i)=(*((char*)(&d1)+i))^(*((char*)(&d2)+i));
  350. }
  351. for(int i=0;i<sizeof(T);++i)
  352. {
  353. *((char*)(&d2)+i)=(*((char*)(&d1)+i))^(*((char*)(&d2)+i));
  354. }
  355. for(int i=0;i<sizeof(T);++i)
  356. {
  357. *((char*)(&d1)+i)=(*((char*)(&d1)+i))^(*((char*)(&d2)+i));
  358. }
  359. }
  360.  
  361. int kmp(const string& s,const string& t)
  362. {
  363. int s_size=s.size(),t_size=t.size();
  364. if(s_size<t_size)
  365. return 0;
  366. vector<int> arr(t_size);
  367. int len=0;
  368. for(int i=0;i<t_size;++i)
  369. {
  370. if(!i)
  371. {
  372. arr[i]=0;
  373. continue;
  374. }
  375. while(1)
  376. {
  377. if(t[len]==t[i])
  378. {
  379. arr[i]=++len;
  380. break;
  381. }
  382. if(!len)
  383. {
  384. arr[i]=0;
  385. break;
  386. }
  387. len=arr[len-1];
  388.  
  389. }
  390. }
  391. //printall(arr);
  392. int ans=0;
  393. for(int j=0,i=0;i<s_size;++i,++j)
  394. {
  395. // debug(i,j);
  396. if(s[i]==t[j])
  397. {
  398. if(j==t.length()-1)
  399. {
  400. //debug(i,j)
  401. j=arr[j]-1;
  402.  
  403. //debug(j);
  404.  
  405. ++ans;
  406. }
  407. continue;
  408. }
  409. if(!j)
  410. {
  411. --j;
  412. continue;
  413. }
  414. --i;
  415. j=arr[j-1]-1;
  416. }
  417. return ans;
  418. }
  419. template<class T>
  420. vector<T> LIS(vector<T> a)
  421. {
  422. int n=a.size();
  423. vector<pair<T,int>> v;
  424. vector<T*> add(n);
  425. add[0]=nullptr;
  426. v.push_back(make_pair(a[0],0));
  427. auto f=[](pair<T,int> a,pair<T,int> b){return a.first<b.first;};
  428. for(int i=1;i<n;++i)
  429. {
  430. auto it=lower_bound(v.begin(),v.end(),make_pair(a[i],-1),f);
  431. if(it==v.end())
  432. {
  433. add[i]=&a[0]+v.back().second;
  434. v.push_back(make_pair(a[i],i));
  435. }
  436. else
  437. {
  438. it->first=a[i];
  439.  
  440. it->second=i;
  441. if(it==v.begin())
  442. {
  443. add[i]=nullptr;
  444. }
  445. else
  446. {
  447. add[i]=&a[0]+(it-1)->second;
  448. }
  449. }
  450. }
  451. vector<T> ans;
  452. ans.reserve(v.size());
  453. T* p=&a[0]+v.back().second;
  454. while(p!=nullptr)
  455. {
  456. ans.push_back(*p);
  457. p=(add[p-&a[0]]);
  458. }
  459. reverse(ans.begin(),ans.end());
  460. return ans;
  461. }
  462.  
  463. ///O(N*N) NOT MANCHAR . BULLSHIT DP
  464. string longest_palindromic_substring(const string& s)
  465. {
  466. if(s.size()<=1)
  467. return s;
  468. int len=s.size();
  469. vector<bool> odd(s.size(),1);
  470. vector<bool> even(s.size(),0);
  471. string ans=string(1,s[0]);
  472. for(int i=0;i<len-1;++i)
  473. {
  474. if(s[i]==s[i+1])
  475. {
  476. even[i]=1;
  477. if(ans.size()<2)
  478. ans=s.substr(i,2);
  479. }
  480. }
  481. for(int i=3;i<=len;++i)
  482.  
  483. {
  484. if(i&1)
  485. {
  486. for(int j=0;j<=len-i;++j)
  487. {
  488. odd[j]=(s[j]==s[j+i-1])&&(odd[j+1]);
  489. if(odd[j]&&ans.size()<i)
  490. ans=s.substr(j,i);
  491. }
  492. }
  493. else
  494. {
  495. for(int j=0;j<=len-i;++j)
  496. {
  497. even[j]=(s[j]==s[j+i-1])&&(even[j+1]);
  498. if(even[j]&&ans.size()<i)
  499. ans=s.substr(j,i);
  500. }
  501. }
  502. }
  503. return ans;
  504. }
  505.  
  506.  
  507. template<class S>
  508. S longestSubarraySum(auto start,auto end)
  509. {
  510. S val=0;
  511. S maxi=*start;
  512. for(auto s=start;s!=end;++s)
  513. {
  514. if(val+*s>=*s)
  515. {
  516. val+=*s;
  517. }
  518. else
  519. {
  520. val=*s;
  521. }
  522. if(maxi<val)
  523. {
  524. maxi=val;
  525. }
  526. }
  527. return maxi;
  528. }
  529.  
  530. template<class T>
  531. T fibo(T x,T _mod)
  532. {
  533. if(x==1)
  534. {
  535. return (T)0;
  536. }
  537. else if(x==2)
  538. {
  539. return (T)1;
  540. }
  541. // x*=2;// made it twice to get the actual value
  542. stack<pair<T,T>> st;
  543. while(x>1)
  544. {
  545. st.push(make_pair(x,x+1));
  546. x/=2;
  547. }
  548. //start with an even means the same components
  549. //otherwise component change
  550. T a=0;
  551. T b=1;
  552. T c;
  553. while(st.size())
  554. {
  555. auto p=st.top();
  556. st.pop();
  557. T cur_a;
  558. T cur_b;
  559. if(p.first&1)
  560. {
  561. cur_a=(b*b+2*a*b)%_mod;
  562. b=(a+b)%_mod;
  563. a=(b-a+_mod)%_mod;
  564. cur_b=(a*a+b*b)%_mod;
  565. }
  566. else
  567. {
  568. cur_a=(a*a+b*b)%_mod;
  569. cur_b=(b*b+2*a*b)%_mod;
  570. }
  571. a=cur_a;
  572. b=cur_b;
  573. }
  574. return a;
  575. }
  576.  
  577. // #pragma GCC optimize("Ofast")
  578. // #pragma GCC optimize("unroll-loops")
  579.  
  580.  
  581. int main()
  582. {
  583. // #ifdef ONLINE_JUDGE
  584. // #include <sys/resource.h>
  585. // rlimit R;
  586. // getrlimit(RLIMIT_STACK, &R);
  587. // R.rlim_cur = R.rlim_max;
  588. // setrlimit(RLIMIT_STACK, &R);
  589. // #endif
  590. //define cin fin
  591. //ifstream fin;
  592. //fin.open("input.txt",ios_base::in);
  593.  
  594. // fastio;
  595. // freopen("input.txt","r",stdin);
  596. //freopen("output.txt","w",stdout);
  597. int tt=1;
  598. cin>>tt;
  599. // scanf("%d",&tt);
  600. // timer t;
  601. int ittt=1;
  602. //////CHECK FOR EDGE CASES DUMMY!!!!!!!!!!!/////
  603. while(tt--)
  604. {
  605. int N,q;
  606. cin>>N>>q;
  607. string s;
  608. cin>>s;
  609. s=string("!")+s;
  610. int pos[N+1]={};
  611. int neg[N+1]={};
  612. int p=0,n=0;
  613. vector<int> PLUS,MINUS;
  614. for(int i=1;i<=N;++i)
  615. {
  616. if(s[i]=='+')
  617. {
  618. ++p;
  619. PLUS.push_back(p);
  620. }
  621. else
  622. {
  623. ++n;
  624. MINUS.push_back(n);
  625. }
  626. pos[i]=p;
  627. neg[i]=n;
  628. }
  629. for(int i=0;i<q;++i)
  630. {
  631. int x,y;
  632. cin>>x>>y;
  633. int balance=(pos[y]-pos[x-1])-(neg[y]-neg[x-1]);
  634. cout<<abs(balance)<<"\n";
  635. if(balance>0)
  636. {
  637. auto it=lower_bound(pack(PLUS),x);
  638. for(int j=0;j<abs(balance);++j)
  639. {
  640. cout<<*it<<" ";
  641. ++it;
  642. }
  643. cout<<"\n";
  644. }
  645. else if(balance<0)
  646. {
  647. auto it=lower_bound(pack(MINUS),x);
  648. for(int j=0;j<abs(balance);++j)
  649. {
  650. cout<<*it<<" ";
  651. ++it;
  652. }
  653. cout<<"\n";
  654. }
  655. }
  656. }
  657. // t.print_time();
  658. return 0;
  659. }
Add Comment
Please, Sign In to add comment
Public Pastes
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!