oj.uz

Submission #95344

# Submission time Handle Problem Language Result Execution time Memory
95344 2019-01-30T13:14:46 Z Retro3014 None (JOI14_ho_t5) C++17
20 / 100
 204 ms 19456 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 16 ms 2580 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 3 ms 632 KB Output is correct
6 Correct 204 ms 18548 KB Output is correct
7 Correct 11 ms 2608 KB Output is correct
8 Correct 95 ms 17748 KB Output is correct
9 Correct 129 ms 17756 KB Output is correct
10 Correct 134 ms 19456 KB Output is correct

Subtask #5
0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -