| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 13041 | gs14004 | 허수아비 (JOI14_scarecrows) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <cstdio>
#include <stack>
#include <algorithm>
#include <utility>
#include <set>
#include <vector>
using namespace std;
typedef pair<int,int> pi;
int a[200005],n;
long long f(int s, int e){
long long res = 0;
if(e - s < 400){
for (int i=s; i<=e; i++) {
int upper=1e9;
for (int j=i+1; j<=e; j++) {
if(a[i] < a[j] && a[j] < upper){
upper = a[j];
res++;
}
}
}
return res;
}
int m = (s+e)/2;
res = f(s,m) + f(m+1,e);
vector<int> l;
vector<pi> r;
l.push_back(a[m]);
for (int i=m-1; i>=s; i--) {
if(l.back() < a[i]) l.push_back(a[i]);
}
for (int i=m+1; i<=e; i++) {
r.push_back(pi(a[i],i));
}
sort(r.begin(),r.end());
int p = (int)r.size() - 1;
stack<int> st;
for (int i=(int)l.size() - 1; i>=0; i--) {
while (r[p].first > l[i]) {
while (!st.empty() || st.top() > r[p].second) {
st.pop();
}
st.push(r[p].second);
}
res += (int)st.size();
}
return res;
}
pi p[200005];
vector<int> py;
int main(){
scanf("%d",&n);
py.push_back(-1e9);
for (int i=0; i<n; i++) {
scanf("%d %d",&p[i].first,&p[i].second);
py.push_back(p[i].second);
}
sort(p,p+n);
sort(py.begin(),py.end());
for (int i=0; i<n; i++) {
a[i] = (int)(lower_bound(py.begin(),py.end(),p[i].second) - py.begin());
}
for(lim = 1; lim <= n+1; lim <<= 1);
long long r = f(0,n-1);
printf("%lld",r);
}