Submission #420225

#	Time	Username	Problem	Language	Result	Execution time	Memory
420225		parsabahrami	Financial Report (JOI21_financial)	C++17	100 / 100	2423 ms	38536 KiB

Main

#include <bits/stdc++.h>
 
using namespace std;

typedef long long int ll;
typedef pair<int, int> pii;
 
#define SZ(x)                       (int) x.size()
#define F                           first
#define S                           second
#define lc                          id << 1
#define rc                          lc | 1

const int N = 3e5 + 10, MOD = 1e9 + 7;
int n, D, dp[N], A[N], seg[N << 2]; vector<int> cp, vec[N]; set<int> st1, st2;

void upd(int p, int x, int id = 1, int l = 1, int r = n + 1) {
    if (r - l < 2) {
        seg[id] = x;
        return;
    }
    int md = (l + r) >> 1;
    if (p < md) upd(p, x, lc, l, md);
    else upd(p, x, rc, md, r);
    seg[id] = max(seg[lc], seg[rc]);
}

int get(int ql, int qr, int id = 1, int l = 1, int r = n + 1) {
    if (qr <= l || r <= ql || ql >= qr) return 0;
    if (ql <= l && r <= qr) return seg[id];
    int md = (l + r) >> 1;
    return max(get(ql, qr, lc, l, md), get(ql, qr, rc, md, r));
}

void add(int pos) {
    if (SZ(st1)) {
        if (*st1.begin() < pos) {
            auto it = st1.upper_bound(pos); it--;
            if (pos - *it > D) st2.insert(pos);
            it++;
            if (it != st1.end()) {
                st2.erase(*it);
                if (*it - pos > D) st2.insert(*it);
            }
            st1.insert(pos);
        } else {
            auto it = st1.upper_bound(pos);
            st1.insert(pos);
            if (*it - pos > D) st2.insert(*it);
        }
    } else {
        st1.insert(pos);
    }
}

void remove(int pos) {
    if (*st1.begin() < pos) {
        st2.erase(pos);
        auto it = st1.upper_bound(pos);
        if (it != st1.end()) {
            st2.erase(*it);
            int x = *it;
            it--; assert(*it == pos);
            it--;
            if (x - *it > D) st2.insert(x);
        }
        st1.erase(pos);
    } else {
        auto it = st1.upper_bound(pos);
        if (it != st1.end()) st2.erase(*it);
        st1.erase(pos);
    }
}

void print() {
    printf("start\n");
    for (int x : st2) 
        printf("%d ", x);
    printf("\nend\n");
}

int main() {
    scanf("%d%d", &n, &D);
    for (int i = 1; i <= n; i++) 
        scanf("%d", &A[i]), cp.push_back(A[i]);
    sort(begin(cp), end(cp));
    cp.resize(unique(begin(cp), end(cp)) - begin(cp));
    for (int i = 1; i <= n; i++) {
        int id = lower_bound(begin(cp), end(cp), A[i]) - begin(cp);
        vec[id].push_back(i);
    }
    for (int i = 0; i < SZ(cp); i++) {
        for (int &j : vec[i]) {
            //dp[i] = get(l, j) + 1;
            add(j);
            if (st2.empty() || *st2.begin() > j) dp[j] = get(1, j) + 1;
            else {
                auto it = st2.upper_bound(j); it--;
                dp[j] = get(*it, j) + 1;
            }
            remove(j);
        } 
        for (int &j : vec[i])
            upd(j, dp[j]), add(j);
        //print();
    }
    int ret = dp[n];
    st1.clear();
    st2.clear();
    for (int i = 0; i < SZ(cp); i++) {
        for (int &j : vec[i]) 
            add(j);
        if (cp[i] >= A[n]) {
            for (int &j : vec[i]) {
                auto it = st2.upper_bound(j);
                if (it == st2.end()) ret = max(ret, dp[j]);
            }
        }
    }
    printf("%d\n", ret);
    return 0;
}
    

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:83:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |     scanf("%d%d", &n, &D);
      |     ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:85:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |         scanf("%d", &A[i]), cp.push_back(A[i]);
      |         ~~~~~^~~~~~~~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 20 / 20
• Subtask 4: 12 / 12
• Subtask 5: 5 / 5
• Subtask 6: 35 / 35