Submission #758863

#	Time	Username	Problem	Language	Result	Execution time	Memory
758863		Ronin13	허수아비 (JOI14_scarecrows)	C++14	100 / 100	2152 ms	35248 KiB

scarecrows

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;

const int nmax = 200005;

vector <pii> points;

vector <int> t(4 * nmax);

void upd(int v, int l, int r, int pos, int val){
    if(l > pos || r < pos){
        return;
    }
    if(l == r){
        t[v] = val;
        return;
    }
    int m = (l + r) / 2;
    upd(2 * v, l, m, pos,  val);
    upd(2 * v + 1, m + 1, r, pos,  val);
    t[v] = t[2 * v] + t[2 * v + 1];
}

int get(int v, int l, int r, int st, int fin){
    if(l > fin || r < st){
        return 0;
    }
    if(l >= st && r <= fin)
        return t[v];
    int m = (l + r) / 2;
    return get(2 * v, l,m, st, fin) + get(2 * v + 1, m + 1, r, st, fin);
}


int cur[nmax];

ll ans = 0;
void divi(int l, int r){
    if(l >= r)
        return;
    int m = (l + r) / 2;
    set <pii> st;
    vector <pii> vec;
    vector <pair<pii, int> > vv;
    for(int i = l; i <= m; i++){
        vv.pb({{points[i].s, points[i].f}, i});
    }
    sort(vv.begin(), vv.end());
    reverse(vv.begin(), vv.end());
    stack <int> s;
    s.push(vv[0].s);
    cur[vv[0].s] = 200001;
    for(int i = 1; i < vv.size(); i++){
        while(!s.empty()){
            int v = s.top();
            if(points[v].f > points[vv[i].s].f){
                break;
            }
            else s.pop();
        }
        if(s.empty()){
            cur[vv[i].s] = 200001;
        }
        else cur[vv[i].s] = points[s.top()].s;
        s.push(vv[i].s);
    }
    for(int i= l; i <= r; i++){
        vec.epb(points[i].s, i);
    }

    sort(vec.begin(), vec.end());
    reverse(vec.begin(), vec.end());
    for(int i= 0; i < vec.size(); i++){
        if(vec[i].s <= m){
            int xx = cur[vec[i].s];
            int o  = vec[i].s;
            ans += (ll)get(1, 1, 200001, points[o].s, xx);
            //upd(1, 1, 200000, points[i].s, 1);
        }
        else{
            int o = vec[i].s;
            auto it = st.upper_bound({points[o].f, -1});
            vector <pii> er;
            while(it != st.end()){
                er.pb(*it);
                it++;
            }
            for(auto to : er){
                int x=  to.s;
                upd(1, 1, 200001, points[x].s, 0);
                st.erase(to);
            }
            st.insert({points[o].f, o});
            upd(1, 1, 200001, points[o].s, 1);
        }
    }
    st.clear();
    for(int i = l; i <= r; ++i){
        cur[points[i].s] = 0;
        upd(1, 1, 200001, points[i].s, 0);
    }

    //cout << ans << "\n";
    divi(l, m);
    divi(m + 1, r);
}


int main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    int n; cin >> n;
    int x[n + 1];
    int y[n + 1];
    map <int, int> mpx, mpy;
    vector <int> xx, yy;
    for(int i= 1; i<= n ;++i){
        cin >> x[i] >> y[i];
        xx.pb(x[i]);
        yy.pb(y[i]);
    }
    sort(xx.begin(), xx.end());
    sort(yy.begin(), yy.end());

    for(int i = 0; i < xx.size(); i++){
        mpx[xx[i]] = i + 1;
    }
    for(int i = 0; i < yy.size(); i++){
        mpy[yy[i]] = i + 1;
    }
    for(int i = 1; i <= n; i++){
        points.pb({mpx[x[i]], mpy[y[i]]});
    }
    sort(points.begin(), points.end());
    divi(0, n - 1);
    cout << ans;
}

Compilation message (stderr)

scarecrows.cpp: In function 'void divi(int, int)':
scarecrows.cpp:61:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |     for(int i = 1; i < vv.size(); i++){
      |                    ~~^~~~~~~~~~~
scarecrows.cpp:81:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |     for(int i= 0; i < vec.size(); i++){
      |                   ~~^~~~~~~~~~~~
scarecrows.cpp: In function 'int main()':
scarecrows.cpp:132:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  132 |     for(int i = 0; i < xx.size(); i++){
      |                    ~~^~~~~~~~~~~
scarecrows.cpp:135:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  135 |     for(int i = 0; i < yy.size(); i++){
      |                    ~~^~~~~~~~~~~

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