fork(1) download
copy 
  1. #include <iostream>
  2. //#include <fstream>
  3. #include <sstream>
  4. #include <cstdio>
  5. #include <cstring>
  6. #include <string>
  7. #include <cmath>
  8. #include <algorithm>
  9. //#include <map>
  10. #include <stack>
  11. #include <queue>
  12. #include <vector>
  13. //#include <deque>
  14. #include <functional>
  15. #include <ctime>
  16. #include <cstdlib>
  17. #include <iomanip>
  18.  
  19. using namespace std;
  20. typedef long long LL;
  21.  
  22. #define F(a,b) for(int a=0;a<b;++a)
  23.  
  24. const int Max = 200001;
  25.  
  26. LL ans,k,m;;
  27. pair<LL,LL> s[Max],tmp[Max];
  28.  
  29. void Count(int L,int M,int R){
  30.     int i = L,j = M+1,pos = 0;
  31.     while(i<=M && j<=R){
  32.         if(s[i].first < s[j].first && s[i].second > s[j].second){
  33.             tmp[pos++] = s[j++];
  34.             ans += M - i + 1;
  35.         }
  36.         else tmp[pos++] = s[i++];
  37.     }
  38.     while(i <= M)tmp[pos++] = s[i++];
  39.     while(j <= R)tmp[pos++] = s[j++];
  40.     int now = 0;
  41.     while(now < pos)s[L++] = tmp[now++];
  42. }
  43.  
  44.  
  45. void Divide(int L,int R){
  46.     if(L == R)return;
  47.     int M = (L+R)/2;
  48.     Divide(L,M);
  49.     Divide(M+1,R);
  50.     Count(L,M,R);
  51. }
  52.  
  53. int main(){
  54.     while(~scanf("%lld%lld",&k,&m)){
  55.         ans = 0;
  56.         F(i,k)scanf("%lld",&s[i].first);
  57.         F(i,k)scanf("%lld",&s[i].second);
  58.         sort(s,s+k);
  59.         Divide(0,(int)k-1);
  60.         printf("%lld\n",ans);
  61.     }
  62. }
  63.  
  64.  
  65.  
Success #stdin #stdout 0s 9552KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/yhOc5k
language:
C++ (gcc 8.3)
created:
12 years 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!