Submission

Score: 100

User: ki

Problemset: fireball

Language: cpp

Time: 0.004 second

Submitted On: 2026-03-20 11:53:06

#include<iostream>
#include<vector>
#include<utility>
#include<numeric>
#include<functional>
using namespace std;
int n,m,q,x,y;
int main(){
	cin>>n>>m>>q;
	vector<vector<int>>a(n,vector<int>(m));
	vector<int>p(n*m),sz(n*m);
	vector<bool>f(n*m);
	iota(p.begin(),p.end(),0);
	auto get=[&](int x,int y){
		return x*m+y;
	};
	function<int(int)>fset=[&](int x){
		return (p[x]==x?x:p[x]=fset(p[x]));
	};
	auto mg=[&](int x,int y){
		if((x=fset(x))==(y=fset(y)))return;
		sz[x]+=sz[y];
		p[y]=x;
	};
	int ans=0;
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			cin>>a[i][j];
			if(a[i][j])sz[get(i,j)]=1;
			ans+=a[i][j];
		}
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			if(a[i][j]){
				for(auto e:vector<pair<int,int>>{{-1,0},{0,-1},{1,0},{0,1}}){
					int nx=i+e.first,ny=j+e.second;
					if(nx>=0&&nx<n&&ny>=0&&ny<m&&a[nx][ny]){
						mg(get(i,j),get(nx,ny));
					}
				}
			}
		}
	}
	while(q--){
		cin>>x>>y;
		x--;y--;
		int z=get(x,y);
		if(f[fset(z)])cout<<ans<<'\n';
		else{
			ans-=sz[fset(z)];
			f[fset(z)]=1;
			cout<<ans<<'\n';
		}
	}
}