QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#297018#7105. Pixel ArtValenciaTravisAC ✓361ms31356kbC++204.2kb2024-01-03 21:21:382024-01-03 21:21:39

Judging History

你现在查看的是最新测评结果

  • [2024-01-03 21:21:39]
  • 评测
  • 测评结果:AC
  • 用时:361ms
  • 内存:31356kb
  • [2024-01-03 21:21:38]
  • 提交

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