12542022-03-29 10:53:10FulopMateHadjáratcpp14Futási hiba 16/100115ms63460 KiB
#include <bits/stdc++.h>

using namespace std;

//#define __TEST_CASE_TEXT
#define __TEST_CASE_BEFORE "Case #"
#define __TEST_CASE_AFTER ": "

#define ll long long
#define all(c) (c).begin(), (c).end()
#define MIN(a, b) ((a) = min((a), (b)))
#define MAX(a, b) ((a) = max((a), (b)))

const ll MOD = 1e9+7;
const int abc = 'z'-'a'+1;


int n;
vector<int> ans, p;

struct ST {
    int lx = 1, rx = 1e6, ly = 1, ry = 1e6;
    int id;
    ST() {id = n;}
    ST(int lx_, int rx_, int ly_, int ry_) : lx(lx_), rx(rx_), ly(ly_), ry(ry_) {
        id = n;
    }

    ST *a = nullptr, *b = nullptr, *c = nullptr, *d = nullptr;

    int getqueryfrom(ST *x, int clx, int crx, int cly, int cry){
        if(!x)return n;
        return x->query(clx, crx, cly, cry);
    }

    int query(int clx, int crx, int cly, int cry){
        if(clx > rx || crx < lx || cly > ry || cry < ly){
            return n;
        }
        if(lx == rx && ly == ry){
            return id;
        }
        // int mx = (lx + rx) >> 1, my = (ly + ry) >> 1;
        // int a[] = {this->getqueryfrom(a, lx, mx, ly, my),
        // this->getqueryfrom(b, mx+1, rx, ly, my),
        // this->getqueryfrom(c, lx, mx, my+1, ry),
        // this->getqueryfrom(d, mx+1, rx, my+1, ry)};
        int x[] = {this->getqueryfrom(a, clx, crx, cly, cry),
        (ly == ry ? n : this->getqueryfrom(b, clx, crx, cly, cry)),
        (lx == rx ? n : this->getqueryfrom(c, clx, crx, cly, cry)),
        (ly == ry || lx == ry ? n : this->getqueryfrom(d, clx, crx, cly, cry))};
        int r = n;
        for(int i : x){
            if(ans[i] > ans[r])r = i;
        }
        return r;
    }

    void insert(int x, int y, int ind){
        if(lx == rx && ly == ry){
            if(ans[ind] > ans[id])id = ind;
            return;
        }
        int mx = (lx + rx) >> 1, my = (ly + ry) >> 1;
        if(x <= mx){
            if(y <= my){
                if(!a){
                    a = new ST(lx, mx, ly, my);
                }
                a->insert(x, y, ind);
            } else {
                if(!b){
                    b = new ST(lx, mx, my+1, ry);
                }
                b->insert(x, y, ind);
            }
        } else {
            if(y <= my){
                if(!c){
                    c = new ST(mx+1, rx, ly, my);
                }
                c->insert(x, y, ind);
            } else {
                if(!d){
                    d = new ST(mx+1, rx, my+1, ry);
                }
                d->insert(x, y, ind);
            }
        }
    }

};


void solve(){
    cin>>n;
    ans.assign(n+1, 1);
    ans[n] = -1e9;
    int r = 0;
    p.assign(n+1, -1);
    vector<pair<int,int>> v;
    vector<int> w1, w2;
    for(int i = 0; i < n; i++){
        int a, b; cin>>a>>b;
        v.push_back({a, b});
        w1.push_back(a); w2.push_back(b);
    }
    sort(all(w1)); sort(all(w2));
    w1.erase(unique(all(w1)), w1.end());
    w2.erase(unique(all(w2)), w2.end());
    int m1 = w1.size(), m2 = w2.size();
    map<int, int> z1, z2;
    for(int i = 0; i < n; i++){
        z1[w1[i]] = i;
        z2[w2[i]] = i;
    }
    ST *st = new ST(0, m1, 0, m2);
    for(int i = 0; i < n; i++){
        int a = z1[v[i].first], b = z2[v[i].second];
        int c = st->query(0, a-1, 0, b-1);
        MAX(ans[i], ans[c] + 1);
        if(ans[i] > ans[r])r = i;
        p[i] = c;
        st->insert(a, b, i);
    }
    cout<<ans[r]<<endl;
    vector<int> rr;
    while(r != n){
        rr.push_back(r);
        r = p[r];
    }
    reverse(all(rr));
    for(int i : rr)cout<<i+1<<" ";
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int _t;
    _t = 1;
    for(int _i = 0; _i < _t; _i++){
        #ifdef __TEST_CASE_TEXT
        cout<<__TEST_CASE_BEFORE<<_i+1<<__TEST_CASE_AFTER;
        #endif
        solve();
    }
    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base16/100
1Elfogadva0/02ms1884 KiB
2Futási hiba0/071ms61696 KiB
3Futási hiba0/435ms62208 KiB
4Elfogadva4/41ms2592 KiB
5Elfogadva4/41ms2596 KiB
6Elfogadva4/41ms2604 KiB
7Elfogadva4/42ms2604 KiB
8Futási hiba0/445ms62232 KiB
9Futási hiba0/439ms62236 KiB
10Futási hiba0/439ms62244 KiB
11Futási hiba0/454ms62252 KiB
12Futási hiba0/457ms62252 KiB
13Futási hiba0/650ms62368 KiB
14Futási hiba0/648ms62552 KiB
15Futási hiba0/656ms62932 KiB
16Futási hiba0/671ms63068 KiB
17Futási hiba0/686ms63460 KiB
18Futási hiba0/693ms62736 KiB
19Futási hiba0/6114ms62936 KiB
20Futási hiba0/6114ms63064 KiB
21Futási hiba0/6111ms63060 KiB
22Futási hiba0/6115ms63056 KiB