社区讨论
哪位大佬可以告诉我为何会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 条回复,欢迎继续交流。
正在加载回复...