Submission #99801

#	Time	Username	Problem	Language	Result	Execution time	Memory
99801		rdd6584	허수아비 (JOI14_scarecrows)	C++14	100 / 100	248 ms	5764 KiB

scarecrows

#include <cstdio>
#include <memory.h>
#include <cstring>
#include <vector>
#include <deque>
#include <cstdlib>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cassert>
#include <functional>
#include <iostream>
#include <set>
#include <list>
#include <map>
#include <time.h>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
using namespace std;

typedef long long ll;
typedef unsigned long long llu;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<int, ll> pil;
typedef pair<string, int> psi;
const ll MOD = 1e9 + 7;
const long double PI = 3.141592653589793238462643383279502884197;

priority_queue<int, vector<int>, greater<int> > pq;
vector<int> v;

pii vec[200000];
pii ori[200000];
pii temp[200000];
ll ans = 0;

void go(int le, int ri) {
	int mid = (le + ri) / 2;
	if (le < ri) { go(le, mid); go(mid + 1, ri); }

	int pt, l = le;
	vector<pii> a, b;
	for (int i = mid + 1; i <= ri; i++) {
		while (!b.empty() && b.back().second > vec[i].second) b.pop_back();
		if (b.empty()) pt = -1;
		else pt = b.back().first;
		b.push_back(vec[i]);

		while (l <= mid && vec[l].first < vec[i].first) {
			while (!a.empty() && a.back().second < vec[l].second) a.pop_back();
			a.push_back(vec[l++]);
		}

		int t = upper_bound(all(a), pii(pt, -1)) - a.begin();
		ans += sz(a) - t;
	}

	/*
	for (int i = le; i <= ri; i++)
		printf("%d : %d %d\n", i + 1, vec[i].second, vec[i].first);
	printf("//%d %d : %lld//\n\n", le + 1, ri + 1, ans);
	*/

	merge(vec + le, vec + mid + 1, vec + mid + 1, vec + ri + 1, temp);
	memcpy(vec + le, temp, sizeof(pii) * (ri - le + 1));
}

int main() {
	int n;
	scanf("%d", &n);

	for (int i = 0; i < n; i++) {
		scanf("%d %d", &vec[i].first, &vec[i].second);
		swap(vec[i].first, vec[i].second);
	}
	sort(vec, vec + n, [](pii v1, pii v2) { return v1.second < v2.second; });
	go(0, n - 1);

	printf("%lld", ans);
}

Compilation message (stderr)

scarecrows.cpp: In function 'int main()':
scarecrows.cpp:76:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
scarecrows.cpp:79:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &vec[i].first, &vec[i].second);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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