Submission #527098

#	Time	Username	Problem	Language	Result	Execution time	Memory
527098		colazcy	Topovi (COCI15_topovi)	C++11	120 / 120	1545 ms	33624 KiB

topovi

#include <cstdio>
#include <map>
#include <utility>
#include <cassert>
#define let const auto
#define rep(name,beg,end) for(auto lim_##name = end,name = beg;name <= lim_##name;name++)
#define per(name,beg,end) for(auto lim_##name = end,name = beg;name >= lim_##name;name--)
#define repn(lim) for(auto REPN_LIM = lim,REPN = 1;REPN <= REPN_LIM;REPN++)
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define trace() debug("Line : %d, Function : %s\n",__LINE__,__FUNCTION__)
using ll = long long;
constexpr int maxn = 1e5 + 100;

std::map<std::pair<int,int>,int> id;
std::map<int,int> val_x,val_y;
std::map<int,int> cnt_x,cnt_y;

ll ans;
void modify(const int x,const int y,const int v){
	ans -= 1ll * cnt_x[val_x[x]] * cnt_y[val_x[x]];
	cnt_x[val_x[x]]--;
	ans += 1ll * cnt_x[val_x[x]] * cnt_y[val_x[x]];
	
	val_x[x] ^= v;
	ans -= 1ll * cnt_x[val_x[x]] * cnt_y[val_x[x]];
	cnt_x[val_x[x]]++;
	ans += 1ll * cnt_x[val_x[x]] * cnt_y[val_x[x]];

	ans -= 1ll * cnt_y[val_y[y]] * cnt_x[val_y[y]];
	cnt_y[val_y[y]]--;
	ans += 1ll * cnt_y[val_y[y]] * cnt_x[val_y[y]];
	
	val_y[y] ^= v;
	ans -= 1ll * cnt_y[val_y[y]] * cnt_x[val_y[y]];
	cnt_y[val_y[y]]++;
	ans += 1ll * cnt_y[val_y[y]] * cnt_x[val_y[y]];
}
int n,k,q,w[maxn];

int main(){
	// std::freopen("topovi.in","r",stdin);
	// std::freopen("topovi.out","w",stdout);
	std::scanf("%d %d %d",&n,&k,&q);
	cnt_x[0] = cnt_y[0] = n;
	ans = 1ll * n * n;
	rep(i,1,k){
		int x,y; std::scanf("%d %d %d",&x,&y,w + i);
		modify(x,y,w[i]);
		id[std::make_pair(x,y)] = i;
	}

	repn(q){
		int fx,fy,tx,ty; std::scanf("%d %d %d %d",&fx,&fy,&tx,&ty);
		let it = id.find(std::make_pair(fx,fy));
		let t = it->second,v = w[t];
		id.erase(it);
		id[std::make_pair(tx,ty)] = t;

		modify(fx,fy,v);
		modify(tx,ty,v);
		std::printf("%lld\n",1ll * n * n - ans);
	}
	std::fclose(stdin);
	std::fclose(stdout);
	return 0;
}

Compilation message (stderr)

topovi.cpp: In function 'int main()':
topovi.cpp:43:12: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |  std::scanf("%d %d %d",&n,&k,&q);
      |  ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
topovi.cpp:47:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |   int x,y; std::scanf("%d %d %d",&x,&y,w + i);
      |            ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
topovi.cpp:53:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |   int fx,fy,tx,ty; std::scanf("%d %d %d %d",&fx,&fy,&tx,&ty);
      |                    ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 120 / 120