Submission #1698409


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];
        }
    }
    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] = data2[k*2+1] > N || orderOfLeft[data2[k*2]] < orderOfLeft[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(snd(p1) == -1){
            return p2;
        }else if(snd(p2) == -1){
            return p1;
        }else if(orderOfLeft[snd(p1)] < orderOfLeft[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;
    }

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

        int first;
        {
            int lb = N, 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 = fst(ps[orderOfLeft[lb]]) >= r ? lb : N + 1;
        }
        
        int max_n, next_idx;
        tie(max_n, next_idx) = seg.query(first, N + 1);
        next_idx = mapping2[orderOfLeft[next_idx]];
        
        if(max_n == 0){
            dp[i] = std::make_tuple(1, -1);
        }else{
            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 4882 Byte
Status RE
Exec Time 124 ms
Memory 6016 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 100
Status
WA × 3
WA × 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 WA 3 ms 5888 KB
1.txt WA 3 ms 5888 KB
10.txt WA 3 ms 5888 KB
11.txt WA 3 ms 5888 KB
12.txt RE 98 ms 5888 KB
13.txt WA 3 ms 5888 KB
14.txt WA 3 ms 5888 KB
15.txt RE 100 ms 5888 KB
16.txt WA 3 ms 5888 KB
17.txt WA 3 ms 5888 KB
18.txt RE 114 ms 6016 KB
19.txt RE 124 ms 6016 KB
2.txt WA 3 ms 5888 KB
20.txt WA 85 ms 6016 KB
21.txt RE 113 ms 6016 KB
22.txt RE 114 ms 6016 KB
23.txt WA 79 ms 6016 KB
3.txt WA 3 ms 5888 KB
4.txt WA 3 ms 5888 KB
5.txt WA 3 ms 5888 KB
6.txt WA 3 ms 5888 KB
7.txt WA 3 ms 5888 KB
8.txt WA 3 ms 5888 KB
9.txt WA 3 ms 5888 KB
sample1.txt WA 3 ms 5888 KB
sample2.txt WA 3 ms 5888 KB
sample3.txt WA 3 ms 5888 KB