Submission #115478

#	Time	Username	Problem	Language	Result	Execution time	Memory
115478		parkj2180	허수아비 (JOI14_scarecrows)	C++14	0 / 100	126 ms	45176 KiB

scarecrows

#include<cstdio>
#include<iostream>
#include<vector>
#include<stack>
#include<algorithm>
using namespace std;
#define MAX 1000000009
int n, ans, before, chk;
pair<int, int> arr[200200];
pair<int, int> asdfa[200200];
vector< pair<int, int> > dp[500200];
int asdf(int index, int x, int start, int end) {
	if (start == end) return start;
	int mid = (start + end) / 2;
	if (dp[index][mid].first < x&&dp[index][mid + 1].first > x) return mid;
	if (dp[index][mid].first > x) {
		return asdf(index, x, start, mid);
	}
	else {
		return asdf(index, x, mid + 1, end);
	}
}
void f(int index, int start, int end, int left, int right, int x) {
	if (chk == 1) return;
	if (left > end || right < start) return;
	else if (left <= start && right >= end) {
		if (x < dp[index][0].first) return;
		int s = asdf(index, x, 0, dp[index].size() - 1);
		if (before > dp[index][s].first) {
			chk = 1;
			return;
		}
		int r = asdf(index, before, 0, dp[index].size() - 1);
		if (before < dp[index][0].first) {
			r = -1;
		}
		before = dp[index][s].first;
		if (r >= 0) {
			ans += dp[index][s].second - dp[index][r].second;
		}
		else ans += dp[index][s].second;
	}
	else {
		int mid = (start + end) / 2;
		f(index * 2 + 1, mid + 1, end, left, right, x);
		f(index * 2, start, mid, left, right, x);
	}
}

int main() {
	scanf("%d", &n);
	for (int i = 0; i<n; i++) {
		scanf("%d%d", &arr[i].first, &arr[i].second);
		arr[i].first++;
		arr[i].second++;
	}
	sort(arr, arr + n);
	for (int i = 0; i<n; i++) {
		asdfa[i].first = arr[i].second;
		asdfa[i].second = i;
	}
	sort(asdfa, asdfa + n);
	int t = 1, depth;
	for (depth = 1; t<n; depth++) t = t * 2;
	for (int i = 0; i<n; i++) {
		dp[i + t].push_back(make_pair(asdfa[i].second+1, 1));
	}
	for (int i = n; i<t; i++) {
		dp[i + t].push_back(make_pair(MAX+i, 1));
	}
	for (int i = t - 1; i >= 1; i--) {
		stack < pair<int, int> > st;
		int cnt = 0;
		for (int j = 0; j<dp[2 * i].size(); j++) {
			st.push(dp[2 * i][dp[2 * i].size()-j-1]);
		}
		int j = 1;
		while (1) {
			if (j == dp[2 * i + 1].size()+1) {
				while (st.empty() != 1) {
					pair<int, int> temp = st.top();
					temp.second += cnt;
					dp[i].push_back(temp);
					st.pop();
				}
				break;
			}
			else if (st.empty() == 1) {
				while (j != dp[2*i+1].size()+1) {
					pair<int, int> temp = dp[2 * i + 1][j-1];
					dp[i].push_back(temp);
					j++;
				}
				break;
			}
			else if (st.top().first<dp[2 * i + 1][j-1].first) {
				pair<int, int> temp = st.top();
				temp.second += cnt;
				dp[i].push_back(temp);
				st.pop();
			}
			else if (st.top().first>dp[2 * i + 1][j-1].first) {
				dp[i].push_back(dp[2 * i + 1][j - 1]);
				j++;
				cnt++;
			}
		}
	}
	for (int i = 0; i < n; i++) {
		before = 0;
		chk = 0;
		int x = dp[i+t][0].first;
		int y = i+1;
		f(1, 1, t, 1, y-1, x);
	}
	printf("%d", ans);
	return 0;
}

Compilation message (stderr)

scarecrows.cpp: In function 'int main()':
scarecrows.cpp:74:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j<dp[2 * i].size(); j++) {
                   ~^~~~~~~~~~~~~~~~~
scarecrows.cpp:79:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (j == dp[2 * i + 1].size()+1) {
        ~~^~~~~~~~~~~~~~~~~~~~~~~~~
scarecrows.cpp:89:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (j != dp[2*i+1].size()+1) {
            ~~^~~~~~~~~~~~~~~~~~~~~
scarecrows.cpp:51:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
scarecrows.cpp:53:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &arr[i].first, &arr[i].second);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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