fork download
copy 
  1. /*Flow..................*/
  2. #include <string>
  3. #include <vector>
  4. #include <iostream>
  5. #include <cstdio>
  6. #include <cstdlib>
  7. #include <stack>
  8. #include <queue>
  9. #include <cmath>
  10. #include <algorithm>
  11. #include <functional>
  12. #include <list>
  13. #include <deque>
  14. #include <bitset>
  15. #include <set>
  16. #include <map>
  17. #include <unordered_map>
  18. #include <unordered_set>
  19. #include <cstring>
  20. #include <sstream>
  21. #include <complex>
  22. #include <iomanip>
  23. #include <numeric>
  24. #include <cassert>
  25. #include <climits>
  26. #include <utility>
  27. #include <ctime>
  28. #include <tuple>
  29. #include <fstream>
  30. #include <cctype>
  31. #define FOR(i,a,n) for(i=a;i<n;i++)
  32. #define FORD(i,a,n) for(i=a;i>=n;i--)
  33. #define FORS(i,a) for(i=0;a[i];i++)
  34. #define si(x) scanf("%d",&x)
  35. #define sc(x) cin>>x
  36. #define sd(x) scanf("%lf",&x)
  37. #define sll(x) scanf("%lld",&x)
  38. #define ss(x) scanf("%s",x)
  39. #define prs(x) printf("%d ",x)
  40. #define pls(x) printf("%lld ",(long long)x)
  41. #define pc(x) printf("%c",(char)x)
  42. #define pi(x) printf("%d\n",x)
  43. #define pd(x) printf("%0.10lf\n",x);
  44. #define pll(x) printf("%lld\n",(long long)x)
  45. #define ps(x) printf("%s\n",x)
  46. #define M 1000000007
  47. #define ll long long
  48. #define mp make_pair
  49. #define all(x) x.begin(),x.end()
  50. #define pb push_back
  51. #define fr first
  52. #define se second
  53. #define in insert
  54. #define er erase
  55. #define pii pair<int, int>
  56. #define plll pair<long long, long long>
  57. #define PI 3.14159265358979323846264338327950288419716939937510582097494459230
  58. #define bs(x,y,z,w) {cerr<<x<<" "<<#y<<"="<<y<<" "<<#z<<"="<<z<<" "<<#w<<"="<<w<<endl;}
  59. #define ts(x,u,y,z,w) {cerr<<x<<" "<<#u<<"="<<u<<" "<<#y<<"="<<y<<" "<<#z<<"="<<z<<" "<<#w<<"="<<w<<endl;}
  60. #define trace(x) {cerr << #x << "=" << x <<endl;}
  61. #define trace2(x, y) {cerr << #x << "=" << x << " " << #y << "=" << y <<endl;}
  62. #define trace3(x, y, z) {cerr << #x << "=" << x << " " << #y << "=" << y << " " << #z << "=" << z << endl;}
  63. using namespace std;
  64. template <typename T> ostream& operator<<(ostream& os, const vector<T> &p){os << "[ "; for (T x: p) os << x << " "; os << "]" << endl; return os;}
  65. template <typename T> ostream& operator<<(ostream& os, const set<T> &p){os << "{ "; for (T x: p) os << x << " "; os << "}" << endl; return os;}
  66. template <typename T> ostream& operator<<(ostream& os, const multiset<T> &p){os << "{ "; for (T x: p) os << x << " "; os << "}" << endl; return os;}
  67. template <typename Tk, typename Tv> ostream& operator<<(ostream& os, const map<Tk, Tv> &p){os << "{ "; for (pair<Tk, Tv> x: p) os << x << " "; os << "}" << endl; return os;}
  68. template <typename Tk, typename Tv> ostream& operator<<(ostream& os, const pair<Tk, Tv> &p){os << "{" << p.first << ',' << p.second << "}";return os;}
  69. ll gcd (ll a, ll b) {return ( a ? gcd(b%a, a) : b );}
  70. ll power(ll a, ll n) {ll p = 1;while (n > 0) {if(n&1) {p = p * a;} n >>= 1; a *= a;} return p;}
  71. ll power(ll a, ll n, ll mod) {ll p = 1;while (n > 0) {if(n&1) {p = p * a; p %= mod;} n >>= 1; a *= a; a %= mod;} return p % mod;}
  72.  
  73. const int N=600005;
  74.  
  75. ll bit[2][N];
  76.  
  77. void update(int st,int x,ll v)
  78. {
  79. 	while(x<N)
  80. 		bit[st][x]+=v,x+=x&(-x);
  81. }
  82. ll query(int st,int x)
  83. {
  84. 	ll s=0;
  85. 	while(x>0)
  86. 		s+=bit[st][x],x-=x&(-x);
  87. 	return s;
  88. }
  89. ll query(ll a)
  90. {
  91. 	return query(0,a)*a-query(1,a);
  92. }
  93. ll range_query(int l,int r)
  94. {
  95. 	return query(r)-query(l-1);
  96. }
  97. void range_upd(int l,int r,ll val)
  98. {
  99. 	update(0,l,val);
  100. 	update(0,r+1,-val);
  101. 	update(1,l,val*(l-1));
  102. 	update(1,r+1,-val*r);
  103. }
  104.  
  105. map<int,int> pr;
  106.  
  107. int main()
  108. {
  109.    int i,j;
  110. 	int n;
  111. 	si(n);
  112. 	int la=0;
  113. 	FOR(i,1,n+1)
  114. 	{
  115. 		int e,l,r;
  116. 		si(e),si(l),si(r);
  117. 		la=max(la,pr[e]);
  118. 		// trace3(e,i,la);
  119. 		pr[e]=i;
  120. 		range_upd(1,i-la,1);
  121. 		ll x;
  122. 		if(l>r)
  123. 			x=0;
  124. 		else
  125. 			x=(range_query(l,r));
  126. 		pll(x);
  127. 	}   
  128.    return 0;
  129. }
Success #stdin #stdout 0s 24616KB
comments (?)
stdin
copy 
10
1 1 4
2 3 2
4 2 5
2 1 10
1 2 4
5 4 7
3 3 8
2 2 6
1 1 10
6 2 5
stdout
copy 
1
0
3
8
6
1
7
16
28
23
https://ideone.com/GdcBzO
language:
C++14 (gcc 8.3)
created:
6 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!