Submission #1698517


Source Code Expand

#include <bits/stdc++.h>

using namespace std;

#define fst(t) std::get<0>(t)
#define snd(t) std::get<1>(t)
#define thd(t) std::get<2>(t)
#define unless(p) if(!(p))
#define until(p) while(!(p))

using ll = long long;
using P = std::tuple<int,int>;
using P3 = std::tuple<int,int,int>;

const int dx[8] = {-1, 1, 0, 0, -1, -1, 1, 1}, dy[8] = {0, 0, -1, 1, -1, 1, -1, 1};

const int INF = numeric_limits<int>::max() / 2;

P ps[100100], dp[100100];
int orderOfLeft[100100], orderOfRight[100100];
int mapping[100100], mapping2[100100]; // ps -> oOl, ps -> oOr

// I want to delete this stupid solution ;(
#define sandwich(x) [](auto a, auto b){return (x)(a, b);}

template <typename T>
using F2 = std::function<T(T,T)>;

template <typename T, int N>
struct SegmentTree{
    SegmentTree(){
        size = 1;
        while(size < N){
            size <<= 1;
        }

        unit = 0;
        
        init();
    }
    void init(){
        for(int i=0;i<size;++i){
            data[i+size] = unit;
            data2[i+size] = i;
        }

        for(int i=size-1;i>0;--i){
            data[i] = unit;
            data2[i] = data2[i*2];
        }
    }
    int safeAt(int idx){ // orderOfLeft[idx]
        if(1 <= idx && idx <= N){
            return orderOfLeft[idx];
        }
        return INF;
    }
    void update(int k, T v){
        k += size;
        data[k] = v;

        while(k > 1){
            k >>= 1;
            if(data[k*2] > data[k*2+1]){
                data[k] = data[k*2];
                data2[k] = data2[k*2];
            }else{
                data[k] = data[k*2+1];
                if(data[k*2] == data[k*2+1]){
                    data2[k] = safeAt(data2[k*2]) <= safeAt(data2[k*2+1]) ? data2[k*2] : data2[k*2+1];
                }else{
                    data2[k] = data2[k*2+1];
                }
            }
        }
    }
    inline tuple<T, int> query(int l, int r){
        return _query(l, r, 1, 0, size);
    }
    tuple<T, int> _query(int a, int b, int k, int l, int r){
        if(b <= l || r <= a){return std::make_tuple(unit, -1);}
        if(a <= l && r <= b){return std::make_tuple(data[k], data2[k]);}
        int mid = (l + r) >> 1;
        
        auto p1 = _query(a, b,   2*k,   l, mid),
            p2 = _query(a, b, 2*k+1, mid, r  );

        if(fst(p1) > fst(p2)){
            return p1;
        }else if(fst(p1) < fst(p2)){
            return p2;
        }else if(safeAt(snd(p1)) <= safeAt(snd(p2))){
            return p1;
        }
        return p2;
    }

    T unit, data[N*4], data2[N*4];
    int size;
};

SegmentTree<int, 100100> seg;

int main(){
    std::cin.tie(nullptr);
    std::ios::sync_with_stdio(false);

    int N;
    std::cin >> N;
    
    for(int i=1;i<=N;++i){
        int a, b;
        std::cin >> a >> b;
        ps[i] = std::make_tuple(a, b);
    }

    iota(orderOfLeft + 1, orderOfLeft + 1 + N, 1);
    iota(orderOfRight + 1, orderOfRight + 1 + N, 1);    

    sort(orderOfLeft + 1, orderOfLeft + 1 + N, [&](const int lhs, const int rhs){
            return fst(ps[lhs]) <= fst(ps[rhs]);
        });
    sort(orderOfRight + 1, orderOfRight + 1 + N, [&](const int lhs, const int rhs){
            return snd(ps[lhs]) <= snd(ps[rhs]);
        });

    for(int i=1;i<=N;++i){
        mapping[orderOfLeft[i]] = i;
        mapping2[orderOfRight[i]] = i;
    }

    seg.query(N + 1, N + 1);
    
    for(int i=N;i>0;--i){
        int r;
        tie(ignore, r) = ps[orderOfRight[i]];

        int first;
        {
            int lb = N + 1, ub = 0;

            while(std::abs(ub - lb) > 1){
                int mid = (lb + ub) / 2;

                if(fst(ps[orderOfLeft[mid]]) >= r){
                    lb = mid;
                }else{
                    ub = mid;
                }
            }

            first = lb;
        }
        
        int max_n, next_idx;
        tie(max_n, next_idx) = seg.query(first, N + 1);
        
        if(max_n == 0){
            dp[i] = std::make_tuple(1, -1);
        }else{
            next_idx = mapping2[orderOfLeft[next_idx]];
            dp[i] = std::make_tuple(max_n + 1, next_idx);
        }

        int i_in_oOl = mapping[orderOfRight[i]];
        seg.update(i_in_oOl, fst(dp[i]));
    }

    int first = 1;
    for(int i=2;i<=N;++i){
        if(fst(dp[i]) == fst(dp[1]) && orderOfRight[i] < orderOfRight[first]){
            first = i;
        }
    }

    vector<int> res;
    while(first != -1){
        res.emplace_back(orderOfRight[first]);
        first = snd(dp[first]);
    }

    std::cout << res.size() << std::endl;
    for(int i=0;i<res.size();++i){
        std::cout << res[i] << " \n"[i + 1 == res.size()];
    }
}

Submission Info

Submission Time
Task C - 仕事計画
User iwashisnake
Language C++14 (GCC 5.4.1)
Score 0
Code Size 4845 Byte
Status RE
Exec Time 147 ms
Memory 6776 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 100
Status
AC × 3
AC × 21
RE × 6
Set Name Test Cases
Sample sample1.txt, sample2.txt, sample3.txt
All 0.txt, 1.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 2.txt, 20.txt, 21.txt, 22.txt, 23.txt, 3.txt, 4.txt, 5.txt, 6.txt, 7.txt, 8.txt, 9.txt, sample1.txt, sample2.txt, sample3.txt
Case Name Status Exec Time Memory
0.txt AC 4 ms 5888 KB
1.txt AC 4 ms 5888 KB
10.txt AC 3 ms 5888 KB
11.txt AC 4 ms 5888 KB
12.txt RE 107 ms 5888 KB
13.txt AC 4 ms 5888 KB
14.txt AC 4 ms 5888 KB
15.txt RE 106 ms 5888 KB
16.txt AC 4 ms 5888 KB
17.txt AC 4 ms 5888 KB
18.txt RE 119 ms 6016 KB
19.txt RE 147 ms 6016 KB
2.txt AC 4 ms 5888 KB
20.txt AC 101 ms 6016 KB
21.txt RE 118 ms 6016 KB
22.txt RE 119 ms 6016 KB
23.txt AC 98 ms 6776 KB
3.txt AC 4 ms 5888 KB
4.txt AC 4 ms 5888 KB
5.txt AC 4 ms 5888 KB
6.txt AC 4 ms 5888 KB
7.txt AC 3 ms 5888 KB
8.txt AC 4 ms 5888 KB
9.txt AC 3 ms 5888 KB
sample1.txt AC 4 ms 5888 KB
sample2.txt AC 4 ms 5888 KB
sample3.txt AC 4 ms 5888 KB