fork download
  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
stdin
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
1
0
3
8
6
1
7
16
28
23