QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#176234#7105. Pixel Artpengpeng_fudanWA 2ms11140kbC++172.2kb2023-09-11 12:58:022023-09-11 12:58:03

Judging History

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

  • [2023-09-11 12:58:03]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:11140kb
  • [2023-09-11 12:58:02]
  • 提交

answer

#include <bits/stdc++.h>
#define int long long
using namespace std;
using ull=unsigned long long;
using ll=long long;
int n,m,k;
vector<pair<int,int>> ve[100010];
vector<int> hi[100010];
struct seg{
	#define ls(x) tr[x].l
	#define rs(x) tr[x].r
	#define fu(x)	tr[x].fu
	struct node{
		int l,r;bool fu;
	}tr[100010*2];
	int tot=1;
	void clear(int x){ls(x)=rs(x)=fu(x)=0;}
	seg(){tot=1,clear(1);}
	void clear(){tot=1,clear(1);}
	void upd(int x,int l,int r,int L,int R){
		if(L<=l&&r<=R){fu(x)=1;return ;}
		int mid=(l+r)>>1;
		if(mid>=L){
			if(!ls(x)){ls(x)=++tot;clear(tot);}
			upd(ls(x),l,mid,L,R);
		}
		if(mid<R){
			if(!rs(x)){rs(x)=++tot;clear(tot);}
			upd(rs(x),mid+1,r,L,R);
		}
	}
	bool query(int x,int l,int r,int L,int R){
		if(fu(x))	return true;
		int mid=(l+r)>>1;
		bool ans=0;
		if(mid>=L&&ls(x))	ans|=query(ls(x),l,mid,L,R);
		if(mid<R&&rs(x))	ans|=query(rs(x),mid+1,r,L,R);
		return ans;
	}
};
seg sg[2];
bool flag[100010];
void solve() {
	cin>>n>>m>>k;
	fill(flag,flag+m+2,0);
	sg[0].clear(),sg[1].clear();
	for(int i=1;i<=n;i++){
		ve[i].clear();
		hi[i].clear();
	}
	int a,b,c,d;
	for(int i=1;i<=k;i++){
		cin>>a>>b>>c>>d;
		if(a==c) ve[a].push_back({b,d});
		else{
			hi[a].push_back(b);
			hi[c+1].push_back(-b);
		}
	}
	for(int i=1;i<=n;i++)	sort(hi[i].begin(),hi[i].end(),[&](int a,int b){if(fabs(a)==fabs(b))	return a<b;else return fabs(a)<fabs(b);});
	int black_num=0;
	int ltk=0;
	int len_num=0;
	int t=0;
	for(int i=1;i<=n;i++){
		t=t^1;
		sg[t].clear();
		for(auto j:ve[i])	black_num+=j.second-j.first+1;
		int sz=hi[i].size();
		for(int j=0;j<sz;j++){
			int t=hi[i][j];
			if(t<0){
				flag[j]=0;
				len_num--;
			}
			else{
				if(sg[t^1].query(1,1,m,t,t)||flag[t-1]||(j!=0&&hi[i][j-1]==-hi[i][j]));
				else ltk++;
				flag[j]=1;
				len_num++;
			}		
		}
		for(auto j:ve[i]){
			if(!sg[t^1].query(1,1,m,j.first,j.second)&&!flag[j.first-1]&&!flag[j.second+1])	ltk++;
			sg[t].upd(1,1,m,j.first,j.second);
		}
		black_num+=len_num;
		cout<<black_num<<' '<<ltk<<'\n';
	}
}

signed main() {
	ios::sync_with_stdio(0),cin.tie(0);
	int _ = 1; 
	cin >> _;
	while(_--) solve();
	return 0;
}

详细

Test #1:

score: 0
Wrong Answer
time: 2ms
memory: 11140kb

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 0
4 0
6 1

result:

wrong answer 5th lines differ - expected: '3 1', found: '3 0'