Submission #115895

#	Time	Username	Problem	Language	Result	Execution time	Memory
115895		gs18081	허수아비 (JOI14_scarecrows)	C++11	100 / 100	242 ms	9612 KiB

scarecrows

#include <bits/stdc++.h>
#define MAXN 202020
using namespace std;
typedef pair<int,int> pi;
typedef tuple<int,int,int> ti;
typedef pair<vector<int>,vector<int> > pvi;
typedef long long int ll;
int N;
pi arr[MAXN];
ll ans;
vector<ti> dnc(int s,int e){
    vector<ti> ret;
    if(s==e){
        ret.push_back(ti(arr[s].first,arr[s].second,-1));
        return ret;
    }
    int m = (s+e)>>1;
    vector<ti> A = dnc(s,m);
    vector<ti> B = dnc(m+1,e);
    
    vector<pi> vect;
    int a = 0,b = 0;
    while(a < A.size()&&b < B.size()){
        if(get<1>(A[a]) < get<1>(B[b])){
            while(!vect.empty()&&vect.back().second < get<0>(A[a])) vect.pop_back();
            vect.push_back(pi(get<1>(A[a]),get<0>(A[a])));
            ret.push_back(A[a]);
            a++;
        }
        else{
            int p1 = lower_bound(vect.begin(),vect.end(),pi(get<2>(B[b]),-1)) - vect.begin();
            ans += vect.size() - p1;
            auto ptr = vect.end();
            int temp = get<2>(B[b]);
            if(!vect.empty()){
                ptr--;
                temp = max(get<2>(B[b]),ptr->first);
            }
            B[b] = ti(get<0>(B[b]),get<1>(B[b]),temp);
            ret.push_back(B[b]);
            b++;
        }
    }
    while(a < A.size()){
        while(!vect.empty()&&vect.back().first < get<0>(A[a])) vect.pop_back();
        vect.push_back(pi(get<0>(A[a]),get<1>(A[a])));
        ret.push_back(A[a]);
        a++;
    }
    while(b < B.size()){
        int p1 = lower_bound(vect.begin(),vect.end(),pi(get<2>(B[b]),-1)) - vect.begin();
        ans += vect.size() - p1;
        auto ptr = vect.end();
        int temp = get<2>(B[b]);
        if(!vect.empty()){
            ptr--;
            temp = max(get<2>(B[b]),ptr->first);
        }
        B[b] = ti(get<0>(B[b]),get<1>(B[b]),temp);
        ret.push_back(B[b]);
        b++;
    }
    return ret;
}
int main(){
    scanf("%d",&N);
    for(int i=0;i<N;i++){
        scanf("%d %d",&arr[i].first,&arr[i].second);
    }
    sort(arr,arr+N);
    dnc(0,N-1);
    printf("%lld\n",ans);
    return 0;
}

Compilation message (stderr)

scarecrows.cpp: In function 'std::vector<std::tuple<int, int, int> > dnc(int, int)':
scarecrows.cpp:23:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(a < A.size()&&b < B.size()){
           ~~^~~~~~~~~~
scarecrows.cpp:23:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(a < A.size()&&b < B.size()){
                         ~~^~~~~~~~~~
scarecrows.cpp:44:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(a < A.size()){
           ~~^~~~~~~~~~
scarecrows.cpp:50:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(b < B.size()){
           ~~^~~~~~~~~~
scarecrows.cpp: In function 'int main()':
scarecrows.cpp:66:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&N);
     ~~~~~^~~~~~~~~
scarecrows.cpp:68:14: 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: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 85 / 85