oj.uz

Submission #153644

# Submission time Handle Problem Language Result Execution time Memory
153644 2019-09-15T05:26:50 Z semiauto Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
64 / 100
 1523 ms 262148 KB 
#include <bits/stdc++.h>
using namespace std;
int n,m,i,j,l,r,ans;
int mas[1000001],par[1000001],val[1000001],ori[1000001],hey[3000001],pre[1000001][20];
pair <int,int> p[1000001][20];
vector <int> v[1000001];
void dfs(int u) {
    int i;
    for (i=1;i<20;i++)
        if (p[p[u][i-1].first][i-1].first)
            p[u][i]={p[p[u][i-1].first][i-1].first,max(p[u][i-1].second,p[p[u][i-1].first][i-1].second)};
    for (i=0;i<(v[u].size());i++)
        dfs(v[u][i]);
}
int solve(int a,int b) {
    int c=ori[b-a+1];
    return max(pre[a][c],pre[b-(1<<c)+1][c]);
}
int main() {
    for (i=1;i<20;i++)
        ori[(1<<i)]=i;
    for (i=1;i<1000001;i++)
        if (!ori[i])
            ori[i]=ori[i-1];
    cin>>n>>m;
    for (i=1;i<=n;i++) {
        cin>>mas[i];
        pre[i][0]=mas[i];
    }
    for (j=1;j<20;j++)
        for (i=1;(i+(1<<j)-1)<=n;i++)
            pre[i][j]=max(pre[i][j-1],pre[i+(1<<(j-1))][j-1]);
    for (i=n;i>0;i--) {
        for (;r>0;r--)
            if (mas[hey[r]]>=mas[i])
                break;
        par[i]=hey[r];
        v[hey[r]].push_back(i);
        hey[++r]=i;
    }
    for (i=1;i<=n;i++)
        if (par[i]>(i+1))
            val[i]=mas[i]+solve(i+1,par[i]-1);
    for (i=1;i<=n;i++)
        p[i][0]={par[i],val[i]};
    for (i=0;i<(v[0].size());i++)
        dfs(v[0][i]);
    while (cin>>l>>r>>m) {
        if (l==r) {
            cout<<"1"<<endl;
            continue;
        }
        ans=0;
        for (i=19;i>=0;i--)
            if (p[l][i].first && p[l][i].first<=r) {
                ans=max(ans,p[l][i].second);
                l=p[l][i].first;
            }
        if (r>l)
            ans=max(ans,mas[l]+solve(l+1,r));
        if (ans>m)
            cout<<"0"<<endl;
        else
            cout<<"1"<<endl;
    }
}

Compilation message

sortbooks.cpp: In function 'void dfs(int)':
sortbooks.cpp:12:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<(v[u].size());i++)
              ~^~~~~~~~~~~~~~
sortbooks.cpp: In function 'int main()':
sortbooks.cpp:46:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<(v[0].size());i++)
              ~^~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 27896 KB Output is correct
