#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
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);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
12160 KB |
Output is correct |
| 2 |
Incorrect |
13 ms |
12160 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
13440 KB |
Output is correct |
| 2 |
Incorrect |
19 ms |
13440 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
126 ms |
45176 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
