孩子已经调崩溃了。。。
  • 板块CF12D Ball
  • 楼主YamadaRyou
  • 当前回复0
  • 已保存回复0
  • 发布时间2021/6/25 17:25
  • 上次更新2023/11/4 21:31:12
查看原帖
孩子已经调崩溃了。。。
203008
YamadaRyou楼主2021/6/25 17:25

样例过了,然后 0pts0\text{pts}。。。

思路和第四篇题解一样。

// 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;
}
2021/6/25 17:25
加载中...