fork download
copy 
  1. #include <algorithm>
  2. #include <bitset>
  3. #include <cassert>
  4. #include <cctype>
  5. #include <cmath>
  6. #include <cstdio>
  7. #include <cstdlib>
  8. #include <cstring>
  9. #include <ctime>
  10. #include <deque>
  11. #include <functional>
  12. #include <iomanip>
  13. #include <iostream>
  14. #include <limits>
  15. #include <list>
  16. #include <map>
  17. #include <memory>
  18. #include <numeric>
  19. #include <queue>
  20. #include <set>
  21. #include <sstream>
  22. #include <stack>
  23. #include <string>
  24. #include <utility>
  25. #include <vector>
  26.  
  27. using namespace std;
  28.  
  29. #ifndef ONLINE_JUDGE
  30. 	bool debug = false;
  31. #else
  32. 	bool debug = true;
  33. #endif
  34.  
  35. typedef long long unsigned llu;
  36. typedef long long lld;
  37. typedef long ld;
  38.  
  39. //definition
  40. #define vi vector < int >
  41. #define vld vector < ld >
  42. #define vlld vector < lld >
  43. #define pii pair <int, int>
  44.  
  45. #define gc getchar
  46. #define pc putchar
  47. #define rr freopen("input.txt", "r", stdin)
  48. #define wr freopen("output.txt", "w", stdout)
  49.  
  50. #define MOD 1000000007
  51. #define MAX 100005
  52. #define pi 3.14159265358979
  53. #define ESP (1e-9)
  54.  
  55. #define fu(i,a,n) for(i=a;i<n;i++)
  56. #define fue(i,a,n) for(i=a;i<=n;i++)
  57. #define fd(i,n,a) for(i=n;i>a;i--)
  58. #define fde(i,n,a) for(i=n;i>=a;i--)
  59. #define fr(i,a) for(i=0;i<a;i++)
  60. #define fe(i,a) for(i=0;i<=a;i++)
  61.  
  62. #define sd(n) scanf("%d",&n)
  63. #define sld(n) scanf("%ld",&n)
  64. #define slld(n) scanf("%lld",&n)
  65. #define pfd(n) printf("%d",n)
  66. #define pfld(n) printf("%ld",n)
  67. #define pflld(n) printf("%lld",n)
  68.  
  69. #define ff first
  70. #define ss second
  71. #define sz size()
  72. #define clr clear()
  73. #define len length()
  74. #define pb push_back
  75. #define mp make_pair
  76. #define gcd(a,b)  __gcd(a,b)
  77. #define all(vi) vi.begin(), vi.end()
  78. #define mem(i,n) memset(i,n,sizeof(i))
  79. #define IOS ios_base::sync_with_stdio(false)
  80.  
  81. #define imax numeric_limits<int>::max()
  82. #define imin numeric_limits<int>::min()
  83. #define ldmax numeric_limits<ld>::max()
  84. #define ldmin numeric_limits<ld>::min()
  85. #define lldmax numeric_limits<lld>::max()
  86. #define lldmin numeric_limits<lld>::min()
  87. #define tr(container, it) for(typeof(container.begin()) it = container.begin(); it != container.end(); it++)
  88. //end of definition
  89.  
  90. //fast input
  91.  
  92. int scan_d()		{register int c=gc();int x=0;for(;(c<48 || c>57);c = gc());for(;c>47 && c<58;c = gc()){x = (x<<1) + (x<<3) + c - 48;}return x;}
  93. ld scan_ld()		{register ld c=gc();ld x=0;for(;(c<48 || c>57);c = gc());for(;c>47 && c<58;c = gc()){x = (x<<1) + (x<<3) + c - 48;}return x;}
  94. lld scan_lld()		{register lld c=gc();lld x=0;for(;(c<48 || c>57);c = gc());for(;c>47 && c<58;c = gc()){x = (x<<1) + (x<<3) + c - 48;}return x;}
  95. llu scan_llu()		{register llu c=gc();llu x=0;for(;(c<48 || c>57);c = gc());for(;c>47 && c<58;c = gc()){x = (x<<1) + (x<<3) + c - 48;}return x;}
  96.  
  97. //end of fast input
  98.  
  99. //fast output
  100.  
  101. //no line break
  102. void print_d(int n)     {if(n<0){n=-n;putchar('-');}int i=10;char output_buffer[10];do{output_buffer[--i]=(n%10)+'0';n/=10;}while(n);do{putchar(output_buffer[i]);}while(++i<10);}
  103. void print_ld(ld n)     {if(n<0){n=-n;putchar('-');}int i=11;char output_buffer[11];do{output_buffer[--i]=(n%10)+'0';n/=10;}while(n);do{putchar(output_buffer[i]);}while(++i<11);}
  104. void print_lld(lld n)     {if(n<0){n=-n;putchar('-');}int i=21;char output_buffer[21];do{output_buffer[--i]=(n%10)+'0';n/=10;}while(n);do{putchar(output_buffer[i]);}while(++i<21);}
  105. void print_llu(llu n)     {int i=21;char output_buffer[21];do{output_buffer[--i]=(n%10)+'0';n/=10;}while(n);do{putchar(output_buffer[i]);}while(++i<21);}
  106.  
  107. //new line
  108. void println_d(int n)     {if(n<0){n=-n;putchar('-');}int i=10;char output_buffer[11];output_buffer[10]='\n';do{output_buffer[--i]=(n%10)+'0';n/=10;}while(n);do{putchar(output_buffer[i]);}while(++i<11);}
  109. void println_ld(ld n)     {if(n<0){n=-n;putchar('-');}int i=11;char output_buffer[12];output_buffer[11]='\n';do{output_buffer[--i]=(n%10)+'0';n/=10;}while(n);do{putchar(output_buffer[i]);}while(++i<12);}
  110. void println_lld(lld n)     {if(n<0){n=-n;putchar('-');}int i=21;char output_buffer[22];output_buffer[21]='\n';do{output_buffer[--i]=(n%10)+'0';n/=10;}while(n);do{putchar(output_buffer[i]);}while(++i<22);}
  111. void println_llu(llu n)     {int i=21;char output_buffer[22];output_buffer[21]='\n';do{output_buffer[--i]=(n%10)+'0';n/=10;}while(n);do{putchar(output_buffer[i]);}while(++i<22);}
  112.  
  113. //special char
  114. char sp;
  115. void printsp_d(int n)     {if(n<0){n=-n;putchar('-');}int i=10;char output_buffer[11];output_buffer[10]=sp;do{output_buffer[--i]=(n%10)+'0';n/=10;}while(n);do{putchar(output_buffer[i]);}while(++i<11);}
  116. void printsp_ld(ld n)     {if(n<0){n=-n;putchar('-');}int i=11;char output_buffer[12];output_buffer[11]=sp;do{output_buffer[--i]=(n%10)+'0';n/=10;}while(n);do{putchar(output_buffer[i]);}while(++i<12);}
  117. void printsp_lld(lld n)     {if(n<0){n=-n;putchar('-');}int i=21;char output_buffer[22];output_buffer[21]=sp;do{output_buffer[--i]=(n%10)+'0';n/=10;}while(n);do{putchar(output_buffer[i]);}while(++i<22);}
  118. void printsp_llu(llu n)     {int i=21;char output_buffer[22];output_buffer[21]=sp;do{output_buffer[--i]=(n%10)+'0';n/=10;}while(n);do{putchar(output_buffer[i]);}while(++i<22);}
  119.  
  120. //end of fast output
  121.  
  122. void calculate(lld a[],lld b[],lld n)
  123. {
  124. 	stack<lld> st;
  125. 	st.push(0);
  126. 	lld i;
  127. 	b[0]=1;
  128. 	fu(i,1,n)
  129. 	{
  130. 		//while(a[i]>a[st.top()] && !st.empty())
  131. 		while(!st.empty() && a[i]>a[st.top()])
  132. 			st.pop();
  133. 		if(!st.empty())
  134. 			b[i]=i-st.top();
  135. 		else
  136. 			b[i]=i+1;
  137. 		st.push(i);
  138. 		println_lld(b[i]);
  139. 	}
  140. }
  141.  
  142.  
  143. void print(lld a[],lld n)
  144. {
  145. 	lld i;
  146. 	fr(i,n-1)
  147. 		printsp_lld(a[i]);
  148. 	println_lld(a[i]);
  149. }
  150.  
  151. int main()
  152. {
  153. 	lld n,i;
  154. 	n=scan_lld();
  155. 	lld a[n],b[n];
  156. 	fr(i,n)
  157. 		a[i]=scan_lld();
  158. 	print(a,n);
  159. 	calculate(a,b,n);
  160. 	print(b,n);
  161. 	return 0;
  162. }
Success #stdin #stdout 0s 3468KB
comments (?)
stdin
copy 
6
10 4 5 90 120 80
stdout
copy 
10459012080
1
2
4
5
1
112451
https://ideone.com/OJj9Jc
language:
C++ (gcc 8.3)
created:
8 years 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!