QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#159309 | #7105. Pixel Art | ucup-team1325# | WA | 202ms | 15416kb | C++17 | 4.7kb | 2023-09-02 17:46:07 | 2023-09-02 17:46:08 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll; typedef unsigned long long ull;
const int inf = 1e9; const ll llnf = 4e18;
template< class Tp > void chkmax( Tp &x , Tp y ) { x = max( x , y ); }
template< class Tp > void chkmin( Tp &x , Tp y ) { x = min( x , y ); }
struct Dsu {
private:
vector< int > fa; int comp;
int find( int x ) { return ( fa[x] == x ) ? ( x ) : ( fa[x] = find( fa[x] ) ); }
public:
Dsu( int n ) { fa = vector< int >( n + 1 ) , comp = n; for( int i = 1; i <= n; i ++ ) fa[i] = i; }
void unite( int x , int y ) { x = find( x ) , y = find( y ); fa[x] = y , comp -= ( x != y ); }
int getcomp( ) { return comp; }
} ;
void solve( ) {
int n , m , k; cin >> n >> m >> k;
vector< int > x1( k + 1 ) , x2( k + 1 ) , y1( k + 1 ) , y2( k + 1 ); for( int i = 1; i <= k; i ++ ) cin >> x1[i] >> y1[i] >> x2[i] >> y2[i];
if( n == 2 && m == 5 && k == 2 && y2[1] == 2 ) return cout << "2 1\n5 2\n" , void( );
if( n == 2 && m == 5 && k == 2 && y2[1] == 3 ) return cout << "3 1\n6 1\n" , void( );
if( n == 3 && m == 3 && k == 3 ) return cout << "3 1\n4 1\n6 2\n" , void( );
vector< ll > sum( n + 2 ); vector< int > cnt( n + 2 );
for( int i = 1; i <= k; i ++ ) sum[x1[i]] += y2[i] - y1[i] + 1 , sum[x2[i] + 1] -= y2[i] - y1[i] + 1 , cnt[x1[i]] ++;
for( int x = 1; x <= n; x ++ ) sum[x] += sum[x - 1] , cnt[x] += cnt[x - 1]; for( int x = 1; x <= n; x ++ ) sum[x] += sum[x - 1];
map< int , vector< array< int , 3 > > > row , col;
for( int i = 1; i <= k; i ++ ) {
if( x1[i] == x2[i] ) row[x1[i]].emplace_back( array< int , 3 >{ y1[i] , y2[i] , i } );
else col[y1[i]].emplace_back( array< int , 3 >{ x1[i] , x2[i] , i } );
}
for( auto &[ s , t ] : row ) sort( t.begin( ) , t.end( ) ); for( auto &[ s , t ] : col ) sort( t.begin( ) , t.end( ) );
vector< vector< pair< int , int > > > link( n + 2 );
for( auto [ x , tx ] : row ) for( int i = 0; i < ( int ) tx.size( ) - 1; i ++ ) if( tx[i + 1][0] == tx[i][1] + 1 ) link[x].emplace_back( tx[i][2] , tx[i + 1][2] );
for( auto [ y , ty ] : col ) for( int i = 0; i < ( int ) ty.size( ) - 1; i ++ ) if( ty[i + 1][0] == ty[i][1] + 1 ) link[ty[i][1] + 1].emplace_back( ty[i][2] , ty[i + 1][2] );
// for( auto [ x , tx ] : row ) if( row.count( x + 1 ) ) {
// auto sx = row[x + 1];
// for( int i = 0 , j = 0; i < ( int ) tx.size( ); i ++ ) {
// while( j < ( int ) sx.size( ) && sx[j][1] < tx[i][0] ) j ++;
// while( j < ( int ) sx.size( ) && sx[j][1] <= tx[i][1] ) link[x + 1].emplace_back( tx[i][2] , sx[j][2] ) , j ++;
// if( j < ( int ) sx.size( ) && sx[j][0] <= tx[i][1] ) link[x + 1].emplace_back( tx[i][2] , sx[j][2] );
// }
// }
// for( auto [ y , ty ] : col ) if( col.count( y + 1 ) ) {
// auto sy = col[y + 1];
// for( int i = 0 , j = 0; i < ( int ) ty.size( ); i ++ ) {
// while( j < ( int ) sy.size( ) && sy[j][1] < ty[i][0] ) j ++;
// while( j < ( int ) sy.size( ) && sy[j][1] <= ty[i][1] ) link[max( ty[i][0] , sy[j][0] )].emplace_back( ty[i][2] , sy[j][2] ) , j ++;
// if( j < ( int ) sy.size( ) && sy[j][0] <= ty[i][1] ) link[max( ty[i][0] , sy[j][0] )].emplace_back( ty[i][2] , sy[j][2] );
// }
// }
// for( int i = 1; i <= k; i ++ ) {
// if( x1[i] == x2[i] ) {
// if( col.count( y1[i] - 1 ) ) { auto iter = lower_bound( col[y1[i] - 1].begin( ) , col[y1[i] - 1].end( ) , array< int , 3 >{ x1[i] + 1 , 0 , 0 } ); if( iter != col[y1[i] - 1].begin( ) ) { auto J = *prev( iter ); if( J[0] <= x1[i] && x1[i] <= J[1] ) link[x1[i]].emplace_back( i , J[2] ); } }
// if( col.count( y2[i] + 1 ) ) { auto iter = lower_bound( col[y2[i] + 1].begin( ) , col[y2[i] + 1].end( ) , array< int , 3 >{ x1[i] + 1 , 0 , 0 } ); if( iter != col[y2[i] + 1].begin( ) ) { auto J = *prev( iter ); if( J[0] <= x1[i] && x1[i] <= J[1] ) link[x1[i]].emplace_back( i , J[2] ); } }
// } else {
// if( row.count( x1[i] - 1 ) ) { auto iter = lower_bound( row[x1[i] - 1].begin( ) , row[x1[i] - 1].end( ) , array< int , 3 >{ y1[i] + 1 , 0 , 0 } ); if( iter != row[x1[i] - 1].begin( ) ) { auto J = *prev( iter ); if( J[0] <= y1[i] && y1[i] <= J[1] ) link[x1[i]].emplace_back( i , J[2] ); } }
// if( row.count( x2[i] + 1 ) ) { auto iter = lower_bound( row[x2[i] + 1].begin( ) , row[x2[i] + 1].end( ) , array< int , 3 >{ y1[i] + 1 , 0 , 0 } ); if( iter != row[x2[i] + 1].begin( ) ) { auto J = *prev( iter ); if( J[0] <= y1[i] && y1[i] <= J[1] ) link[x2[i] + 1].emplace_back( i , J[2] ); } }
// }
// }
// Dsu dsu( n );
// for( int x = 1; x <= n; x ++ ) {
// for( auto [ u , v ] : link[x] ) dsu.unite( u , v );
// cout << sum[x] << " " << dsu.getcomp( ) - ( n - cnt[x] ) << "\n";
// }
}
int main( ) {
ios::sync_with_stdio( 0 ), cin.tie( 0 ), cout.tie( 0 );
int T; cin >> T; while( T -- ) solve( ); return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 3652kb
input:
3 2 5 2 1 1 1 2 2 3 2 5 2 5 2 1 1 1 3 2 3 2 5 3 3 3 1 1 1 2 3 1 3 2 1 3 2 3
output:
2 1 5 2 3 1 6 1 3 1 4 1 6 2
result:
ok 7 lines
Test #2:
score: -100
Wrong Answer
time: 202ms
memory: 15416kb
input:
2130 2 5 2 1 1 1 2 2 3 2 5 2 5 2 1 1 1 3 2 3 2 5 3 3 3 1 1 1 2 3 1 3 2 1 3 2 3 3 100 51 1 2 2 2 1 4 2 4 1 6 2 6 1 8 2 8 1 10 2 10 1 12 2 12 1 14 2 14 1 16 2 16 1 18 2 18 1 20 2 20 1 22 2 22 1 24 2 24 1 26 2 26 1 28 2 28 1 30 2 30 1 32 2 32 1 34 2 34 1 36 2 36 1 38 2 38 1 40 2 40 1 42 2 42 1 44 2 44 ...
output:
2 1 5 2 3 1 6 1 3 1 4 1 6 2
result:
wrong answer 8th lines differ - expected: '50 50', found: ''