1252 2022. 03. 29 10:34:02 FulopMate Hadjárat cpp14 Időlimit túllépés 32/100 298ms 5356 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),
        this->getqueryfrom(b, clx, crx, cly, cry),
        this->getqueryfrom(c, clx, crx, cly, cry),
        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(){
    ST *st = new ST();
    cin>>n;
    ans.assign(n+1, 1);
    ans[n] = -1e9;
    int r = 0;
    p.assign(n+1, -1);
    for(int i = 0; i < n; i++){
        int a, b; cin>>a>>b;
        int c = st->query(1, a-1, 1, 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 Összpont Teszt Verdikt Idő Memória
base 32/100
1 Elfogadva 0/0 3ms 1912 KiB
2 Időlimit túllépés 0/0 293ms 3456 KiB
3 Elfogadva 4/4 1ms 2136 KiB
4 Elfogadva 4/4 1ms 2112 KiB
5 Elfogadva 4/4 1ms 2124 KiB
6 Elfogadva 4/4 1ms 2128 KiB
7 Elfogadva 4/4 1ms 2140 KiB
8 Elfogadva 4/4 1ms 2132 KiB
9 Elfogadva 4/4 2ms 2176 KiB
10 Elfogadva 4/4 32ms 3224 KiB
11 Időlimit túllépés 0/4 293ms 3084 KiB
12 Időlimit túllépés 0/4 298ms 3312 KiB
13 Időlimit túllépés 0/6 286ms 2960 KiB
14 Időlimit túllépés 0/6 287ms 3172 KiB
15 Időlimit túllépés 0/6 298ms 3864 KiB
16 Időlimit túllépés 0/6 284ms 4016 KiB
17 Időlimit túllépés 0/6 287ms 4556 KiB
18 Időlimit túllépés 0/6 298ms 4768 KiB
19 Időlimit túllépés 0/6 296ms 5016 KiB
20 Időlimit túllépés 0/6 296ms 5352 KiB
21 Időlimit túllépés 0/6 284ms 5184 KiB
22 Időlimit túllépés 0/6 294ms 5356 KiB