Advertisement
BaoJIaoPisu

Untitled

Apr 22nd, 2022
114
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.10 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. #define fi first
  3. #define se second
  4. #define pb push_back
  5. #define pf push_front
  6. #define popb pop_back
  7. #define popf pop_front
  8. #define ins insert
  9. #define pq priority_queue
  10. #define minele min_element
  11. #define maxele max_element
  12. #define lb lower_bound
  13. #define ub upper_bound
  14. #define cnt_bit __builtin_popcount
  15. #define debug(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
  16. using namespace std;
  17.  
  18. typedef long long ll;
  19. typedef pair<ll, ll> pll;
  20. typedef pair<int, int> pii;
  21.  
  22.  
  23. int d4x[4] = {1, 0, -1, 0}; int d4y[4] = {0, 1, 0, -1};
  24. int d8x[8] = {0, 1, 1, 1, 0, -1, -1, -1};
  25. int d8y[8] = {1, 1, 0, -1, -1, -1, 0, 1};
  26.  
  27. const ll oo = 1e18;
  28. const ll maxN = 5000;
  29.  
  30. void maximize(int &a, int b) {
  31.     a = max(a, b);
  32. }
  33.  
  34. void minimize(int &a, int b) {
  35.     a = min(a, b);
  36. }
  37.  
  38. struct P {
  39.     int x, y, z;
  40. } f[maxN];
  41. struct F {
  42.     int x, y, id;
  43. } a[maxN];
  44. int resL[maxN], resR[maxN];
  45.  
  46. bool cmp(F _a, F _b) {
  47.     if(max(_a.x, _a.y) == max(_b.x, _b.y)) {
  48.         return min(_a.x, _a.y) < min(_b.x, _b.y);
  49.     }
  50.  
  51.     return max(_a.x, _a.y) < max(_b.x, _b.y);
  52. }
  53.  
  54. bool ok(P a, P b) {
  55.     if(a.x < b.x) return true;
  56.     else {
  57.         if(a.x == b.x) {
  58.             if(a.y < b.y) return true;
  59.             else {
  60.                 if(a.y == b.y) {
  61.                     if(a.z <= b.z) return true;
  62.                     else return false;
  63.                 } else return false;
  64.             }
  65.         } else return false;
  66.     }
  67. }
  68.  
  69. void merge(P &a) {
  70.     if(a.x < a.y) swap(a.x, a.y);
  71.     if(a.x < a.z) swap(a.x, a.z);
  72.     if(a.y < a.z) swap(a.y, a.z);
  73.  
  74.     if(a.y == a.z) {
  75.         a.y++; a.z = 0;
  76.     }
  77.  
  78.     if(a.x == a.y) {
  79.         a.x++; a.y = 0;
  80.     }
  81.  
  82.     if(a.x < a.y) swap(a.x, a.y);
  83.     if(a.x < a.z) swap(a.x, a.z);
  84.     if(a.y < a.z) swap(a.y, a.z);
  85. }
  86.  
  87. void solve() {
  88.     int n; cin >> n;
  89.     for(int i = 1; i <= n; i++) cin >> a[i].x;
  90.     for(int i = 1; i <= n; i++) cin >> a[i].y;
  91.     for(int i = 1; i <= n; i++) a[i].id = i;
  92.     sort(a + 1, a + 1 + n, cmp);
  93.    
  94.     // thu hang tot nhat
  95.     for(int i = 1; i <= n; i++) {
  96.         f[i].x = a[i].x, f[i].y = a[i].y, f[i].z = 1;
  97.         merge(f[i]);
  98.  
  99.         int d = 2, ans = 0;
  100.         for(int j = n; j >= 1; j--) {
  101.             if(d > n) break;
  102.             if(j == i) continue;
  103.             f[j].x = a[j].x, f[j].y = a[j].y, f[j].z = d;
  104.             merge(f[j]);
  105.             while(!ok(f[i], f[j]) && d < n) {
  106.                 d++;
  107.                 f[j].x = a[j].x; f[j].y = a[j].y; f[j].z = d;
  108.                 merge(f[j]);
  109.             }
  110.  
  111.             d++;
  112.  
  113.             if(ok(f[i], f[j])) ans++;
  114.         }
  115.  
  116.         resL[a[i].id] = n - ans;
  117.     }
  118.  
  119.     for(int i = 1; i <= n; i++) {
  120.         f[i].x = a[i].x, f[i].y = a[i].y, f[i].z = n;
  121.         merge(f[i]);
  122.  
  123.         int d = n - 1, ans = 0;
  124.         for(int j = 1; j <= n; j++) {
  125.             if(d < 1) break;
  126.             if(j == i) continue;
  127.             f[j].x = a[j].x, f[j].y = a[j].y, f[j].z = d;
  128.             merge(f[j]);
  129.             while(ok(f[i], f[j]) && d > 1) {
  130.                 d--;
  131.                 f[j].x = a[j].x; f[j].y = a[j].y; f[j].z = d;
  132.                 merge(f[j]);
  133.             }
  134.  
  135.             d--;
  136.  
  137.             if(!ok(f[i], f[j])) ans++;
  138.         }
  139.  
  140.         resR[a[i].id] = ans + 1;
  141.     }
  142.  
  143.     for(int i = 1; i <= n; i++) {
  144.         cout << resL[i] << " " << resR[i] << "\n";
  145.     }
  146. }
  147.  
  148. int main()
  149. {
  150.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  151.     #ifndef ONLINE_JUDGE
  152.     freopen("input.txt", "r", stdin);
  153.     freopen("output.txt", "w", stdout);
  154.     #else
  155.     //online
  156.     #endif
  157.     solve();
  158. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement