General
 
 
# Author Problem Lang Verdict Time Memory Sent Judged  
129807390 Practice:
Czhgugugu
39C - 15 C++17 (GCC 9-64) Accepted 62 ms 4788 KB 2021-09-25 05:03:41 2021-09-25 05:03:42
→ Source
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
typedef pair <int, int> pin;

#ifndef ONLINE_JUDGE
bool MEMORY_ST;
#endif

const int N = 4005;
const ll P = 998244353LL;
const int inf = 2e9;

int n, m, pos[N], f[N], pre[N];
vector <int> res[N], vec[N], pot, finalAns;

struct Bracket {
    int l, r, id, ans;
} a[N];

bool cmp1(const Bracket &u, const Bracket &v) {
    return u.r - u.l < v.r - v.l;
}

bool cmp2(const Bracket &u, const Bracket &v) {
    return u.id < v.id;
}

namespace Fread {
    const int L = 1 << 15;
    
    char buffer[L], *S, *T;
    
    inline char Getchar() {
        if(S == T) {
            T = (S = buffer) + fread(buffer, 1, L, stdin);
            if(S == T) return EOF;
        }
        return *S++;
    }
    
    template <class T> 
    inline void read(T &X) {
        char ch; T op = 1;
        for(ch = Getchar(); ch > '9' || ch < '0'; ch = Getchar())
            if(ch == '-') op = -1;
        for(X = 0; ch >= '0' && ch <= '9'; ch = Getchar()) 
            X = (X << 1) + (X << 3) + ch - '0'; 
        X *= op;
    }
    
} using Fread::read; 

inline void discrete() {
    vector <pin> tmp(n + n + 1);
    tmp[0] = pin(-inf, 0);
    for (int i = 1; i <= n; i++) {
        tmp[i].first = a[i].l, tmp[i].second = i;
        tmp[i + n].first = a[i].r, tmp[i + n].second = i + n;
    }
    sort(tmp.begin(), tmp.end());
    
    // for (int i = 0; i < tmp.size(); i++)
    //     printf("%d%c", tmp[i].first, " \n"[i == tmp.size() - 1]);

    m = 0;
    for (int i = 1; i <= n + n; i++) {
        if (tmp[i].first != tmp[i - 1].first) ++m;
        if (tmp[i].second > n) {
            a[tmp[i].second - n].r = m;
        } else {
            a[tmp[i].second].l = m; 
        }
    }
}

inline void getAns(int l, int r, vector <int> &v) {
    assert(v.empty());
    int p = r;
    for (; p >= l; ) {
        if (!pre[p]) --p;
        else {
            v.emplace_back(pre[p]);
            p = a[pre[p]].l; 
        } 
    }
}

void getFinalAns(int cur) {
    finalAns.emplace_back(cur);
    for (int i = 0; i < res[cur].size(); i++) getFinalAns(res[cur][i]);
}

inline void solve(int l, int r, bool flag, int cur) {
    for (int i = l; i <= r; i++) {
        if (i != l) {
            f[i] = f[i - 1];
            pre[i] = 0;
        } 
        for (int j = 0; j < vec[i].size(); j++) {
            int id = vec[i][j];
            if (id == cur) continue;
            if (a[id].l >= l) {
                if (f[a[id].l] + a[id].ans > f[i]) {
                    f[i] = f[a[id].l] + a[id].ans;
                    pre[i] = id;
                }
            }
        }
    }
    if (!flag) return;
    a[cur].ans = f[r] + 1;
    getAns(l, r, res[cur]);
}

inline void clear(int l, int r) {
    for (int i = l; i <= r; i++) f[i] = pre[i] = 0;
}

#ifndef ONLINE_JUDGE
bool MEMORY_ED;
#endif

int main() {
#ifndef ONLINE_JUDGE
    freopen("sample.in", "r", stdin);
    clock_t st_clock = clock();
#endif

    read(n);
    for (int r, c, i = 1; i <= n; i++) {
        read(c), read(r);
        a[i].l = c - r, a[i].r = c + r, a[i].id = i;
    }
    discrete();
    
    // printf("%d\n", m);
    // for (int i = 1; i <= n; i++) printf("%d %d\n", a[i].l, a[i].r);

    for (int i = 1; i <= n; i++) vec[a[i].r].emplace_back(i);
    sort(a + 1, a + 1 + n, cmp1);
    for (int i = 1; i <= n; i++) pos[i] = a[i].id;
    sort(a + 1, a + 1 + n, cmp2);

    for (int i = 1; i <= n; i++) {
        int cur = pos[i];
        solve(a[cur].l, a[cur].r, 1, cur);
        clear(a[cur].l, a[cur].r);
    }

    // for (int i = 1; i <= n; i++) printf("%d\n", a[i].ans);
    // for (int i = 1; i <= n; i++) {
    //     printf("%d: ", i);
    //     for (int j = 0; j < res[i].size(); j++)
    //         printf("%d%c", res[i][j], " \n"[j == res[i].size() - 1]);
    //     if (res[i].empty()) puts("");
    // }

    solve(1, m, 0, 0);
    printf("%d\n", f[m]);
    getAns(1, m, pot);

    // for (int i = 0; i < pot.size(); i++)
    //     printf("%d%c", pot[i], " \n"[i == pot.size() - 1]);

    for (int i = 0; i < pot.size(); i++) getFinalAns(pot[i]);
    for (int i = 0; i < finalAns.size(); i++)
        printf("%d%c", finalAns[i], " \n"[i == finalAns.size() - 1]);

#ifndef ONLINE_JUDGE
    clock_t ed_clock = clock();
    printf("time = %f ms\n", (double)(ed_clock - st_clock) / CLOCKS_PER_SEC * 1000);
    printf("memory = %.2f MB\n", (&MEMORY_ED - &MEMORY_ST) / 1024.0 / 1024.0);
#endif
    return 0;
}
?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details