样例过了,然后 0pts。。。
思路和第四篇题解一样。
// Problem: CF12D Ball
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF12D
// Memory Limit: 250 MB
// Time Limit: 2000 ms
// Powered by CP Editor (https://cpeditor.org)
#include <algorithm>
#include <stdio.h>
const int maxnlogw = 15e6 + 2, maxn = 5e5 + 1;
inline int max( int a, int b ) {
return a > b ? a : b;
}
int n, maxw;
struct tree {
int a[ maxnlogw ], lc[ maxnlogw ], rc[ maxnlogw ], cnt = 1;
int _query( int x, int ql, int qr, int l, int r ) {
if ( ql <= l && r <= qr )
return a[ x ];
int mid = l + r >> 1, ans = 0;
if ( ql <= mid )
ans = lc[ x ] ? max( ans, _query( lc[ x ], ql, qr, l, mid ) ) : ans;
if ( mid < qr )
ans = rc[ x ] ? max( ans, _query( rc[ x ], ql, qr, mid + 1, r ) ) : ans;
return ans;
}
int query( int l, int r ) {
return _query( 1, l, r, 1, maxw );
}
void _set( int x, int y, int k, int l, int r ) {
if ( l == r ) {
a[ x ] = k;
return;
}
int mid = l + r >> 1;
if ( y <= mid )
_set( lc[ x ] = ( lc[ x ] ? lc[ x ] : ++cnt ), y, k, l, mid );
else
_set( rc[ x ] = ( rc[ x ] ? rc[ x ] : ++cnt ), y, k, mid + 1, r );
a[ x ] = max( a[ lc[ x ] ], a[ rc[ x ] ] );
}
void set( int x, int y ) {
_set( 1, x, y, 1, maxw );
}
} t;
struct node {
int a, b, c;
bool operator<( const node &o ) const {
return a != o.a ? a > o.a : b > o.b;
}
} a[ maxn ];
int main( ) {
scanf( "%d", &n );
for ( int i = 1; i <= n; ++i )
scanf( "%d", &a[ i ].a );
for ( int i = 1; i <= n; ++i )
scanf( "%d", &a[ i ].b ), maxw = max( maxw, a[ i ].b );
for ( int i = 1; i <= n; ++i )
scanf( "%d", &a[ i ].c );
std::sort( a + 1, a + n + 1 );
t.set( a[ 1 ].b, a[ 1 ].c );
int ans = 0;
for ( int i = 2; i <= n; ++i ) {
if ( t.query( a[ i ].b + 1, maxw ) > a[ i ].c )
++ans;
else
t.set( a[ i ].b, a[ i ].c );
}
printf( "%d", ans );
return 0;
}