Submission #95344

#	Time	Username	Problem	Language	Result	Execution time	Memory
95344		Retro3014	절취선 (JOI14_ho_t5)	C++17	20 / 100	204 ms	19456 KiB

2014_ho_t5

#include <iostream>
#include <vector>
#include <stdio.h>
#include <algorithm>
#include <map>

using namespace std;
typedef long long ll;

int W, H, N;
struct LINE{
	LINE (int x, int y1, int y2) : x(x), y1(y1), y2(y2) {}
	int x;
	int y1, y2;
	bool operator <(const LINE &a)const{
		return x<a.x;
	}};
vector<LINE> line;
struct POINT{
	POINT (int x, int y, int z) : x(x), y(y), z(z) {}
	int x, y, z;
	bool operator <(const POINT &a)const{
		if(x==a.x){
			return z<a.z;
		}
		return x<a.x;
	}};
vector<POINT> p;

struct SEG{
	SEG (int l, int r, int sum) : l(l), r(r), sum(sum) {}
	int l, r;
	int sum;
};
vector<SEG> seg1;

ll ans = 1;
//map<pair<int, int>, int> mp;

int sum11(int idx, int s, int e, int x, int y){
	if(idx==-1)	return 0;
	if(x<=s && e<=y)	return seg1[idx].sum;
	if(x>e || y<s)	return 0;
	return sum11(seg1[idx].l, s, (s+e)/2, x, y) + sum11(seg1[idx].r, (s+e)/2+1, e, x, y);
}

void update11(int idx, int s, int e, int x, int y){
	seg1[idx].sum+=y;
	if(s==e)	return;
	if(x<=(s+e)/2){
		if(seg1[idx].l==-1){
			seg1[idx].l = seg1.size(); seg1.push_back({-1, -1, 0});
		}
		update11(seg1[idx].l, s, (s+e)/2, x, y);
	}else{
		if(seg1[idx].r==-1){
			seg1[idx].r = seg1.size(); seg1.push_back({-1, -1, 0});
		}
		update11(seg1[idx].r, (s+e)/2+1, e, x, y);
	}
}

int sum1(int x, int y)	{return sum11(0, 0, H, x, y);}
void update1(int x, int y)	{update11(0, 0, H, x, y);}


int main(){
	scanf("%d%d%d", &W, &H, &N);
	seg1.push_back({-1, -1, 0});
	for(int i=0; i<N; i++){
		int a, b, c, d;
		scanf("%d%d%d%d", &a, &b, &c, &d);
		if(a==c){
			line.push_back({a, b, d});
		}else{
			p.push_back({a, b, 1}); p.push_back({c+1, b, -1});
		}
	}
	//cout<<ans<<endl;
	p.push_back({0, 0, 1}); p.push_back({0, H, 1});
	line.push_back({0, 0, H}); line.push_back({W, 0, H});
	sort(p.begin(), p.end()); sort(line.begin(), line.end());
	int idx = 0;
	ans-=(ll)(N+4);
	for(int i=0; i<line.size(); i++){
		while(idx<p.size() && p[idx].x<=line[i].x){
			POINT now = p[idx]; idx++;
			//cout<<'*'<<now.x<<' '<<now.y<<' '<<now.z<<endl;
			if(now.z==1){
				update1(now.y, 1);
			}else{
				update1(now.y, -1);
			}
		}
		int tmp = sum1(line[i].y1, line[i].y2);
		ans+=(ll)tmp;
	}
	printf("%lld", ans);
}

Compilation message (stderr)

2014_ho_t5.cpp: In function 'int main()':
2014_ho_t5.cpp:85:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<line.size(); i++){
               ~^~~~~~~~~~~~
2014_ho_t5.cpp:86:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(idx<p.size() && p[idx].x<=line[i].x){
         ~~~^~~~~~~~~
2014_ho_t5.cpp:68:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &W, &H, &N);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
2014_ho_t5.cpp:72:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d%d", &a, &b, &c, &d);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 5
• Subtask 3: 0 / 20
• Subtask 4: 20 / 20
• Subtask 5: 0 / 50