# |
Author |
Problem |
Lang |
Verdict |
Time |
Memory |
Sent |
Judged |
|
141427385 |
Practice:
Akpr |
1284B
- 29
|
GNU C++17
|
Happy New Year!
|
93 ms
|
3896 KB
|
2022-01-02 21:02:33 |
2022-01-02 21:02:33 |
|
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fo(i,n) for(i=0;i<n;i++)
ll i,n;
int binarySearchCount1(ll arr[], int n, int key)
{
int left = 0;
int right = n - 1;
int count = 0;
while (left <= right) {
int mid = (right + left) / 2;
if (arr[mid] <= key) {
count = mid + 1;
left = mid + 1;
}
else
right = mid - 1;
}
return n - count;
}
void solve(){
ll n;
cin >> n;
ll i;
ll yes = 0;
ll no = 0;
ll check[n];
vector<pair<ll,ll>> vp;
for(i =0 ; i < n;i++){
ll sz ;
cin >> sz;
ll j;
ll flag = 0;
ll v1[sz];
// vector<ll> v1;
for(j =0 ; j< sz;j++){
cin >> v1[j];
}
for(j =1 ;j< sz;j++){
if(v1[j] > v1[j-1]){
flag =1 ;
break;
}
}
if(flag == 0){
check[i] = -1;
no++;
}else {
check[i] = 1;
yes++;
}
if(check[i] == -1){
ll maxel = INT_MIN;
ll minel = INT_MAX;
ll j;
for(j =0 ; j< sz;j++){
if(v1[j] > maxel)maxel = v1[j];
if(v1[j] < minel)minel = v1[j];
}
vp.push_back({maxel,minel});
}
}
ll ans = 0;
ans = yes*yes + 2*yes*no;
ll maxel[vp.size()];
sort(vp.begin(),vp.end());
for(i =0 ; i < vp.size();i++){
maxel[i] = vp[i].first;
}
for(i =0; i< vp.size();i++){
ll t1 = binarySearchCount1(maxel,vp.size(),vp[i].second);
if(vp[i].second != vp[i].first)t1--;
ans = ans + t1;
}
ll count =0;
for(i =0 ; i < vp.size();i++){
if(vp[i].first != vp[i].second)count++;
}
cout << ans + count ;
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int t=1;
//cin>>t;
while(t--){
solve();
cout << endl;
}
}
Click to see test details