社区讨论

哪位大佬可以告诉我为何会TLE

P14228 [ICPC 2024 Kunming I] 漫步野径参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@mhiyt782
此快照首次捕获于
2025/11/03 17:56
4 个月前
此快照最后确认于
2025/11/03 17:56
4 个月前
查看原帖
按理来说,应该是O(nlogn)啊。
rt:
CPP
#include<bits/stdc++.h>
using namespace std ; 
#define int long long 

const int N = 3e6 + 10 ; 
namespace fastIO {
    template<typename T> inline void read(T &x) {
        x = 0; char ch = getchar(); bool f = 0;
        for (; ch < '0' || ch > '9'; ch = getchar()) f ^= (ch == '-');
        for (; ch >= '0' && ch <= '9'; ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
        if (f) x = -x;
    }
    template<typename T> inline void write(T x) {
        if (x == 0) { putchar('0'); return; }
        static char stk[100]; int top = 0;
        if (x < 0) { putchar('-'); x = -x; }
        for (; x; x /= 10) stk[++top] = (x % 10) ^ 48;
        for (; top; --top) putchar(stk[top]);
    }
    struct IO {
        template<typename T> inline IO& operator>>(T &x) { read(x); return *this; }
        template<typename T> inline IO& operator<<(const T &x) { write(x); return *this; }
    } in, out;
}
using fastIO::in; using fastIO::out;

int n ; 
vector< int > innode[ N ] ; 
vector< int > node ;
int q , p ; 

signed main() 
{
    int T ; 
    time_t a = clock() ; 
    in >> T ; 
    while( T -- ) 
    {
        in >> n >> q >> p ; 
        int ans = ( q + 1 ) * ( p + 1 ) * ( q + p ) / 2 ; 
        int now_ans = 0 ; 
        for( int i = 1 ; i <= q ; i ++ ) innode[ i ].clear() ; 
        for( int i = 1 ; i <= n ; i ++ ) 
        {
            int x , y ; 
            in >> x >> y ; 
            if( x >= p && y >= q ) continue ; 
            innode[ x + 1 ].push_back( -y - 1 ) ; 
        }
        for( int i = 1 ; i <= q ; i ++ ) 
        {
            if( innode[ i ].size() != 0 ) 
                sort( innode[ i ].begin() , innode[ i ].end() ) ; 
        } 
        node.clear() ; 
        for( int i = 1 ; i <= q ; i ++ ) 
        {
            if( innode[ i ].size( ) == 0 ) continue ; 
            for( vector< int >::iterator it = innode[ i ].begin() ; it != innode[ i ].end() ; it ++ ) 
            {
                // if( abs ( *it ) > p ) continue ; 
                if( node.size() == 0 ) 
                {
                    node.push_back( abs( *it ) ) ; 
                    now_ans += ( p - abs( *it ) + 1 ) ; 
                    continue ; 
                }
                vector< int >::iterator it1 = lower_bound( node.begin( ) , node.end( ) ,  abs( *it ) ) ; 
                if(  it1 != node.end() && *it1 == abs( *it ) ) 
                    continue ; 
                it1 = upper_bound( node.begin() , node.end() , abs( *it ) ) ; 
                if( it1 == node.end() ) 
                {
                    node.push_back( abs( *it ) ) ; 
                    now_ans += ( p - abs( *it ) + 1 ) ;  
                }
                else 
                {
                    now_ans -= ( p - *it1 + 1 ) ; 
                    int l = it1 - node.begin() ; 
                    node[ l ] = abs( *it ) ; 
                    now_ans += ( p - abs( *it ) + 1 ) ; 
                }
            }
            ans -= now_ans ; 
        }
        out << ans ; 
        puts( "" ) ; 
    }
    // cerr << ( clock() - a ) / ( CLOCKS_PER_SEC ) ; 
}

回复

0 条回复,欢迎继续交流。

正在加载回复...