Submission #892278

#	Time	Username	Problem	Language	Result	Execution time	Memory
892278		fucfan	Financial Report (JOI21_financial)	C++14	5 / 100	227 ms	16676 KiB

Main

#include<bits/stdc++.h>
#define fi first
#define se second
#define ull unsigned long long
#define ll long long
#define BIT(a , b) ((a >> b) & 1)
#define flip(a , b) ((a) ^ (1 << (b)))
#define pii pair<int, int>
#define pb push_back
#define nl cout << "\n";
#define __ <<" "<<
#define mem(a, b) memset((a), (b), sizeof((a)))
#define all(c) (c).begin(), (c).end()
#define add(x , y) ((x) + (y) >= mod ? ((x) + (y) - mod) : ((x) + (y)))
#define file "test"
#define Times cerr << "\nTime run: " << clock() / 1000.0 << " ms\n";
using namespace std;

const ll oo = 1e18 + 7;
const int mod = 1e9 + 7;
const int N = 3e5 + 5;
const int LOG = 20;
const int base = 31;

void run_with_file(){
    if(fopen(file".inp" , "r")){
         freopen(file".inp", "r" , stdin);
         freopen(file".out", "w" , stdout);
    }
}

int n , d , a[N];
vector <int> compress;
int dp[N];

struct segment_tree{
    pii node[N << 2 | 1];

    void update(int id , int l , int r , int pos , pii val){
        if(l > pos || pos > r) return;

        if(l == r){
            node[id] = val;
//            cout << l << ' ' << r << ' ' << val.fi << ' ' << val.se << '\n';
            return;
        }

        int mid = (l + r) >> 1;

        update(id << 1 , l , mid , pos , val);
        update(id << 1 | 1 , mid + 1 , r , pos , val);

        node[id] = max(node[id << 1] , node[id << 1 | 1]);
    }

    int get(int id , int l , int r , int u , int v){
        if(l > v || u > r) return 0;

        if(u <= l && r <= v) return node[id].fi;

        int mid = (l + r) >> 1;

        return max(get(id << 1 , l , mid , u , v) ,
                   get(id << 1 | 1 , mid + 1 , r , u , v));
    }

    int get_pos(int id , int l , int r , int pos){
        if(pos > r || l > pos) return 0;

        if(l == r) return node[id].se;

        int mid = (l + r) >> 1;

        return max(get_pos(id << 1 , l , mid , pos) ,
                   get_pos(id << 1 | 1 , mid + 1 , r , pos));
    }
} ST;

void inp(){
    cin >> n >> d;

    for(int i = 1 ; i <= n ; i++){
        cin >> a[i];
        compress.pb(a[i]);
    }
}

int main(){
    cin.tie(0)->sync_with_stdio(false);
    run_with_file();
    inp();

    sort(all(compress));
    compress.erase(unique(all(compress)) , compress.end());

    int pre = 1;
    int ans = 0;

    for(int i = 1 ; i <= n ; i++){
        if(i - pre > d){
            int tmp = lower_bound(all(compress) , a[pre]) - compress.begin() + 1;
            if(ST.get_pos(1 , 1 , n , tmp) == pre){
                ST.update(1 , 1 , n , tmp , {0 , 0});
            }
            pre++;
        }

        int pos = lower_bound(all(compress) , a[i]) - compress.begin() + 1;
        dp[i] = max(ST.get(1 , 1 , n , pos , pos) , ST.get(1 , 1 , n , 1 , pos - 1) + 1);

        ST.update(1 , 1 , n , pos , {dp[i] , i});
        ans = max(ans , dp[i]);

//        for(int j = 1 ; j <= n ; j++)
//            cout << ST.get(1 , 1 , n , j , j) << '/' << ST.get_pos(1 , 1 , n , j) << ' ';
//        nl;

//        cout << dp[i] << ' ';
    }
//    nl;

    cout << ans;
}

/*      UwU      */

Compilation message (stderr)

Main.cpp: In function 'void run_with_file()':
Main.cpp:27:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |          freopen(file".inp", "r" , stdin);
      |          ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:28:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |          freopen(file".out", "w" , stdout);
      |          ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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