Submission #536137

#	Time	Username	Problem	Language	Result	Execution time	Memory
536137		sare	Financial Report (JOI21_financial)	C++17	5 / 100	3621 ms	274660 KiB

Main

//In the name of Allah :)
#include <bits/stdc++.h>
using namespace std;
string to_string(char c) { return string(1,c); }
string to_string(bool b) { return b ? "true" : "false"; }
string to_string(const char* s) { return (string)s; }
string to_string(string s) { return s; }
template<class A> string to_string(complex<A> c) { 
    stringstream ss; ss << c; return ss.str(); }
string to_string(vector<bool> v) { 
    string res = "{"; for(int i = 0; i < (int)v.size(); i++) res += char('0'+v[i]);
    res += "}"; return res; }
template<size_t SZ> string to_string(bitset<SZ> b) {
    string res = ""; for(size_t i = 0; i < SZ; i++) res += char('0'+b[i]);
    return res; }
template<class A, class B> string to_string(pair<A,B> p);
template<class T> string to_string(T v) { // containers with begin(), end()
    bool fst = 1; string res = "{";
    for (const auto& x: v) {
        if (!fst) res += ", ";
        fst = 0; res += to_string(x);
    }
    res += "}"; return res;
}
template<class A, class B> string to_string(pair<A,B> p) {
    return "("+to_string(p.first)+", "+to_string(p.second)+")"; }
void DBG() { cerr << "]" << endl; }
template<class H, class... T> void DBG(H h, T... t) {
    cerr << to_string(h); if (sizeof...(t)) cerr << ", ";
    DBG(t...); }
#ifdef LOCAL // compile with -DLOCAL
#define wis(...) cerr << "LINE(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "] : [", DBG(__VA_ARGS__)
#else
#define wis(...) 0
#endif
typedef long long ll;
typedef long double ld;
#define all(x) (x).begin(), (x).end()
const int MAXN = 3e5 + 10;
int n, d, a[MAXN], dp[MAXN];

struct Fenwick {
    multiset<int> s[MAXN];

    inline void add (int ind, int val) {
        for (ind += 2; ind < MAXN; ind += ind & -ind) {
            s[ind].insert(val);
        }
    }

    inline int get (int ind) {
        int res = 0;
        for (ind += 2; ind; ind -= ind & -ind) {
            if (s[ind].size()) {
                res = max(res, *s[ind].rbegin());
            }
        }
        return res;
    }

    inline void remove (int ind, int val) {
        for (ind += 2; ind < MAXN; ind += ind & -ind) {
            s[ind].erase(s[ind].find(val));
        }
    }
} fen;

int main() {
    ios::sync_with_stdio(0);cin.tie(0);
    cin >> n >> d;
    vector<int> num(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        num[i] = a[i];
    }
    sort(all(num));
    num.erase(unique(all(num)), num.end());
    for (int i = 0; i < n; ++i) {
        a[i] = lower_bound(all(num), a[i]) - num.begin() + 1;
    }

    for (int i = 0; i < n; ++i) {
        dp[i] = fen.get(a[i] - 1) + 1;
        wis(i, dp[i]);
        fen.add(a[i], dp[i]);
        if (i - d >= 0) {
            fen.remove(a[i - d], dp[i - d]);
        }
    }
    cout << *max_element(dp, dp + n) << '\n';
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:34:18: warning: statement has no effect [-Wunused-value]
   34 | #define wis(...) 0
      |                  ^
Main.cpp:84:9: note: in expansion of macro 'wis'
   84 |         wis(i, dp[i]);
      |         ^~~

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