fork download 
  1. #include <iostream>
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4.  
  5.  
  6. int merge(vector<int>&v,int s,int mid,int h){
  7.  
  8.     int i = s;
  9.  
  10.     int j= mid +1;
  11.     int k =0;
  12.     int invent = 0;
  13.     vector<int> temp(h-s +1);
  14.     while(i<=mid && j<=h){
  15.         if(v[j]> v[i]){
  16.             temp[k++] =v[i++];
  17.         } else {
  18.             invent =  mid -i+1;
  19.             temp[k++] =v[j++];
  20.         }
  21.     }
  22.  
  23.  
  24.     while(i<=mid){
  25.        temp[k++] =v[i++]; 
  26.     }
  27.  
  28.     while(j<=h){
  29.        temp[k++] =v[j++]; 
  30.     }
  31.  
  32.  
  33.     int l =0;
  34.     for(int i = s;i<=h;i++){
  35.         v[i] = temp[l++];
  36.     }
  37.  
  38.     return invent;
  39.  
  40. }
  41.  
  42. int mergeSort(vector<int>&v,int s,int e){
  43.  
  44.     int inven =0;
  45.     if(s<e){
  46.         int mid = s + (e-s)/2;
  47.  
  48.     inven += mergeSort(v,s,mid);
  49.     inven += mergeSort(v,mid+1,e);
  50.  
  51.      inven += merge(v,s,mid,e);
  52.     }
  53.  
  54.     return inven;
  55.  
  56. }
  57.  
  58. int main() {
  59. 	// your code goes here
  60.  
  61. 	int t;
  62.  
  63. 	cin>>t;
  64. 	while(t--){
  65.  
  66. 	    int n;
  67.  
  68. 	    cin>>n;
  69.  
  70. 	    vector<int> v(n);
  71. 	    for(int i=0;i<n;i++){
  72. 	        cin>>v[i];
  73. 	    }
  74.  
  75.  
  76. 	    int localCount =0;
  77. 	    for(int i=0;i<n-1;i++){
  78.  
  79. 	        if(v[i]>v[i+1]){
  80. 	            localCount++;
  81. 	        }
  82. 	    }
  83.  
  84. 	    int icount = mergeSort(v,0,v.size()-1);
  85.  
  86. 	    if(icount == localCount) {
  87. 	        cout<<"YES"<<endl;
  88.  
  89. 	    } else {
  90. 	         cout<<"NO"<<endl;
  91. 	    }
  92.  
  93.  
  94. 	}
  95. 	return 0;
  96. }
  97.  
Success #stdin #stdout 0s 4396KB
comments (?)
stdin 
1
4
1 4 2 3
stdout 
YES
https://ideone.com/URAlXG
language:
C++14 (gcc 8.3)
created:
5 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!