oj.uz

Submission #852324

# Submission time Handle Problem Language Result Execution time Memory
852324 2023-09-21T15:20:26 Z Mularstyle Pilot (NOI19_pilot) C++14
40 / 100
 24 ms 16208 KB 
#include<bits/stdc++.h>
using namespace std;

const int mxn =1000005;
int n,q,h[mxn],a[mxn],dp[mxn],L[mxn],R[mxn];
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>q;
    for(int i=1;i<=n;i++)
        cin>>h[i];
    for(int i=1;i<=q;i++)
        cin>>a[i];
    stack<int> s;
    h[0]=h[n+1]=INT_MAX;
    s.push(0);
    for(int i=1;i<=n;i++)
    {
        while(h[s.top()]<h[i])
              s.pop();
        L[i]=s.top();
        s.push(i);
    }
    while(!s.empty())s.pop();
    s.push(n+1);
    for(int i=n;i>=1;i--)
    {
        while(h[s.top()]<=h[i])
            s.pop();
        R[i]=s.top();
        s.push(i);
    }
    for(int i=1;i<=n;i++)
        dp[h[i]]+=(i-L[i])*(R[i]-i);
    for(int i=1;i<=1000000;i++)
        dp[i]+=dp[i-1];
    for(int i=1;i<=q;i++)
        cout<<dp[a[i]]<<"\n";

}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 10584 KB Output is correct
2 Correct 4 ms 9048 KB Output is correct
3 Correct 4 ms 9048 KB Output is correct
4 Correct 3 ms 10584 KB Output is correct
5 Correct 4 ms 9048 KB Output is correct
6 Correct 3 ms 10588 KB Output is correct
7 Correct 3 ms 9048 KB Output is correct
8 Correct 4 ms 10584 KB Output is correct
9 Correct 4 ms 9048 KB Output is correct
10 Correct 4 ms 10840 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 10584 KB Output is correct
2 Correct 4 ms 9048 KB Output is correct
3 Correct 4 ms 9048 KB Output is correct
4 Correct 3 ms 10584 KB Output is correct
5 Correct 4 ms 9048 KB Output is correct
6 Correct 3 ms 10588 KB Output is correct
7 Correct 3 ms 9048 KB Output is correct
8 Correct 4 ms 10584 KB Output is correct
9 Correct 4 ms 9048 KB Output is correct
10 Correct 4 ms 10840 KB Output is correct
11 Correct 4 ms 10704 KB Output is correct
12 Correct 3 ms 10584 KB Output is correct
13 Correct 3 ms 10584 KB Output is correct
14 Correct 4 ms 10584 KB Output is correct
15 Correct 3 ms 10584 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 10584 KB Output is correct
2 Correct 4 ms 9048 KB Output is correct
3 Correct 4 ms 9048 KB Output is correct
4 Correct 3 ms 10584 KB Output is correct
5 Correct 4 ms 9048 KB Output is correct
6 Correct 3 ms 10588 KB Output is correct
7 Correct 3 ms 9048 KB Output is correct
8 Correct 4 ms 10584 KB Output is correct
9 Correct 4 ms 9048 KB Output is correct
10 Correct 4 ms 10840 KB Output is correct
11 Correct 4 ms 10704 KB Output is correct
12 Correct 3 ms 10584 KB Output is correct
13 Correct 3 ms 10584 KB Output is correct
14 Correct 4 ms 10584 KB Output is correct
15 Correct 3 ms 10584 KB Output is correct
16 Correct 4 ms 10584 KB Output is correct
17 Correct 3 ms 10720 KB Output is correct
18 Correct 4 ms 10584 KB Output is correct
19 Correct 4 ms 10584 KB Output is correct
20 Correct 3 ms 10584 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 10584 KB Output is correct
2 Correct 4 ms 9048 KB Output is correct
3 Correct 4 ms 9048 KB Output is correct
4 Correct 3 ms 10584 KB Output is correct
5 Correct 4 ms 9048 KB Output is correct
6 Correct 3 ms 10588 KB Output is correct
7 Correct 3 ms 9048 KB Output is correct
8 Correct 4 ms 10584 KB Output is correct
9 Correct 4 ms 9048 KB Output is correct
10 Correct 4 ms 10840 KB Output is correct
11 Correct 4 ms 10704 KB Output is correct
12 Correct 3 ms 10584 KB Output is correct
13 Correct 3 ms 10584 KB Output is correct
14 Correct 4 ms 10584 KB Output is correct
15 Correct 3 ms 10584 KB Output is correct
16 Correct 4 ms 10584 KB Output is correct
17 Correct 3 ms 10720 KB Output is correct
18 Correct 4 ms 10584 KB Output is correct
19 Correct 4 ms 10584 KB Output is correct
20 Correct 3 ms 10584 KB Output is correct
21 Correct 4 ms 10584 KB Output is correct
22 Correct 4 ms 10584 KB Output is correct
23 Correct 4 ms 10584 KB Output is correct
24 Correct 4 ms 10584 KB Output is correct
25 Correct 4 ms 10584 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 14936 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 14168 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 24 ms 16208 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 10584 KB Output is correct
2 Correct 4 ms 9048 KB Output is correct
3 Correct 4 ms 9048 KB Output is correct
4 Correct 3 ms 10584 KB Output is correct
5 Correct 4 ms 9048 KB Output is correct
6 Correct 3 ms 10588 KB Output is correct
7 Correct 3 ms 9048 KB Output is correct
8 Correct 4 ms 10584 KB Output is correct
9 Correct 4 ms 9048 KB Output is correct
10 Correct 4 ms 10840 KB Output is correct
11 Incorrect 11 ms 14936 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #9
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 10584 KB Output is correct
2 Correct 4 ms 9048 KB Output is correct
3 Correct 4 ms 9048 KB Output is correct
4 Correct 3 ms 10584 KB Output is correct
5 Correct 4 ms 9048 KB Output is correct
6 Correct 3 ms 10588 KB Output is correct
7 Correct 3 ms 9048 KB Output is correct
8 Correct 4 ms 10584 KB Output is correct
9 Correct 4 ms 9048 KB Output is correct
10 Correct 4 ms 10840 KB Output is correct
11 Correct 4 ms 10704 KB Output is correct
12 Correct 3 ms 10584 KB Output is correct
13 Correct 3 ms 10584 KB Output is correct
14 Correct 4 ms 10584 KB Output is correct
15 Correct 3 ms 10584 KB Output is correct
16 Correct 4 ms 10584 KB Output is correct
17 Correct 3 ms 10720 KB Output is correct
18 Correct 4 ms 10584 KB Output is correct
19 Correct 4 ms 10584 KB Output is correct
20 Correct 3 ms 10584 KB Output is correct
21 Correct 4 ms 10584 KB Output is correct
22 Correct 4 ms 10584 KB Output is correct
23 Correct 4 ms 10584 KB Output is correct
24 Correct 4 ms 10584 KB Output is correct
25 Correct 4 ms 10584 KB Output is correct
26 Incorrect 11 ms 14936 KB Output isn't correct
27 Halted 0 ms 0 KB -

