Submission #1087011

#	Time	Username	Problem	Language	Result	Execution time	Memory
1087011		cccc	Financial Report (JOI21_financial)	C++14	53 / 100	67 ms	8276 KiB

Main

/// YVKNTD
#include <bits/stdc++.h>
#define int long long
#define ld long double
#define f(i, a, b) for(int i = a; i <= b; i++)
#define fr(i, a, b) for(int i = a; i >= b; i--)
#define pii pair <int, int>
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define in insert
#define vvec vector<vector<int>>
#define Keiiiii ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ___ 1000 * clock() / CLOCKS_PER_SEC

using namespace std;

const int N = 3e5 + 5;
const int mod = 1e9 + 7;
const int inf = 1e16;
int n, k, a[N];

void READ()
{
    cin >> n >> k;
    f(i, 1, n) cin >> a[i];
}

struct ST
{
    int st[N * 4];
    void up(int i, int l, int r, int j, int w)
    {
        if(j > r || j < l) return;
        if(l == r) { st[i] = w; return; }
        int mid = (l + r) >> 1;
        up(i << 1, l, mid, j, w);
        up(i << 1 | 1, mid + 1, r, j, w);
        st[i] = min(st[i << 1], st[i << 1 | 1]);
    }

    int get(int i, int l, int r, int x, int y)
    {
        if(x > r || y < l) return 0;
        if(x <= l && r <= y) return st[i];
        int mid = (l + r) >> 1;
        return min(get(i << 1, l, mid, x, y), get(i << 1 | 1, mid + 1, r, x, y));
    }
} f;

void cmprss()
{
    vector <int> z;
    f(i, 1, n) z.eb(a[i]);
    sort(z.begin(), z.end());
    z.resize(unique(z.begin(), z.end()) - z.begin());
    f(i, 1, n) a[i] = lower_bound(z.begin(), z.end(), a[i]) - z.begin() + 1;
}

int dp[N];
void sub3()
{
    f(i, 1, n)
    {
        dp[i] = 1;
        int cnt = 0, mx = 0, ok = 1;
        fr(j, i - 1, 1)
        {
            mx = max(a[j], mx);
            if(a[j] >= a[i]) cnt++;
            else cnt = 0;

            if(cnt >= k) ok = 0;
            if(i - j <= k)
            {
                if(a[i] > a[j]) dp[i] = max(dp[i], dp[j] + 1);
            }
            else if(ok)
            {
                if(a[i] > a[j]) dp[i] = max(dp[i], dp[j] + 1);
            }
        }
    }
    cout << *max_element(dp + 1, dp + n + 1) << "\n";
}

void sub4()
{

}

void sub5()
{
    vector <int> ff(n + 1, inf);
    ff[0] = -inf;

    int ans = 1;
    f(i, 1, n)
    {
        int k = lower_bound(ff.begin(), ff.end(), a[i]) - ff.begin();
        ff[k] = a[i];
        ans = max(ans, k);
    }
    cout << ans << "\n";
}

void SOLVE()
{
    if(n <= 7000) sub3();
    else if(k == 1) sub4();
    else if(k == n) sub5();
//    k++;
//    cmprss();
//    multiset <int> s;
//    int ans = 0;
//    f(i, 1, n)
//    {
//        if(i > k)
//        {
//            s.erase(s.find(a[i - k]));
//            if(s.find(a[i - k]) == s.end()) f.up(1, 1, n, a[i - k], 0);
//        }
//        s.in(a[i]);
//        int cur = f.get(1, 1, n, 1, a[i] - 1) + 1;
//        f.up(1, 1, n, a[i], cur);
//        ans = max(ans, cur);
//    }
//    cout << ans;
}

signed main()
{
    Keiiiii
    if(fopen("TASK.INP", "r"))
    {
        freopen("TASK.INP", "r", stdin);
        freopen("TASK.OUT", "w", stdout);
    }
    #define TASK "IMPAIR"
    if(fopen(TASK ".INP", "r"))
    {
        freopen(TASK ".INP", "r", stdin);
        freopen(TASK ".OUT", "w", stdout);
    }
    int TEST = 1;
    while(TEST--)
    {
        READ();
        SOLVE();
    }
    cerr << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
    return 0;
}

///    /\_/\
///   (= ._.)
///   / >  \>

Compilation message (stderr)

Main.cpp:156:1: warning: multi-line comment [-Wcomment]
  156 | ///    /\_/\
      | ^
Main.cpp: In function 'int main()':
Main.cpp:137:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  137 |         freopen("TASK.INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:138:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  138 |         freopen("TASK.OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:143:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  143 |         freopen(TASK ".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:144:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  144 |         freopen(TASK ".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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