Advertisement
Guest User

Untitled

a guest
May 15th, 2013
119
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.62 KB | None | 0 0
  1. #pragma comment(linker,"/STACK:64000000")
  2. #define _CRT_SECURE_NO_WARNINGS
  3. #include <iostream>
  4. #include <vector>
  5. #include <string>
  6. #include <sstream>
  7. #include <cmath>
  8. #include <map>
  9. #include <set>
  10. #include <ctime>
  11. #include <algorithm>
  12. #include <memory.h>
  13. #include <stdio.h>
  14. #include <stdlib.h>
  15.  
  16. using namespace std;
  17.  
  18. #define WR printf
  19. #define RE scanf
  20. #define PB push_back
  21. #define SE second
  22. #define FI first
  23.  
  24. #define FOR(i,k,n) for(int i=(k); i<=(n); i++)
  25. #define DFOR(i,k,n) for(int i=(k); i>=(n); i--)
  26. #define SZ(a) (int)((a).size())
  27. #define FA(i,v) FOR(i,0,SZ(v)-1)
  28. #define RFA(i,v) DFOR(i,SZ(v)-1,0)
  29. #define CLR(a) memset(a, 0, sizeof(a))
  30.  
  31. #define LL long long
  32. #define VI  vector<int>
  33. #define PAR pair<int ,int>
  34. #define o_O 1000000000
  35.  
  36. void __never(int a){printf("\nOPS %d", a);}
  37. #define ass(s) {if (!(s)) {__never(__LINE__);cout.flush();cerr.flush();abort();}}
  38.  
  39. #define BSZ 1000
  40.  
  41. struct SQRTD
  42. {
  43.     int t[2000100];
  44.     int mi[2010];
  45.     void clear()
  46.     {
  47.         CLR(t);
  48.         CLR(mi);
  49.     }
  50.     int get_min( int x, int y )
  51.     {
  52.         int re = o_O;
  53.         int i = 0, j = 0;
  54.         while (i <= y)
  55.         {
  56.             if (x<=i && i+BSZ-1<=y) re = min( re, mi[j] );
  57.             else
  58.             {
  59.                 int mn = max( x, i );
  60.                 int mx = min( y, i+BSZ-1 );
  61.                 FOR(a,mn,mx)
  62.                     re = min( re, max( t[a], mi[j] ) );
  63.             }
  64.  
  65.             i+=BSZ;
  66.             j++;
  67.         }
  68.         return re;
  69.     }
  70.  
  71.     void set_min( int x, int y, int s )
  72.     {
  73.         int i = 0, j = 0;
  74.         while (i <= y)
  75.         {
  76.             if (x<=i && i+BSZ-1<=y) mi[j] = max( mi[j], s );
  77.             else
  78.             {
  79.                 int mn = max( x, i );
  80.                 int mx = min( y, i+BSZ-1 );
  81.                 if (mn<=mx)
  82.                 {
  83.                     FOR(a,i,i+BSZ-1) t[a] = max( t[a], mi[j] );
  84.                     FOR(a,mn,mx) t[a] = max( t[a], s );
  85.                     mi[j] = o_O;
  86.                     FOR(a,i,i+BSZ-1) mi[j] = min( mi[j], t[a] );
  87.                 }
  88.             }
  89.  
  90.             i+=BSZ;
  91.             j++;
  92.         }
  93.     }
  94. } sq;
  95.  
  96. struct QUE
  97. {
  98.     int x, y, s, t;
  99.     bool build;
  100.     QUE( int _x=0, int _y=0, int _s=0, int _t=0, bool _b=false )
  101.     {
  102.         x=_x; y=_y; s=_s; t=_t; build=_b;
  103.     }
  104. };
  105.  
  106. bool le( const QUE & A, const QUE & B )
  107. {
  108.     if (A.t != B.t) return A.t < B.t;
  109.     return A.build < B.build;
  110. }
  111.  
  112. QUE Q[2000100];
  113. int q_sz;
  114. map< int, int > Map;
  115.  
  116. int A[300];
  117.  
  118. void scale()
  119. {
  120.     Map.clear();
  121.  
  122.     FOR(a,0,q_sz-1)
  123.     {
  124.         Map[Q[a].x] = 0;
  125.         Map[Q[a].y+1] = 0;
  126.     }
  127.  
  128.     int ii=0;
  129.     for (map< int, int >::iterator it = Map.begin(); it != Map.end(); it++)
  130.         it->second = ii++;
  131.  
  132.     FOR(a,0,q_sz-1)
  133.     {
  134.         Q[a].x = Map[Q[a].x];
  135.         Q[a].y = Map[Q[a].y+1]-1;
  136.     }
  137.  
  138.     ass( SZ(Map) < 2000100 );
  139. }
  140.  
  141. void stupid()
  142. {
  143.     CLR(A);
  144.     int ans = 0;
  145.     FOR(a,0,q_sz-1)
  146.         if (Q[a].build)
  147.         {
  148.             FOR(c,Q[a].x,Q[a].y) A[c] = max( A[c], Q[a].s );
  149.         }
  150.         else
  151.         {
  152.             FOR(c,Q[a].x,Q[a].y)
  153.                 if (A[c] < Q[a].s)
  154.                 {
  155.                     ans++;
  156.                     break;
  157.                 }
  158.         }
  159.  
  160.     cout << ans;
  161. }
  162.  
  163. void sol2()
  164. {
  165.     sq.clear();
  166.     int ans = 0;
  167.     FOR(a,0,q_sz-1)
  168.         if (Q[a].build)
  169.         {
  170.             sq.set_min(Q[a].x, Q[a].y, Q[a].s);
  171.         }
  172.         else
  173.         {
  174.             int tmp = sq.get_min(Q[a].x, Q[a].y);
  175.             if (tmp < Q[a].s) ans++;
  176.         }
  177.  
  178.     cout << ans;
  179. }
  180.  
  181. void sol()
  182. {
  183.     sort( Q, Q+q_sz, le );
  184.     scale();
  185.  
  186.     //stupid();
  187.     //cout << " ";
  188.     sol2();
  189. }
  190.  
  191. int main()
  192. {
  193.     freopen("input.txt","r",stdin);
  194.     freopen("output.txt","w",stdout);
  195.  
  196.     int T;
  197.     cin >> T;
  198.     FOR(a,1,T)
  199.     {
  200.         cerr << a;
  201.         q_sz = 0;
  202.  
  203.         int n;
  204.         RE("%d", &n);
  205.         FOR(b,1,n)
  206.         {
  207.             int ti, ni, wi, ei, si, dt, dp, ds;
  208.             RE("%d%d%d%d%d%d%d%d", &ti, &ni, &wi, &ei, &si, &dt, &dp, &ds );
  209.             FOR(c,1,ni)
  210.             {
  211.                 Q[q_sz++] = QUE( wi, ei-1, si, ti, false );
  212.                 Q[q_sz++] = QUE( wi, ei-1, si, ti, true );
  213.                 wi+=dp; ei+=dp;
  214.                 ti+=dt;
  215.                 si+=ds;
  216.                 ass( q_sz < 2000100 );
  217.             }
  218.         }
  219.         cout << "Case #" << a << ": ";
  220.         sol();
  221.         cout << "\n";
  222.         cerr << " ok\n";
  223.     }
  224.  
  225.     return 0;
  226. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement