Submission #51540

#	Time	Username	Problem	Language	Result	Execution time	Memory
51540		moonrabbit2	허수아비 (JOI14_scarecrows)	C++17	100 / 100	2832 ms	98140 KiB

scarecrows

#include <bits/stdc++.h>
#define N 200005
#define INF 1000000005
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
struct fenwick
{
    vector<int>tree;
    fenwick(int sz){tree.resize(sz+5);}
    void add(int k){
        for(;k<=tree.size();k+=k&-k)
            tree[k]++;
    }
    int sum(int k){
        int res=0;
        for(;k;k-=k&-k)
            res+=tree[k];
        return res;
    }
};
ll ans;
int n;P a[N];
void dnc(int s,int e)
{
    if(e==s)
        return;
    int m=(s+e)/2;
    dnc(s,m);
    dnc(m+1,e);
    set<int>st1,st2;
    vector<P> l,r;
    st1.insert(INF);
    for(int i=m;i>=s;i--){
        int p=*st1.lower_bound(a[i].y);
        l.push_back(P(a[i].y,p-1));
        st1.insert(a[i].y);
    }
    st2.insert(INF);
    for(int i=m+1;i<=e;i++){
        int p=-*st2.lower_bound(-a[i].y);
        r.push_back(P(p+1,a[i].y));
        st2.insert(-a[i].y);
    }
    sort(l.begin(),l.end());
    sort(r.begin(),r.end());
    map<int,int> mp;
    for(int i=0;i<l.size();i++){
        mp.insert(P(l[i].x,0));
        mp.insert(P(l[i].y,0));
    }
    for(int i=0;i<r.size();i++){
        mp.insert(P(r[i].x,0));
        mp.insert(P(r[i].y,0));
    }
    int k=1,c=0;
    for(auto it=mp.begin();it!=mp.end();it++)
        it->y=k++;
    fenwick tree(k);
    for(int i=0;i<l.size();i++){
        while(c<r.size()&&r[c].x<=l[i].x)
            tree.add(mp[r[c++].y]);
        ans+=tree.sum(mp[l[i].y])-tree.sum(mp[l[i].x]-1);
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i].x>>a[i].y;
    sort(a+1,a+1+n);
    dnc(1,n);
    cout<<ans;
    return 0;
}

Compilation message (stderr)

scarecrows.cpp: In member function 'void fenwick::add(int)':
scarecrows.cpp:14:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(;k<=tree.size();k+=k&-k)
              ~^~~~~~~~~~~~~
scarecrows.cpp: In function 'void dnc(int, int)':
scarecrows.cpp:50:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<l.size();i++){
                 ~^~~~~~~~~
scarecrows.cpp:54:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<r.size();i++){
                 ~^~~~~~~~~
scarecrows.cpp:62:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<l.size();i++){
                 ~^~~~~~~~~
scarecrows.cpp:63:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(c<r.size()&&r[c].x<=l[i].x)
               ~^~~~~~~~~

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