fork download
copy 
  1. // PhuThuyRuntime <3
  2. // A secret makes a woman woman
  3.  
  4. #include <bits/stdc++.h>
  5.  
  6. using namespace std;
  7.  
  8. #define pb push_back
  9. #define fo(i, l, r) for(int i = l; i <= r; i++)
  10. #define foi(i, l, r) for(int i = l; i >= r; i--)
  11. #define elif else if
  12. #define el cout << "\n";
  13. #define pii pair<int, int>
  14. #define pli pair<ll, int>
  15. #define pll pair<ll, ll>
  16. #define pil pair<int, ll>
  17. #define fi first
  18. #define se second
  19. #define in(x) freopen(x, "r", stdin)
  20. #define out(x) freopen(x, "w", stdout)
  21. #define ll long long
  22. #define ull unsigned long long
  23. #define pob pop_back
  24. #define bs binary_search
  25. #define vi vector<int>
  26. #define vii vector<pair<int, int>>
  27. #define getbit(i, j) (i >> j) & 1
  28. #define offbit(i, j) (1 << j) ^ i
  29. #define onbit(i, j) (1 << j) | i
  30. const int N = 1e5 + 2;
  31. const ll mod = 1e9 + 7;
  32. const int inf = INT_MAX;
  33. const int base = 31;
  34. const long double EPS = 1e-9;
  35. const long double pi = acos(-1.0);
  36. int n;
  37. pii a[2002];
  38. void inp(){
  39.      cin >> n;
  40.      fo(i, 1, n) cin >> a[i].fi;
  41.      fo(i, 1, n) cin >> a[i].se;
  42. }
  43. bool cmp(pii a, pii b){
  44.      return a.fi > b.fi;
  45. }
  46. ll dp[2][2002];
  47. ll bit[2002];
  48. void update(int u, ll val){
  49.      while(u <= n){
  50.           bit[u] = (bit[u] + val) % mod;
  51.           u += u & -u;
  52.      }
  53. }
  54. ll get(int u){
  55.      ll ans = 0;
  56.      while(u){
  57.           ans = (ans + bit[u]) % mod;
  58.           u -= u & -u;
  59.      }
  60.      return ans;
  61. }
  62. void sol(){
  63.      sort(a + 1, a + n + 1, cmp);
  64.      vi zip;
  65.      fo(i, 1, n) zip.emplace_back(a[i].se);
  66.      sort(zip.begin(), zip.end());
  67.      zip.erase(unique(zip.begin(), zip.end()), zip.end());
  68.      fo(j, 1, n){
  69.           ll ans = 0;
  70.           fo(i, 1, n){
  71.                int id = lower_bound(zip.begin(), zip.end(), a[i].se) - zip.begin() + 1;
  72.                dp[j & 1][i] = (j == 1 ? 1 : get(id - 1));
  73.                update(id, dp[(j & 1) ^ 1][i]);
  74.                ans = (ans + dp[j & 1][i]) % mod;
  75.           }
  76.           memset(bit, 0, sizeof(bit));
  77.           cout << ans << ' ';
  78.      }
  79. }
  80. int main(){
  81. //     in("lctour.inp");
  82. //     out("lctour.out");
  83.      ios_base::sync_with_stdio(false);
  84.      cin.tie(NULL); cout.tie(NULL);
  85.      inp();
  86.      sol();
  87.      return 0;
  88. }
  89.  
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
2
5 7 
6 9
stdout
copy 
2 0
https://ideone.com/UhFh7O
language:
C++14 (gcc 8.3)
created:
237 days ago
visibility:
public

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!