oj.uz

Submission #153655

# Submission time Handle Problem Language Result Execution time Memory
153655 2019-09-15T05:41:50 Z semiauto Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
64 / 100
 1535 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;
    p[u][0]={par[u],val[u]};
    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=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:13: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:45: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 27768 KB Output is correct
2 Correct 31 ms 27768 KB Output is correct
3 Correct 33 ms 27740 KB Output is correct
4 Correct 32 ms 27768 KB Output is correct
5 Correct 32 ms 27768 KB Output is correct
6 Correct 33 ms 27896 KB Output is correct
7 Correct 34 ms 27896 KB Output is correct
8 Correct 33 ms 27896 KB Output is correct
9 Correct 34 ms 27896 KB Output is correct
10 Correct 34 ms 27896 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 27768 KB Output is correct
2 Correct 31 ms 27768 KB Output is correct
3 Correct 33 ms 27740 KB Output is correct
4 Correct 32 ms 27768 KB Output is correct
5 Correct 32 ms 27768 KB Output is correct
6 Correct 33 ms 27896 KB Output is correct
7 Correct 34 ms 27896 KB Output is correct
8 Correct 33 ms 27896 KB Output is correct
9 Correct 34 ms 27896 KB Output is correct
10 Correct 34 ms 27896 KB Output is correct
11 Correct 51 ms 28152 KB Output is correct
12 Correct 54 ms 29136 KB Output is correct
13 Correct 50 ms 29048 KB Output is correct
14 Correct 60 ms 29132 KB Output is correct
15 Correct 60 ms 29160 KB Output is correct
16 Correct 57 ms 29176 KB Output is correct
17 Correct 55 ms 29076 KB Output is correct
18 Correct 55 ms 29304 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 1300 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 567 ms 54288 KB Output is correct
2 Correct 541 ms 54228 KB Output is correct
3 Correct 662 ms 58872 KB Output is correct
4 Correct 645 ms 58872 KB Output is correct
5 Correct 647 ms 58996 KB Output is correct
6 Correct 559 ms 58564 KB Output is correct
7 Correct 595 ms 58488 KB Output is correct
8 Correct 565 ms 56924 KB Output is correct
9 Correct 433 ms 28152 KB Output is correct
10 Correct 572 ms 57184 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 27768 KB Output is correct
2 Correct 31 ms 27768 KB Output is correct
3 Correct 33 ms 27740 KB Output is correct
4 Correct 32 ms 27768 KB Output is correct
5 Correct 32 ms 27768 KB Output is correct
6 Correct 33 ms 27896 KB Output is correct
7 Correct 34 ms 27896 KB Output is correct
8 Correct 33 ms 27896 KB Output is correct
9 Correct 34 ms 27896 KB Output is correct
10 Correct 34 ms 27896 KB Output is correct
11 Correct 51 ms 28152 KB Output is correct
12 Correct 54 ms 29136 KB Output is correct
13 Correct 50 ms 29048 KB Output is correct
14 Correct 60 ms 29132 KB Output is correct
15 Correct 60 ms 29160 KB Output is correct
16 Correct 57 ms 29176 KB Output is correct
17 Correct 55 ms 29076 KB Output is correct
18 Correct 55 ms 29304 KB Output is correct
19 Correct 1284 ms 80868 KB Output is correct
20 Correct 1304 ms 80816 KB Output is correct
21 Correct 1257 ms 80796 KB Output is correct
22 Correct 1279 ms 81020 KB Output is correct
23 Correct 1229 ms 80808 KB Output is correct
24 Correct 1411 ms 90160 KB Output is correct
25 Correct 1424 ms 90036 KB Output is correct
26 Correct 1457 ms 90092 KB Output is correct
27 Correct 1452 ms 90132 KB Output is correct
28 Correct 1490 ms 90300 KB Output is correct
29 Correct 1473 ms 90152 KB Output is correct
30 Correct 1473 ms 90184 KB Output is correct
31 Correct 1494 ms 90128 KB Output is correct
32 Correct 1535 ms 90000 KB Output is correct
33 Correct 1495 ms 90212 KB Output is correct
34 Correct 1272 ms 90148 KB Output is correct
35 Correct 1280 ms 90084 KB Output is correct
36 Correct 1299 ms 90120 KB Output is correct
37 Correct 1258 ms 90280 KB Output is correct
38 Correct 1273 ms 90204 KB Output is correct
39 Correct 1317 ms 87012 KB Output is correct
40 Correct 1149 ms 67700 KB Output is correct
41 Correct 1246 ms 86136 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 27768 KB Output is correct
2 Correct 31 ms 27768 KB Output is correct
3 Correct 33 ms 27740 KB Output is correct
4 Correct 32 ms 27768 KB Output is correct
5 Correct 32 ms 27768 KB Output is correct
6 Correct 33 ms 27896 KB Output is correct
7 Correct 34 ms 27896 KB Output is correct
8 Correct 33 ms 27896 KB Output is correct
9 Correct 34 ms 27896 KB Output is correct
10 Correct 34 ms 27896 KB Output is correct
11 Correct 51 ms 28152 KB Output is correct
12 Correct 54 ms 29136 KB Output is correct
13 Correct 50 ms 29048 KB Output is correct
14 Correct 60 ms 29132 KB Output is correct
15 Correct 60 ms 29160 KB Output is correct
16 Correct 57 ms 29176 KB Output is correct
17 Correct 55 ms 29076 KB Output is correct
18 Correct 55 ms 29304 KB Output is correct
19 Runtime error 1300 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
20 Halted 0 ms 0 KB -