제출 #299049

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
299049		TMJN	Rectangles (IOI19_rect)	C++17	0 / 100	5080 ms	410636 KiB

rect

#include <bits/stdc++.h>
#include "rect.h"
using namespace std;

int tree[1<<13][1<<13];
bool b[2500][2500];
set<int>sth[2500],stw[2500];
vector<pair<int,pair<int,int>>>p;
int H,W,res;

int calc(int xl,int xr,int yl,int yr){
	int a=0;
	xl+=(1<<12);
	xr+=(1<<12);
	yl+=(1<<12);
	yr+=(1<<12);
	int YL=yl,YR=yr;
	while(xl<xr){
		if(xl&1){
			yl=YL;
			yr=YR;
			while(yl<yr){
				if(yl&1){
					a+=tree[xl][yl];
				}
				if(~yr&1){
					a+=tree[xl][yr];
				}
				yl=(yl+1)/2;
				yr=(yr-1)/2;
			}
			if(yl==yr){
				a+=tree[xl][yl];
			}
		}
		if(~xr&1){
			yl=YL;
			yr=YR;
			while(yl<yr){
				if(yl&1){
					a+=tree[xr][yl];
				}
				if(~yr&1){
					a+=tree[xr][yr];
				}
				yl=(yl+1)/2;
				yr=(yr-1)/2;
			}
			if(yl==yr){
				a+=tree[xr][yl];
			}
		}
		xl=(xl+1)/2;
		xr=(xr-1)/2;
	}
	if(xl==xr){
		yl=YL;
		yr=YR;
		while(yl<yr){
			if(yl&1){
				a+=tree[xl][yl];
			}
			if(~yr&1){
				a+=tree[xl][yr];
			}
			yl=(yl+1)/2;
			yr=(yr-1)/2;
		}
		if(yl==yr){
			a+=tree[xl][yl];
		}
	}
	return a;
}

void add(int x,int y){
	b[x][y]=true;
	x+=(1<<12);
	y+=(1<<12);
	int Y=y;
	while(x){
		y=Y;
		while(y){
//			cout<<"!"<<x<<' '<<y<<endl;
			tree[x][y]++;
			y/=2;
		}
		x/=2;
	}
}

long long count_rectangles(vector<vector<int>>a){
	H=a.size();
	W=a[0].size();
	for(int i=0;i<H;i++){
		for(int j=0;j<W;j++){
			p.push_back({a[i][j],{i,j}});
		}
	}
	p.push_back({0xE869120,{-1,-1}});
	sort(p.begin(),p.end());
	for(int i=0;i<H;i++){
		for(int j=-1;j<=W;j++){
			sth[i].insert(j);
		}
	}
	for(int i=0;i<W;i++){
		for(int j=-1;j<=H;j++){
			stw[i].insert(j);
		}
	}
	for(int i=0;i<p.size()-1;i++){
		if(i&&p[i-1].first==p[i].first)continue;
		for(int j=i;p[i].first==p[j].first;j++){
			add(p[j].second.first,p[j].second.second);
			sth[p[j].second.first].erase(p[j].second.second);
			stw[p[j].second.second].erase(p[j].second.first);
		}
		vector<pair<pair<int,int>,pair<int,int>>>pp;
		for(int j=i;p[i].first==p[j].first;j++){
			int lx,rx,ly,ry;
			auto it=sth[p[j].second.first].lower_bound(p[j].second.second);
			ry=*it;
			it--;
			ly=*it;
			auto it2=stw[p[j].second.second].lower_bound(p[j].second.first);
			rx=*it2;
			it2--;
			lx=*it2;
			lx++;
			rx--;
			ly++;
			ry--;
			if(lx<=0||ly<=0||H-1<=rx||W-1<=ry)continue;
			if(calc(lx-1,rx+1,ly-1,ry+1)==calc(lx,rx,ly,ry)+b[lx-1][ly-1]+b[lx-1][ry+1]+b[rx+1][ly-1]+b[rx+1][ry+1]){
				pp.push_back({{lx,rx},{ly,ry}});
//				cout<<"!!!"<<lx<<' '<<rx<<' '<<' '<<ly<<' '<<ry<<endl;
			}
//			cout<<p[i].first<<' '<<j<<"   "<<lx<<' '<<rx<<"  "<<ly<<' '<<ry<<' '<<calc(lx,rx,ly,ry)<<' '<<calc(lx-1,rx+1,ly-1,ry+1)<<' '<<b[lx-1][ly-1]+b[lx-1][ry+1]+b[rx+1][ly-1]+b[rx+1][ry+1]<<endl;
		}
		sort(pp.begin(),pp.end());
		pp.erase(unique(pp.begin(),pp.end()),pp.end());
		res+=pp.size();
	}
	return res;
}

컴파일 시 표준 에러 (stderr) 메시지

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:112:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |  for(int i=0;i<p.size()-1;i++){
      |              ~^~~~~~~~~~~

• Subtask 1: 0 / 8
• Subtask 2: 0 / 7
• Subtask 3: 0 / 12
• Subtask 4: 0 / 22
• Subtask 5: 0 / 10
• Subtask 6: 0 / 13
• Subtask 7: 0 / 28