fork download
copy 
  1. #include <cstdio>
  2. #include <iostream>
  3. #include <cstring>
  4. #include <cstdlib>
  5. #include <string>
  6. #include <stack>
  7. #include <queue>
  8. #include <deque>
  9. #include <vector>
  10. #include <map>
  11. #include <set>
  12. #include <utility>
  13. #include <algorithm>
  14. #include <cmath>
  15. #include <climits>
  16. #ifdef DEBUG
  17.     #include <ctime>
  18. #endif
  19. using namespace std;
  20.  
  21. // template
  22.  
  23. // abbreviations
  24. #define vi vector<int>
  25. #define vl vector<ll>
  26. #define vb vector<bool>
  27. #define vs vector<string>
  28. #define ii pair<int, int>
  29. #define a first
  30. #define b second
  31. #define vii vector<ii>
  32. #define mii map<ii>
  33. #define vvi vector<vi>
  34. #define vvl vector<vl>
  35. #define que queue
  36. #define pque priority_queue
  37. #define stk stack
  38. #define pub push_back
  39. #define pob pop_back
  40. #define puf push_front
  41. #define pof pop_front
  42. #define pu push
  43. #define po pop
  44. #define mp make_pair
  45. #define sz(var) ((int) var.size())
  46. #define rep(it, n) for(int it = 0; it < n; ++it)
  47. #define dep(it, n) for(int it = n - 1; it >= 0; --it)
  48. #define rep1(it, n) for(int it = 1; it <= n; ++it)
  49. #define dep1(it, n) for(int it = n; it > 0; --it)
  50. #define loop(it, from, to) for(int it = (from); it <= (to); ++it)
  51. #define iter(it, cont) for(__typeof((cont).begin()) it = (cont).begin(); it != (cont).end(); ++it)
  52. #define riter(it, cont) for(__typeof((cont).rbegin()) it = (cont).rbegin(); it != (cont).rend(); ++it)
  53. #define all(cont) (cont).begin(), (cont).end()
  54. #define rng(cont, n) cont, cont + n
  55. #define memclr(var) memset(var, 0, sizeof(var))
  56.  
  57. typedef unsigned long long ull;
  58. typedef long long ll;
  59.  
  60. const int INF = INT_MAX;
  61. const int NINF = INT_MIN;
  62. const ll INF_LL = LLONG_MAX;
  63. const ll NINF_LL = LLONG_MIN;
  64. const double PI = acos(-1.0);
  65. const int MOD = 1e9 + 7;
  66.  
  67. #ifdef DEBUG
  68.     #define debug(fmt, args...) printf("Line %d, in %s\t: " fmt, __LINE__, __FUNCTION__, ##args)
  69.     #define rep_rt() printf("[Run time: %.3fs]\n", ((double) clock()) / CLOCKS_PER_SEC)
  70. #else
  71.     #define debug(...)
  72. #endif
  73.  
  74. // end of template
  75.  
  76. #ifdef __WIN32 
  77.     #define gc getchar
  78.     #define pc putchar
  79. #else
  80.     #define gc getchar_unlocked
  81.     #define pc putchar_unlocked
  82. #endif
  83. #define MAX_DIGIT_int 10
  84. #define MAX_DIGIT_ll 19
  85. #define FS_INT_TYPE(type) \
  86.     void fsi(type &inp) { \
  87.         register char c = gc(), prev = '+'; \
  88.         for (; !isdigit(c); c = gc()) prev = c; \
  89.         inp = 0; \
  90.         for (; isdigit(c); c = gc()) { \
  91.             inp = (inp << 3) + (inp << 1) + (c - '0'); \
  92.         } \
  93.         if (prev == '-') \
  94.             inp = -inp; \
  95.     } \
  96.     void fso(type val) { \
  97.         if (!val) { \
  98.             pc('0'); \
  99.             return; \
  100.         } \
  101.         char buff[MAX_DIGIT_ ##type]; \
  102.         if (val < 0) { \
  103.             pc('-'); \
  104.             val = -val; \
  105.         } \
  106.         register int i; \
  107.         for (i = 0; val; ++i, val /= 10) { \
  108.             buff[i] = (val % 10) + '0'; \
  109.         } \
  110.         while (i--) { \
  111.             pc(buff[i]); \
  112.         } \
  113.     }
  114. FS_INT_TYPE(int)
  115. FS_INT_TYPE(ll)
  116.  
  117. void fsi(char *str) {
  118.     register char c = gc();
  119.     for (; c <= 32; c = gc());
  120.     register int idx = 0;
  121.     for (; c > 32; c = gc()) {
  122.         str[idx++] = c;
  123.     }
  124.     str[idx] = 0;
  125. }
  126.  
  127. #define PRINT(str_var, length) \
  128.     register int idx = 0, len = length; \
  129.     while (idx != len) pc(str_var[idx++]);
  130.  
  131. void fso(const char *str) {
  132.     PRINT(str, strlen(str));
  133. }
  134.  
  135. void fso(char *str) {
  136.     PRINT(str, strlen(str));
  137. }
  138.  
  139. void fso(string &str) {
  140.     PRINT(str, str.length());
  141. }
  142. #undef gc
  143. #undef putchar
  144.  
  145. template <typename farg, typename ... args>
  146. void fsi(farg &inp, args& ... rest) {
  147.     fsi(inp);
  148.     fsi(rest...);
  149. }
  150.  
  151. template <typename farg, typename ... args>
  152. void fso(farg val, args ... rest) {
  153.     fso(val);
  154.     fso(rest...);
  155. }
  156. // WARNING: Output doesn't work for minimum value
  157.  
  158. #define MAXN (int) (1e5)
  159. struct Str {
  160.     int a, b, c;
  161. } strs[MAXN + 1];
  162.  
  163. #define MAXM (int) (1e5)
  164. vi stridxs_c[MAXM + 2];
  165.  
  166. ll sqr(ll val) {
  167.     return val * val;
  168. }
  169.  
  170. int main() {
  171. #ifdef DEBUG
  172.     freopen("WILD.in", "r", stdin);
  173. #endif
  174.  
  175.     int n, m;
  176.     for (fsi(n, m); (n != 0) and (m != 0); fsi(n, m)) {
  177.         rep(idx, n) {
  178.             Str &str = strs[idx];
  179.             // scanf("%d %d %d", &str.a, &str.b, &str.c);
  180.             fsi(str.a, str.b, str.c);
  181.             stridxs_c[str.c].pub(idx);
  182.         }
  183.         ll ans = 0;
  184.  
  185.         map<int, int> span;
  186.         span[0] = m + 1;
  187.         span[m + 1] = 0;
  188.  
  189.         ll sum = 0;
  190.         dep1(c_val, m) {
  191.             vi &stridxs = stridxs_c[c_val];
  192.             while (stridxs.size()) {
  193.                 Str &str = strs[stridxs.back()];
  194.                 stridxs.pob();
  195.                 map<int, int>::iterator spanner = span.lower_bound(str.a);
  196.                 int span_val = spanner->b;
  197.                 if (span_val >= str.b) {
  198.                     continue;
  199.                 }
  200.                 // allowed to insert
  201.                 map<int, int>::iterator prev_spanner = --spanner;
  202.                 sum += ll(str.b - span_val) * (str.a - prev_spanner->a);
  203.                 span[str.a] = str.b;
  204.  
  205.                 // check if prev_spanner is consumed by this spanner
  206.                 while (true) {
  207.                     prev_spanner = --span.lower_bound(str.a);
  208.                     int prev_span_idx = prev_spanner->a, prev_span_val = prev_spanner->b;
  209.                     if (prev_span_val > str.b)
  210.                         break;
  211.                     map<int, int>::iterator prev_prev_spanner = --prev_spanner;
  212.                     sum += ll(str.b - prev_span_val) * (prev_span_idx - prev_prev_spanner->a);
  213.                     span.erase(prev_span_idx);
  214.                 }
  215.             }
  216.             ans += sqr(m) - sum;
  217.         }
  218.         // printf("%lld\n", ans);
  219.         fso(ans, "\n");
  220.     }
  221.  
  222. #ifdef DEBUG
  223.     rep_rt();
  224. #endif
  225.     return 0;
  226. }
Success #stdin #stdout 0s 5824KB
comments (?)
stdin
copy 
3 10
2 8 5
6 3 5
1 3 9
1 3
2 2 2
1 10000
2 2 2
0 0
stdout
copy 
848
19
999999999992
https://ideone.com/NUFn6z
problem WILD, based on SPOJ submission 17607742 (C++14), 2016-08-29 18:34:27
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
secret

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!