Submission #742579

#	Time	Username	Problem	Language	Result	Execution time	Memory
742579		flappybird	허수아비 (JOI14_scarecrows)	C++17	100 / 100	442 ms	11612 KiB

scarecrows

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define MAX 201010
#define MAXS 20
#define INF 1000000000000000001
#define bb ' '
#define ln '\n'
#define Ln '\n'
int Y[MAX];
ll ans;
void solve(int l, int r) {
	if (l == r) return;
	int m = l + r >> 1;
	int i;
	vector<pii> lv, rv;
	for (i = l; i <= m; i++) lv.emplace_back(i, Y[i]);
	sort(lv.begin(), lv.end(), [&](pii a, pii b) {return a.second < b.second; });
	for (i = m + 1; i <= r; i++) rv.emplace_back(i, Y[i]);
	sort(rv.begin(), rv.end(), [&](pii a, pii b) {return a.second < b.second; });
	vector<pii> stl, str; // y, x
	int ptr = 0;
	for (auto& [x, y] : rv) {
		while (ptr < lv.size() && lv[ptr].second < y) {
			while (stl.size() && stl.back().second < lv[ptr].first) stl.pop_back();
			stl.emplace_back(lv[ptr].second, lv[ptr].first);
			ptr++;
		}
		while (str.size() && str.back().second > x) str.pop_back();
		int py = -10;
		if (str.size()) py = str.back().first;
		str.emplace_back(y, x);
		int ind = upper_bound(stl.begin(), stl.end(), pii(py, 0)) - stl.begin();
		ans += (ll)(stl.size()) - ind;
	}
	solve(l, m);
	solve(m + 1, r);
}
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int N;
	cin >> N;
	vector<pii> vpi;
	int i, a, b;
	for (i = 1; i <= N; i++) cin >> a >> b, vpi.emplace_back(a, b);
	sort(vpi.begin(), vpi.end());
	i = 0;
	for (auto& [_, y] : vpi) Y[++i] = y;
	solve(1, N);
	cout << ans << ln;
}

Compilation message (stderr)

scarecrows.cpp: In function 'void solve(int, int)':
scarecrows.cpp:20:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   20 |  int m = l + r >> 1;
      |          ~~^~~
scarecrows.cpp:30:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |   while (ptr < lv.size() && lv[ptr].second < y) {
      |          ~~~~^~~~~~~~~~~

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