Subtask #10
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 10584 KB Output is correct
2 Correct 4 ms 9048 KB Output is correct
3 Correct 4 ms 9048 KB Output is correct
4 Correct 3 ms 10584 KB Output is correct
5 Correct 4 ms 9048 KB Output is correct
6 Correct 3 ms 10588 KB Output is correct
7 Correct 3 ms 9048 KB Output is correct
8 Correct 4 ms 10584 KB Output is correct
9 Correct 4 ms 9048 KB Output is correct
10 Correct 4 ms 10840 KB Output is correct
11 Correct 4 ms 10704 KB Output is correct
12 Correct 3 ms 10584 KB Output is correct
13 Correct 3 ms 10584 KB Output is correct
14 Correct 4 ms 10584 KB Output is correct
15 Correct 3 ms 10584 KB Output is correct
16 Correct 4 ms 10584 KB Output is correct
17 Correct 3 ms 10720 KB Output is correct
18 Correct 4 ms 10584 KB Output is correct
19 Correct 4 ms 10584 KB Output is correct
20 Correct 3 ms 10584 KB Output is correct
21 Correct 4 ms 10584 KB Output is correct
22 Correct 4 ms 10584 KB Output is correct
23 Correct 4 ms 10584 KB Output is correct
24 Correct 4 ms 10584 KB Output is correct
25 Correct 4 ms 10584 KB Output is correct
26 Incorrect 11 ms 14936 KB Output isn't correct
27 Halted 0 ms 0 KB -