oj.uz

Submission #762824

# Submission time Handle Problem Language Result Execution time Memory
762824 2023-06-21T20:10:02 Z HoriaHaivas Pilot (NOI19_pilot) C++14
55 / 100
 1000 ms 15424 KB 
/*
    "TLE is like the wind, always by my side"
    - Yasuo - 2022 -
*/
#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast")
#define int long long

using namespace std;

int rmq[20][1000001];
int v[1000001];

int query (int l, int r)
{
    int logi;
    logi=log2(r-l+1);
    return max(rmq[logi][l],rmq[logi][r-(1<<logi)+1]);
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n,q,i,j,r,pas,ans,value;
    cin >> n >> q;
    for (i=1;i<=n;i++)
    {
         cin >> v[i];
         rmq[0][i]=v[i];
    }
    for (i=1;i<=19;i++)
    {
         for (j=1;j+(1<<i)-1<=n;j++)
         {
              rmq[i][j]=max(rmq[i-1][j],rmq[i-1][j+(1<<(i-1))]);
         }
    }
    for (i=1;i<=q;i++)
    {
         cin >> value;
         ans=0;
         for (j=1;j<=n;j++)
         {
             if (value>=v[j])
             {
                r=j;
                pas=(1<<19);
                while (pas)
                {
                    if (r+pas<=n && query(j,r+pas)<=value)
                        r+=pas;
                    pas=pas/2;
                }
                if (i==1)
                {
                    debugs(j);
                    debug(r);
                }
                ans+=r-j+1;
             }
         }
         cout << ans << "\n";
    }
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 328 KB Output is correct
15 Correct 1 ms 340 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 328 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 4 ms 328 KB Output is correct
17 Correct 4 ms 340 KB Output is correct
18 Correct 5 ms 340 KB Output is correct
19 Correct 4 ms 328 KB Output is correct
20 Correct 6 ms 324 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 328 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 4 ms 328 KB Output is correct
17 Correct 4 ms 340 KB Output is correct
18 Correct 5 ms 340 KB Output is correct
19 Correct 4 ms 328 KB Output is correct
20 Correct 6 ms 324 KB Output is correct
21 Correct 119 ms 468 KB Output is correct
22 Correct 114 ms 492 KB Output is correct
23 Correct 139 ms 468 KB Output is correct
24 Correct 115 ms 476 KB Output is correct
25 Correct 121 ms 480 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 788 ms 15120 KB Output is correct
2 Correct 841 ms 15424 KB Output is correct
3 Correct 754 ms 14612 KB Output is correct
4 Correct 740 ms 14064 KB Output is correct
5 Correct 728 ms 14428 KB Output is correct

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1055 ms 14752 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1064 ms 13648 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 788 ms 15120 KB Output is correct
12 Correct 841 ms 15424 KB Output is correct
13 Correct 754 ms 14612 KB Output is correct
14 Correct 740 ms 14064 KB Output is correct
15 Correct 728 ms 14428 KB Output is correct
16 Correct 540 ms 13916 KB Output is correct
17 Correct 325 ms 14408 KB Output is correct
18 Correct 105 ms 14336 KB Output is correct
19 Correct 80 ms 12876 KB Output is correct
20 Correct 408 ms 14256 KB Output is correct
21 Correct 739 ms 14216 KB Output is correct
22 Correct 404 ms 13768 KB Output is correct
23 Correct 240 ms 14460 KB Output is correct
24 Correct 151 ms 13132 KB Output is correct
25 Correct 406 ms 14212 KB Output is correct

Subtask #9
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 328 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 4 ms 328 KB Output is correct
17 Correct 4 ms 340 KB Output is correct
18 Correct 5 ms 340 KB Output is correct
19 Correct 4 ms 328 KB Output is correct
20 Correct 6 ms 324 KB Output is correct
21 Correct 119 ms 468 KB Output is correct
22 Correct 114 ms 492 KB Output is correct
23 Correct 139 ms 468 KB Output is correct
24 Correct 115 ms 476 KB Output is correct
25 Correct 121 ms 480 KB Output is correct
26 Correct 788 ms 15120 KB Output is correct
27 Correct 841 ms 15424 KB Output is correct
28 Correct 754 ms 14612 KB Output is correct
29 Correct 740 ms 14064 KB Output is correct
30 Correct 728 ms 14428 KB Output is correct
31 Execution timed out 1055 ms 14752 KB Time limit exceeded
32 Halted 0 ms 0 KB -

Subtask #10
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 328 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 4 ms 328 KB Output is correct
17 Correct 4 ms 340 KB Output is correct
18 Correct 5 ms 340 KB Output is correct
19 Correct 4 ms 328 KB Output is correct
20 Correct 6 ms 324 KB Output is correct
21 Correct 119 ms 468 KB Output is correct
22 Correct 114 ms 492 KB Output is correct
23 Correct 139 ms 468 KB Output is correct
24 Correct 115 ms 476 KB Output is correct
25 Correct 121 ms 480 KB Output is correct
26 Correct 788 ms 15120 KB Output is correct
27 Correct 841 ms 15424 KB Output is correct
28 Correct 754 ms 14612 KB Output is correct
29 Correct 740 ms 14064 KB Output is correct
30 Correct 728 ms 14428 KB Output is correct
31 Execution timed out 1055 ms 14752 KB Time limit exceeded
32 Halted 0 ms 0 KB -