Submission #771195

#	Time	Username	Problem	Language	Result	Execution time	Memory
771195		VahanAbraham	Financial Report (JOI21_financial)	C++14	45 / 100	1216 ms	7276 KiB

Main

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <sstream>
#include <map>
#include <stack>
#include <set>
#include <queue>
#include <unordered_set>
#include <unordered_map>
#include <math.h>
#include <cmath>
#include <vector>
#include <iomanip>
using namespace std;

#define ll long long
#define fr first
#define sc second
#define pb push_back
#define US freopen("revegetate.in", "r", stdin); freopen("revegetate.out", "w", stdout);
#define m_p make_pair
#define moo -1000000000000000;
#define poo 1000000000000000;

ll gcd(ll a, ll b)
{
    if (a == 0 || b == 0) {
        return  max(a, b);
    }
    if (a <= b) {
        return gcd(a, b % a);
    }
    else {
        return gcd(a % b, b);
    }
}

ll lcm(ll a, ll b) {
    return (a / gcd(a, b)) * b;
}

const int N = 300010;

ll mx[N];
ll ans[N];

vector<pair<ll int, ll int>> dp[405];
ll int mxx[405];
ll a[N];


void solve() {
    int n, d;
    cin >> n >> d;
    for (int i = 1;i <= n;i++) {
        cin >> a[i];
    }
    if (d == 1) {
        if (n == 1) {
            cout << 1 << endl;
            return;
        }
        ll pat = 1, l = n - 1, r = n;
        mx[n] = a[n];
        ans[n] = 1;
        for (int i = n - 1;i >= 1;i--) {
            ll kk = n + 1;
            r = n;
            // cout << i << " " << l << " " << r << endl;
            while (l <= r) {
                ll mid = (l + r) / 2;
                //cout << i << " " << mid << " " << mx[mid] << endl;
                if (mx[mid] > a[i]) {
                    kk = mid;
                    r = mid - 1;
                }
                else {
                    l = mid + 1;
                }
            }
            //cout << kk << " " << i << endl;
            if (kk != n + 1) {
                pat = max(ans[kk] + 1, pat);
                ans[kk - 1] = ans[kk] + 1;
                mx[kk - 1] = a[i];
                l = kk - 1;
            }
            else {
                l = n;
                ans[l] = 1;
                mx[l] = a[i];
            }
        }
        cout << pat << endl;
        return;
    }
    if (n <= 400) {
        if (n == 1) {
            cout << 1 << endl;
            return;
        }
        dp[1].push_back({ a[1],1 });
        mxx[1] = 1;
        map<ll, ll> mp;
        vector<ll> v;
        for (int i = 2;i <= n;i++) {
            for (int j = max(i - d, 1);j < i;j++) {
                for (int k = 0;k < dp[j].size();k++) {
                    if (dp[j][k].fr < a[i]) {
                        if (mp[a[i]] == 0) {
                            v.pb(a[i]);
                        }
                        mp[a[i]] = max(mp[a[i]], dp[j][k].sc + 1);
                    }
                    else {
                        if (mp[dp[j][k].fr] == 0) {
                            v.pb(dp[j][k].fr);
                        }
                        mp[dp[j][k].fr] = max(mp[dp[j][k].fr], dp[j][k].sc);
                    }
                }
            }
            if (mp[a[i]] == 0) {
                v.pb(a[i]);
            }
            mp[a[i]] = max(mp[a[i]], 1LL);
            for (int j = 0;j < v.size();j++) {
                dp[i].push_back({ v[j],mp[v[j]] });
                mxx[i] = max(mxx[i], mp[v[j]]);
            }
            mp.clear();
            v.clear();
        }
        cout << mxx[n] << endl;
        return;
    }
    if (d == n) {
        vector<ll> v;
        for (int i = 1;i <= n;i++) {
            if (v.size() == 0) {
                v.pb(a[i]);
                continue;
            }
            int x = lower_bound(v.begin(), v.end(), a[i]) - v.begin();
            if (x < v.size()) {
                v[x] = a[i];
            }
            else {
                v.pb(a[i]);
            }
        }
        cout << v.size() << endl;
        return;
    }
    if (n <= 7000) {
        vector<ll> v;
        map<ll, ll> mp;
        for (int i = 1;i <= n;i++) {
            if (mp[a[i]] != 1) {
                v.push_back(a[i]);
                mp[a[i]] = 1;
            }
            for (int j = 0;j < v.size();j++) {
                if (v[j] < a[i]) {
                    mp[a[i]] = max(mp[v[j]]+1, mp[a[i]]);
                }
            }
        }
        cout << mp[a[n]] << endl;
        return;
    }
    /*for (int i = 1;i <= n;i++) {
        if (i > d) {
            for (int j = i - d;j < i;j++) {
                int l = 0;
                int r = dp[j].size() - 1, ind = -1;
                while (l <= r) {
                    int mid = (l + r) / 2;
                    if (dp[j][mid].fr < a[i]) {
                        ind = mid;
                        l = mid + 1;
                    }
                    else {
                        r = mid - 1;
                    }
                }
                if (ind != -1) {
                    if (sum[ind] + 1 > mx) {
                        mx = sum[ind] + 1;
                    }
                }
                else {
                    for (int jj = 0;jj < dp[j].size();jj++) {
                        dp[i].push_back({ dp[j][jj].fr,dp[j][jj].sc });
                    }
                }
            }
            if (mx != -1) {
                dp[i].pb({ mx,a[i] });
            }
            sort(dp[i].begin(), dp[i].end());
        }
        else {

        }
    }*/
}


int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    //US
    int tt = 1;
    //cin >> tt;
    while (tt--) {
        solve();
    }
}

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:112:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |                 for (int k = 0;k < dp[j].size();k++) {
      |                                ~~^~~~~~~~~~~~~~
Main.cpp:131:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |             for (int j = 0;j < v.size();j++) {
      |                            ~~^~~~~~~~~~
Main.cpp:149:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  149 |             if (x < v.size()) {
      |                 ~~^~~~~~~~~~
Main.cpp:167:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  167 |             for (int j = 0;j < v.size();j++) {
      |                            ~~^~~~~~~~~~

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