oj.uz

Submission #846835

# Submission time Handle Problem Language Result Execution time Memory
846835 2023-09-08T13:57:13 Z Abito Financial Report (JOI21_financial) C++17
12 / 100
 58 ms 12624 KB 
#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define ppb pop_back
#define ep insert
#define endl '\n'
#define elif else if
#define pow pwr
#define sqrt sqrtt
#define int long long
#define y1 YONE
typedef unsigned long long ull;
using namespace std;
const int N=3e5+5;
int a[N],n,d,bit[N],lis[N],b[N];
void edit(int x){
    while (x<=n){
        bit[x]++;
        x+=x&-x;
    }return;
}int query(int x){
    int y=0;
    while (x){
        y+=bit[x];
        x-=x&-x;
    }return y;
}
int32_t main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    cin>>n>>d;
    for (int i=1;i<=n;i++) cin>>a[i];
    if (d==1){
        stack<int> s;
        for (int i=1;i<=n;i++){
            while (!s.empty()){
                if (a[s.top()]<a[i]) s.pop();
                else{
                    b[i]=s.top();
                    break;
                }
            }s.push(i);
        }
        int ans=0;
        for (int i=n;i;i--){
            edit(b[i]+1);
            ans=max(ans,query(i));
        }cout<<ans<<endl;
        return 0;
    }
    if (d==n){
        stack<int> s;
        for (int i=1;i<=n;i++){
            while (!s.empty()){
                if (a[s.top()]>=a[i]) s.pop();
                else{
                    b[i]=s.top();
                    break;
                }
            }s.push(i);
        }int ans=0;
        for (int i=1;i<=n;i++) lis[i]=lis[b[i]]+1,ans=max(ans,lis[i]);
        cout<<ans<<endl;
        return 0;
    }
    return 0;
}

Subtask #1
0 / 14.0

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

Subtask #2
0 / 14.0

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

Subtask #3
0 / 20.0

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

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 11864 KB Output is correct
2 Correct 33 ms 9552 KB Output is correct
3 Correct 39 ms 9296 KB Output is correct
4 Correct 35 ms 9296 KB Output is correct
5 Correct 38 ms 9676 KB Output is correct
6 Correct 35 ms 9296 KB Output is correct
7 Correct 58 ms 5456 KB Output is correct
8 Correct 30 ms 11852 KB Output is correct
9 Correct 50 ms 9684 KB Output is correct
10 Correct 33 ms 10424 KB Output is correct
11 Correct 35 ms 9808 KB Output is correct
12 Correct 34 ms 9296 KB Output is correct
13 Correct 30 ms 9048 KB Output is correct
14 Correct 32 ms 9808 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 7248 KB Output is correct
2 Incorrect 27 ms 12624 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

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