QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#297018 | #7105. Pixel Art | ValenciaTravis | AC ✓ | 361ms | 31356kb | C++20 | 4.2kb | 2024-01-03 21:21:38 | 2024-01-03 21:21:39 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define rep(i,j,k) for(int i = j; i <= k; ++i)
#define repp(i,j,k) for(int i = j; i >= k;--i)
#define ll long long
#define pb push_back
#define fr first
#define se second
#define mp make_pair
#define P pair< pair<int,int> , int >
#define One first.first
#define Second first.second
#define Third second
int T;
int n,m,k;
set<P>s;
ll ans1 = 0,ans2 = 0;
int res = 0;
struct node {
int l,r,v;
};
int rd() {
int x = 0; char c = getchar();
while( c < '0' || c > '9' ) c = getchar();
while( c >= '0' && c <= '9' ) x = x*10+c-'0' , c = getchar();
return x;
}
vector<P>tmp;
vector<pair<int,int>>e[2][401000];
int f[401000],cnt = 0;
P G(int a,int b,int c) {
return make_pair( make_pair(a,b) , c );
}
bool interact( set<P>::iterator &it , int l , int r ) {
if( it == s.end() ) return false;
int L = it->One , R = it->Second;
// printf("#%d %d\n",L,R);
if( R < l || r < L ) return false;
return true;
}
int get(int x) {
if( f[x] == x ) return f[x];
f[x] = get( f[x] );
return f[x];
}
void merge(int x,int y) {
int fx = get(x) , fy = get(fy);
if( fx != fy ) {
f[fx] = fy;
ans2--;
}
}
void update( set<P>::iterator &it ,int &id2) {
int id1 = get(it->Third);
if( id2 == -1 ) id2 = id1,++it;
else {
id2 = get(id2); id1 = get(id1);
if(id1 != id2) {
ans2--;
f[id1] = id2;
}
it++;
}
}
void Delete( set<P>::iterator &it , int l, int r ) {
int L = it->One , R = it->Second , id = it->Third;
s.erase( it );
if( l > L ) s.insert( G( L , l-1 , id ) );
if( r < R ) s.insert( G( r+1 , R , id ) );
}
void insert(int l,int r,int id) {
set<P>::iterator it = s.lower_bound( G(l,r,id) );
int id2; id = get(id);
if( it != s.end() && r + 1 == it->One ) {
id2 = get(it->Third);
if( id2 != id ) {
ans2--;
id2 = get(id2); f[id2] = id;
}
r = it->Second;
s.erase(it);
it = s.lower_bound( G(l,r,id) );
}
if( it != s.begin() ) {
it--;
if( l-1 == it->Second ) {
id2 = get(it->Third);
if( id2 != id ) {
ans2--;
id2 = get(id2); f[id2] = id;
}
l = it->One;
s.erase(it);
}
}
s.insert( G(l,r,id) );
}
void output() {
printf("Begin:\n");
for(auto it:s) {
printf("#%d %d %d\n",it.One,it.Second,it.Third);
}
printf("End\n\n");
}
void work() {
rep(row,1,n) {
tmp.clear();
// printf("#%d\n",row);
for(int i = 0;i < e[0][row].size();++i) {
int l = e[0][row][i].fr , r = e[0][row][i].se;
res += r-l+1;
int id = -1;
set<P>::iterator it = s.lower_bound( G(l,r,0) );
if( it != s.begin() ) {
it--;
if( interact( it , l , r ) ) update( it , id );
else it++;
}
// output();
// printf("*%d %d %d %d\n",l,r,id,it == s.end());
while( it != s.end() && interact(it,l,r) ) {
// printf("*%d %d\n",it->One,it->Second);
update( it, id );
}
if( id == -1 ) id = ++cnt , ans2++ , f[id] = id;
tmp.pb( G( l , r , id ) );
}
for(int i = 0;i < e[1][row].size();++i) {
int l = e[1][row][i].fr , r = e[1][row][i].se;
res -= r-l+1;
set<P>::iterator it = s.lower_bound( G(l,r,0) );
// printf("*%d %d\n",l,r);
if( interact( it , l , r ) ) Delete( it , l , r );
else {
assert( it != s.begin() );
it--;
if( interact( it , l , r ) ) Delete( it , l , r );
else assert( 0 );
}
}
for(int i = 0;i < tmp.size();++i) {
int l,r,id;
l = tmp[i].One; r = tmp[i].Second; id = tmp[i].Third;
insert( l , r , get(id) );
}
// output();
ans1 += res;
printf("%lld %lld\n",ans1,ans2);
}
}
bool cmp( node a,node b ) {
if( a.v != b.v ) return a.v > b.v;
else return a.l < b.l;
}
int TTT;
void init() {
n = rd(); m = rd(); k = rd();
rep(i,1,k) {
int r1 = rd(),c1 = rd(),r2 = rd(),c2 = rd();
// if(c1 == 11 && c2 == 1) printf("###%d\n",i);
e[0][r1].push_back( make_pair(c1,c2) );
e[1][r2+1].push_back( make_pair(c1,c2) );
}
rep(i,1,n) sort( e[0][i].begin() , e[0][i].end() ) , sort( e[1][i].begin() , e[1][i].end() );
work();
rep(i,1,n+1) e[0][i].clear() , e[1][i].clear(); cnt = 0;
s.clear();
ans1 = 0; ans2 = 0;
res = 0;
}
int main(){
scanf("%d",&T);
for(TTT = 1;TTT <= T;++TTT) {
init();
}
return 0;
}
这程序好像有点Bug,我给组数据试试?
詳細信息
Test #1:
score: 100
Accepted
time: 3ms
memory: 22724kb
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: 0
Accepted
time: 361ms
memory: 31356kb
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 50 50 100 50 200 1 50 50 150 1 200 1 2 1 4 1 6 1 8 1 10 1 12 1 14 1 16 1 18 1 20 1 22 1 24 1 26 1 28 1 30 1 32 1 34 1 36 1 38 1 40 1 42 1 44 1 46 1 48 1 50 1 52 1 54 1 56 1 58 1 60 1 62 1 64 1 66 1 68 1 70 1 72 1 74 1 76 1 78 1 80 1 82 1 84 1 86 1 88 1 90 1 92 1 94 1 96 1...
result:
ok 355756 lines
Extra Test:
score: 0
Extra Test Passed