oj.uz

Submission #13042

# Submission time Handle Problem Language Result Execution time Memory
13042 2015-01-27T04:44:11 Z gs14004 허수아비 (JOI14_scarecrows) C++14
5 / 100
 4000 ms 7520 KB 
#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());
    }
    long long r = f(0,n-1);
    printf("%lld",r);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3932 KB Output is correct
2 Correct 0 ms 3932 KB Output is correct
3 Correct 0 ms 3932 KB Output is correct
4 Correct 0 ms 3932 KB Output is correct
5 Correct 1 ms 3932 KB Output is correct
6 Correct 1 ms 3932 KB Output is correct
7 Correct 1 ms 3932 KB Output is correct
8 Correct 1 ms 3932 KB Output is correct
9 Correct 0 ms 3932 KB Output is correct
10 Correct 1 ms 3932 KB Output is correct

Subtask #2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 3928 KB open (syscall #2) was called by the program (disallowed syscall)
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4000 ms 7520 KB Program timed out
2 Halted 0 ms 0 KB -