12552022-03-29 11:03:46FulopMateHadjáratcpp14Time limit exceeded 32/100289ms22824 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(){
    // ifstream cin("be.txt");
    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 < m1; i++){
        z1[w1[i]] = i;
    }
    for(int i = 0; i < m2; 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;
}
SubtaskSumTestVerdictTimeMemory
base32/100
1Accepted0/02ms2000 KiB
2Time limit exceeded0/0250ms8000 KiB
3Accepted4/41ms2640 KiB
4Accepted4/41ms2652 KiB
5Accepted4/41ms2648 KiB
6Accepted4/41ms2648 KiB
7Accepted4/41ms2660 KiB
8Accepted4/41ms2676 KiB
9Accepted4/42ms2732 KiB
10Accepted4/420ms3628 KiB
11Time limit exceeded0/4202ms3532 KiB
12Time limit exceeded0/4208ms4284 KiB
13Time limit exceeded0/6201ms3988 KiB
14Time limit exceeded0/6202ms4692 KiB
15Time limit exceeded0/6238ms7104 KiB
16Time limit exceeded0/6250ms9476 KiB
17Time limit exceeded0/6248ms12288 KiB
18Time limit exceeded0/6206ms14328 KiB
19Time limit exceeded0/6206ms16452 KiB
20Time limit exceeded0/6206ms19816 KiB
21Time limit exceeded0/6209ms21204 KiB
22Time limit exceeded0/6289ms22824 KiB