Submission #105705

#TimeUsernameProblemLanguageResultExecution timeMemory
105705Pro_ktmr허수아비 (JOI14_scarecrows)C++14
100 / 100
2554 ms50752 KiB
#include"bits/stdc++.h"
using namespace std;
#define LL long long
#define REP(i, n) for(int (i)=0; (i)<(n); (i)++)
#define PB push_back
#define MP make_pair
#define all(x) x.begin(),x.end()

#define int long long

//RSQ セグメント木
struct SegmentTree{
private:
	int n;
	vector<int> nodes;
	const int DEFAULT = 0;
public:
	void init(int N){ //初期化する O(N)
		nodes.clear();
		n = 1;
		while(n < N) n *= 2;
		n = 2 * n -1;
		for(int i=0; i<n; i++) nodes.push_back(DEFAULT);
	}
	void update(int i, int x){ //値を変更する O(log N)
		i += n / 2;
		nodes[i] = x;
		while(i > 0){
			i = (i-1)/2; //親の取得は(i-1)/2
			nodes[i] = nodes[i*2+1] + nodes[i*2+2]; //子の取得はi*2+1,i*2+2
		}
	}
	int sum(int a, int b, int k=0, int l=0, int r=-1){ //[a,b)の最小値を求める O(log N)
		if(r == -1) r = n/2+1;
		if(r <= a || b <= l) return DEFAULT; //交差する場合
		if(a <= l && r <= b) return nodes[k]; //完全に含む場合
		int valueL = sum(a, b, k*2+1, l, (l+r)/2);
		int valueR = sum(a, b, k*2+2, (l+r)/2, r);
		return valueL + valueR;
	}
};

int N;
pair<int,int> point[200000];
//数学と同じ座標の取り方→xとyの大小関係一致
vector<int> zaatuX,zaatuY;

LL ans = 0;
void DevideConquer(int l, int r){
	if(r-l == 1) return;
	int m = (l+r)/2;

	vector<int> zaatu;
	for(int i=l; i<r; i++) zaatu.PB(point[i].second);
	sort(zaatu.begin(), zaatu.end());

	set<int> st1,st2;
	vector<pair<pair<int,int>,int>> kukan;
	for(int i=m-1; i>=l; i--){
		int y = lower_bound(zaatu.begin(), zaatu.end(), point[i].second) - zaatu.begin();
		auto itr = st1.lower_bound(y);
		if(itr == st1.end()) kukan.PB(MP(MP(y,N),0));
		else kukan.PB(MP(MP(y,*itr),0));
		st1.insert(y);
	}
	for(int i=m; i<r; i++){
		int y = lower_bound(zaatu.begin(), zaatu.end(), point[i].second) - zaatu.begin();
		auto itr = st2.lower_bound(y);
		if(itr == st2.begin()) kukan.PB(MP(MP(0,y),1));
		else{
			itr--;
			kukan.PB(MP(MP(*itr,y),1));
		}
		st2.insert(y);
	}


	sort(kukan.begin(), kukan.end());
	SegmentTree rsq; //右サイドの上端
	rsq.init(r-l);
	for(int i=0; i<kukan.size(); i++){
		if(kukan[i].second == 0){
			ans += rsq.sum(kukan[i].first.first, kukan[i].first.second);
		}
		else{
			rsq.update(kukan[i].first.second, 1);
		}
	}

	DevideConquer(l, m);
	DevideConquer(m, r);
}

signed main(){
	scanf("%d", &N);
	for(int i=0; i<N; i++){
		scanf("%d%d", &point[i].first, &point[i].second);
		zaatuX.PB(point[i].first);
		zaatuY.PB(point[i].second);
	}
	sort(zaatuX.begin(), zaatuX.end());
	sort(zaatuY.begin(), zaatuY.end());
	for(int i=0; i<N; i++){
		point[i].first = lower_bound(zaatuX.begin(), zaatuX.end(), point[i].first) - zaatuX.begin();
		point[i].second = lower_bound(zaatuY.begin(), zaatuY.end(), point[i].second) - zaatuY.begin();
	}
	sort(point, point+N);

	//

	DevideConquer(0, N);
	printf("%lld\n", ans);

	return 0;
}

Compilation message (stderr)

scarecrows.cpp: In function 'void DevideConquer(long long int, long long int)':
scarecrows.cpp:81:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<kukan.size(); i++){
               ~^~~~~~~~~~~~~
scarecrows.cpp: In function 'int main()':
scarecrows.cpp:95:16: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
  scanf("%d", &N);
              ~~^
scarecrows.cpp:97:50: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
   scanf("%d%d", &point[i].first, &point[i].second);
                 ~~~~~~~~~~~~~~~                  ^
scarecrows.cpp:97:50: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'long long int*' [-Wformat=]
scarecrows.cpp:95:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
scarecrows.cpp:97:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &point[i].first, &point[i].second);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...