oj.uz

Submission #892278

# Submission time Handle Problem Language Result Execution time Memory
892278 2023-12-25T06:36:18 Z fucfan Financial Report (JOI21_financial) C++14
5 / 100
 227 ms 16676 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2512 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 0 ms 2516 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 0 ms 2392 KB Output is correct
13 Correct 0 ms 2392 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Incorrect 1 ms 2512 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2512 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 0 ms 2516 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 0 ms 2392 KB Output is correct
13 Correct 0 ms 2392 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Incorrect 1 ms 2512 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2512 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 0 ms 2516 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 0 ms 2392 KB Output is correct
13 Correct 0 ms 2392 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Incorrect 1 ms 2512 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 10184 KB Output is correct
2 Incorrect 129 ms 7624 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 10196 KB Output is correct
2 Correct 107 ms 7880 KB Output is correct
3 Correct 157 ms 8084 KB Output is correct
4 Correct 227 ms 16096 KB Output is correct
5 Correct 188 ms 16120 KB Output is correct
6 Correct 221 ms 16072 KB Output is correct
7 Correct 119 ms 16080 KB Output is correct
8 Correct 121 ms 16072 KB Output is correct
9 Correct 137 ms 16676 KB Output is correct
10 Correct 182 ms 16212 KB Output is correct
11 Correct 207 ms 16068 KB Output is correct
12 Correct 186 ms 16324 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2512 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 0 ms 2516 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 0 ms 2392 KB Output is correct
13 Correct 0 ms 2392 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Incorrect 1 ms 2512 KB Output isn't correct
16 Halted 0 ms 0 KB -