oj.uz

Submission #758863

# Submission time Handle Problem Language Result Execution time Memory
758863 2023-06-15T11:42:42 Z Ronin13 허수아비 (JOI14_scarecrows) C++14
100 / 100
 2152 ms 35248 KB 
#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

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

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 4320 KB Output is correct
2 Correct 34 ms 4180 KB Output is correct
3 Correct 28 ms 4316 KB Output is correct
4 Correct 24 ms 4308 KB Output is correct
5 Correct 28 ms 4308 KB Output is correct
6 Correct 30 ms 4300 KB Output is correct
7 Correct 31 ms 4308 KB Output is correct
8 Correct 22 ms 4308 KB Output is correct
9 Correct 35 ms 4180 KB Output is correct
10 Correct 31 ms 4180 KB Output is correct
11 Correct 34 ms 4300 KB Output is correct
12 Correct 22 ms 4180 KB Output is correct

Subtask #3
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1447 ms 35180 KB Output is correct
2 Correct 2152 ms 34516 KB Output is correct
3 Correct 1682 ms 34108 KB Output is correct
4 Correct 1451 ms 34616 KB Output is correct
5 Correct 1703 ms 34076 KB Output is correct
6 Correct 1921 ms 34004 KB Output is correct
7 Correct 2035 ms 33972 KB Output is correct
8 Correct 2079 ms 34084 KB Output is correct
9 Correct 1341 ms 35248 KB Output is correct
10 Correct 1836 ms 34364 KB Output is correct
11 Correct 2084 ms 33936 KB Output is correct
12 Correct 2082 ms 33988 KB Output is correct
13 Correct 2122 ms 33672 KB Output is correct
14 Correct 1382 ms 34868 KB Output is correct
15 Correct 1996 ms 33716 KB Output is correct
16 Correct 2081 ms 33804 KB Output is correct
17 Correct 1171 ms 23028 KB Output is correct
18 Correct 2025 ms 33864 KB Output is correct
19 Correct 1948 ms 33592 KB Output is correct
20 Correct 1958 ms 33796 KB Output is correct