2 Correct 31 ms 27772 KB Output is correct
3 Correct 33 ms 27768 KB Output is correct
4 Correct 39 ms 27768 KB Output is correct
5 Correct 31 ms 27896 KB Output is correct
6 Correct 34 ms 27896 KB Output is correct
7 Correct 36 ms 28024 KB Output is correct
8 Correct 39 ms 27896 KB Output is correct
9 Correct 36 ms 27896 KB Output is correct
10 Correct 33 ms 27896 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 27896 KB Output is correct
2 Correct 31 ms 27772 KB Output is correct
3 Correct 33 ms 27768 KB Output is correct
4 Correct 39 ms 27768 KB Output is correct
5 Correct 31 ms 27896 KB Output is correct
6 Correct 34 ms 27896 KB Output is correct
7 Correct 36 ms 28024 KB Output is correct
8 Correct 39 ms 27896 KB Output is correct
9 Correct 36 ms 27896 KB Output is correct
10 Correct 33 ms 27896 KB Output is correct
11 Correct 46 ms 28256 KB Output is correct
12 Correct 48 ms 29196 KB Output is correct
13 Correct 51 ms 29232 KB Output is correct
14 Correct 59 ms 29304 KB Output is correct
15 Correct 59 ms 29304 KB Output is correct
16 Correct 56 ms 29304 KB Output is correct
17 Correct 56 ms 29048 KB Output is correct
18 Correct 63 ms 29304 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 1234 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 560 ms 55672 KB Output is correct
2 Correct 544 ms 56220 KB Output is correct
3 Correct 650 ms 60856 KB Output is correct
4 Correct 651 ms 61020 KB Output is correct
5 Correct 644 ms 61020 KB Output is correct
6 Correct 559 ms 60492 KB Output is correct
7 Correct 567 ms 60428 KB Output is correct
8 Correct 582 ms 58768 KB Output is correct
9 Correct 430 ms 29424 KB Output is correct
10 Correct 569 ms 59052 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 27896 KB Output is correct
2 Correct 31 ms 27772 KB Output is correct
3 Correct 33 ms 27768 KB Output is correct
4 Correct 39 ms 27768 KB Output is correct
5 Correct 31 ms 27896 KB Output is correct
6 Correct 34 ms 27896 KB Output is correct
7 Correct 36 ms 28024 KB Output is correct
8 Correct 39 ms 27896 KB Output is correct
9 Correct 36 ms 27896 KB Output is correct
10 Correct 33 ms 27896 KB Output is correct
11 Correct 46 ms 28256 KB Output is correct
12 Correct 48 ms 29196 KB Output is correct
13 Correct 51 ms 29232 KB Output is correct
14 Correct 59 ms 29304 KB Output is correct
15 Correct 59 ms 29304 KB Output is correct
16 Correct 56 ms 29304 KB Output is correct
17 Correct 56 ms 29048 KB Output is correct
18 Correct 63 ms 29304 KB Output is correct
19 Correct 1301 ms 87348 KB Output is correct
20 Correct 1309 ms 87388 KB Output is correct
21 Correct 1235 ms 87272 KB Output is correct
22 Correct 1235 ms 87228 KB Output is correct
23 Correct 1240 ms 87276 KB Output is correct
24 Correct 1377 ms 96504 KB Output is correct
25 Correct 1411 ms 96352 KB Output is correct
26 Correct 1455 ms 96624 KB Output is correct
27 Correct 1452 ms 96736 KB Output is correct
28 Correct 1473 ms 96488 KB Output is correct
29 Correct 1498 ms 96616 KB Output is correct
30 Correct 1495 ms 96644 KB Output is correct
31 Correct 1457 ms 96552 KB Output is correct
32 Correct 1474 ms 96736 KB Output is correct
33 Correct 1523 ms 96672 KB Output is correct
34 Correct 1287 ms 96252 KB Output is correct
35 Correct 1336 ms 96304 KB Output is correct
36 Correct 1245 ms 96024 KB Output is correct
37 Correct 1261 ms 96180 KB Output is correct
38 Correct 1277 ms 96456 KB Output is correct
39 Correct 1326 ms 92128 KB Output is correct
40 Correct 1161 ms 72144 KB Output is correct
41 Correct 1251 ms 90840 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 27896 KB Output is correct
2 Correct 31 ms 27772 KB Output is correct
3 Correct 33 ms 27768 KB Output is correct
4 Correct 39 ms 27768 KB Output is correct
5 Correct 31 ms 27896 KB Output is correct
6 Correct 34 ms 27896 KB Output is correct
7 Correct 36 ms 28024 KB Output is correct
8 Correct 39 ms 27896 KB Output is correct
9 Correct 36 ms 27896 KB Output is correct
10 Correct 33 ms 27896 KB Output is correct
11 Correct 46 ms 28256 KB Output is correct
12 Correct 48 ms 29196 KB Output is correct
13 Correct 51 ms 29232 KB Output is correct
14 Correct 59 ms 29304 KB Output is correct
15 Correct 59 ms 29304 KB Output is correct
16 Correct 56 ms 29304 KB Output is correct
17 Correct 56 ms 29048 KB Output is correct
18 Correct 63 ms 29304 KB Output is correct
19 Runtime error 1234 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
20 Halted 0 ms 0 KB -