oj.uz

Submission #51540

# Submission time Handle Problem Language Result Execution time Memory
51540 2018-06-18T08:27:08 Z moonrabbit2 허수아비 (JOI14_scarecrows) C++17
100 / 100
 2832 ms 98140 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 376 KB Output is correct
2 Correct 4 ms 488 KB Output is correct
3 Correct 4 ms 488 KB Output is correct
4 Correct 3 ms 564 KB Output is correct
5 Correct 4 ms 684 KB Output is correct
6 Correct 5 ms 684 KB Output is correct
7 Correct 3 ms 728 KB Output is correct
8 Correct 4 ms 804 KB Output is correct
9 Correct 4 ms 804 KB Output is correct
10 Correct 3 ms 908 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 1276 KB Output is correct
2 Correct 40 ms 1476 KB Output is correct
3 Correct 50 ms 1548 KB Output is correct
4 Correct 35 ms 1824 KB Output is correct
5 Correct 44 ms 1824 KB Output is correct
6 Correct 47 ms 1960 KB Output is correct
7 Correct 44 ms 2060 KB Output is correct
8 Correct 27 ms 2060 KB Output is correct
9 Correct 37 ms 2084 KB Output is correct
10 Correct 38 ms 2300 KB Output is correct
11 Correct 44 ms 2428 KB Output is correct
12 Correct 32 ms 2428 KB Output is correct

Subtask #3
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1876 ms 24564 KB Output is correct
2 Correct 2731 ms 29740 KB Output is correct
3 Correct 2261 ms 33596 KB Output is correct
4 Correct 2208 ms 42440 KB Output is correct
5 Correct 2573 ms 43964 KB Output is correct
6 Correct 2476 ms 45856 KB Output is correct
7 Correct 2643 ms 49160 KB Output is correct
8 Correct 2832 ms 53216 KB Output is correct
9 Correct 1915 ms 53216 KB Output is correct
10 Correct 2085 ms 58064 KB Output is correct
11 Correct 2321 ms 63940 KB Output is correct
12 Correct 2608 ms 68248 KB Output is correct
13 Correct 2679 ms 72172 KB Output is correct
14 Correct 1831 ms 72172 KB Output is correct
15 Correct 2168 ms 79524 KB Output is correct
16 Correct 2621 ms 83720 KB Output is correct
17 Correct 1475 ms 83720 KB Output is correct
18 Correct 2581 ms 90240 KB Output is correct
19 Correct 2604 ms 94200 KB Output is correct
20 Correct 2739 ms 98140 KB Output is correct