Tranvick

Untitled

Feb 14th, 2012
183
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.08 KB | None | 0 0
  1. #pragma comment(linker, "/STACK:65777216")
  2. #include <iostream>
  3. #include <iomanip>
  4. #include <cstdlib>
  5. #include <ctime>
  6. #include <cstdio>
  7. #include <algorithm>
  8. #include <cmath>
  9. #include <vector>
  10. #include <set>
  11. #include <stack>
  12. #include <map>
  13. #include <queue>
  14. #include <string>
  15. #include <memory.h>
  16. #include <iterator>
  17. #define mem(A,X) memset(A,X,sizeof(A))
  18. #define memo(A) memset(A,0,sizeof(A))
  19. #define forn(I,B) for (int I=1;I<=(B);I++)
  20. #define forg(H,V) for (int H=first[V];h;h=next[H])
  21. #define rep(I,B) for (int I=0;I<(B);I++)
  22. #define labs(X) (((X)>0)?(X):(-(X)))
  23. #define ropen(X) freopen(X,"r",stdin)
  24. #define wopen(X) freopen(X,"w",stdout)
  25. #define rwopen(X) freopen(X".in","r",stdin);freopen(X".out","w",stdout)
  26. #define pb push_back
  27. #define mp make_pair
  28. #define all(X) (X).begin(),(X).end()
  29. #define sqr(X) ((X)*(X))
  30.  
  31. using namespace std;
  32.  
  33. typedef pair <int,int> pii;
  34. typedef long double ld;
  35. typedef unsigned long long  ll;
  36. typedef pair <ll,ll> pll;
  37. typedef vector<int> vi;
  38. const int N=5555;
  39. const int INF=1111111;
  40. const double eps=1e-9;
  41. const double pi=3.14159265358979;
  42.  
  43. int n,ta[N],tb[N],buf[N+N],ptr,t[N],bg,ans=-1,cx;
  44. char tc[N];
  45. bool c[N+N],cv[N+N];
  46.  
  47. int main(){
  48. //  ropen("input.txt");
  49.     scanf("%d\n",&n);
  50.     forn(i,n){
  51.         scanf("%d %d %c\n",&ta[i],&tb[i],&tc[i]);
  52.         buf[++ptr]=ta[i];
  53.         buf[++ptr]=tb[i];
  54.     }
  55.     buf[++ptr]=0;buf[++ptr]=1000000000;
  56.     sort(buf+1,buf+ptr+1);ptr=0;
  57.     forn(i,n+n+2) if (buf[i]!=buf[i+1]) t[++ptr]=buf[i];
  58.     forn(i,n){
  59.         int a=ta[i],b=tb[i];
  60.         bool k=tc[i]=='b';
  61.         forn(j,ptr){
  62.             if (t[j]>b) break;
  63.             if (t[j]>=a && t[j]<b) cv[j]=k;
  64.             if (j!=ptr && t[j]>=a && t[j+1]<=b) c[j]=k;
  65.         }
  66.     }
  67.     cx=-1;
  68.     forn(i,ptr){
  69.         if (!cv[i] && cx==-1) cx=t[i];
  70.         if (cv[i] && cx!=-1){
  71.             if (t[i]-cx>ans){
  72.                 bg=cx;
  73.                 ans=t[i]-cx;
  74.             }
  75.             cx=-1;
  76.         }
  77.         if (i==ptr) break;
  78.         if (!c[i] && cx==-1 && t[i]+1!=t[i+1]) cx=t[i]+1;
  79.         if (c[i] && cx!=-1){
  80.             if (t[i+1]-cx>ans){
  81.                 bg=cx;
  82.                 ans=t[i]-cx;
  83.             }
  84.             cx=-1;
  85.         }
  86.     }
  87.     if (1000000000-cx>ans) printf("%d %d\n",cx,1000000000);
  88.     else printf("%d %d\n",bg,bg+ans);
  89.     return 0;
  90. }
Advertisement
Add Comment
Please, Sign In to add comment