Submission #202016

#	Time	Username	Problem	Language	Result	Execution time	Memory
202016		manh9203	허수아비 (JOI14_scarecrows)	C++17	100 / 100	1810 ms	33732 KiB

scarecrows

#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
const int N = 2e5 + 5;
typedef pair<int, int> point;
long long n, m, LBoard[N], RBoard[N], fen[N], ans;
point p[N];
vector<int> dmx, s, que[N], upd[N];
map<int, int> idx;
//BIT
void update(int id, int val){
	for(int i = id; i <= m; i += (i&-i)){
		fen[i] += val;
	}
}
int get(int id){
	int sum = 0;
	for(int i = id; i >= 1; i -= (i&-i)){
		sum += fen[i];
	}
	return sum;
}
//DnC
bool cmp1(point a, point b){
	return a.y < b.y;
}
bool cmp2(point a, point b){
	return a.x < b.x;
}
void solve(int l, int r){
	if(l == r) return;
	int mid = (l + r) >> 1;
	dmx.clear(); idx.clear();
	for(int i = l; i <= r; i++){
		dmx.push_back(p[i].x);
	}
	sort(dmx.begin(), dmx.end());
	auto it = unique(dmx.begin(), dmx.end());
	dmx.resize(distance(dmx.begin(), it));
	m = dmx.size();
	for(int i = 0; i < m; i++){
		idx[dmx[i]] = i + 1;
		que[i + 1].clear(); upd[i + 1].clear();
		fen[i + 1] = 0;
	}
	sort(p + l, p + mid + 1, cmp2);
	sort(p + mid + 1, p + r + 1, cmp2);
	s.clear(); s.push_back(0);
	idx[-1] = m + 1;
	for(int i = mid; i >= l; i--){
		while(s.size() > 1 && p[i].y > p[s.back()].y){
			s.pop_back();
		}
		upd[idx[p[s.back()].x]].push_back(idx[p[i].x]);
		s.push_back(i);
		update(idx[p[i].x], 1);
	}
	s.clear(); s.push_back(0);
	idx[-1] = 0;
	for(int i = mid + 1; i <= r; i++){
		while(s.size() > 1 && p[i].y < p[s.back()].y){
			s.pop_back();
		}
		que[idx[p[i].x]].push_back(idx[p[s.back()].x]);
		s.push_back(i);
	}
	for(int i = 1; i <= m; i++){
		for(int j: upd[i]){
			update(j, -1);
		}
		for(int j: que[i]){
			ans += get(i) - get(j);
		}
	}
	sort(p + l, p + r + 1, cmp1);
	solve(l, mid);
	solve(mid + 1, r);
}
//main
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n;
	for(int i = 1; i <= n; i++){
		cin >> p[i].x >> p[i].y;
	}
	p[0] = {-1, -1};
	sort(p + 1, p + 1 + n, cmp1);
	solve(1, n);
	cout << ans;
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 85 / 85