oj.uz

Submission #153620

# Submission time Handle Problem Language Result Execution time Memory
153620 2019-09-15T04:49:07 Z semiauto Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
64 / 100
 1640 ms 262148 KB 
#include <bits/stdc++.h>
using namespace std;
int n,m,i,j,l,r,ans;
int mas[2000001],par[2000001],val[2000001],ori[2000001],hey[5000001],pre[2000001][22];
pair <int,int> p[2000001][22];
vector <int> v[2000001];
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=1;i<=n;i++)
        cout<<val[i]<<" ";
    cout<<endl;*/
    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:48: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 52 ms 51192 KB Output is correct
2 Correct 52 ms 51320 KB Output is correct
3 Correct 55 ms 51320 KB Output is correct
4 Correct 54 ms 51320 KB Output is correct
5 Correct 54 ms 51320 KB Output is correct
6 Correct 56 ms 51448 KB Output is correct
7 Correct 56 ms 51452 KB Output is correct
8 Correct 55 ms 51448 KB Output is correct
9 Correct 56 ms 51320 KB Output is correct
10 Correct 55 ms 51448 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 51192 KB Output is correct
2 Correct 52 ms 51320 KB Output is correct
3 Correct 55 ms 51320 KB Output is correct
4 Correct 54 ms 51320 KB Output is correct
5 Correct 54 ms 51320 KB Output is correct
6 Correct 56 ms 51448 KB Output is correct
7 Correct 56 ms 51452 KB Output is correct
8 Correct 55 ms 51448 KB Output is correct
9 Correct 56 ms 51320 KB Output is correct
10 Correct 55 ms 51448 KB Output is correct
11 Correct 67 ms 51788 KB Output is correct
12 Correct 71 ms 52728 KB Output is correct
13 Correct 72 ms 52860 KB Output is correct
14 Correct 81 ms 52856 KB Output is correct
15 Correct 84 ms 52984 KB Output is correct
16 Correct 79 ms 52968 KB Output is correct
17 Correct 77 ms 52728 KB Output is correct
18 Correct 77 ms 52988 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 1310 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 587 ms 82208 KB Output is correct
2 Correct 585 ms 82140 KB Output is correct
3 Correct 673 ms 86648 KB Output is correct
4 Correct 694 ms 86744 KB Output is correct
5 Correct 682 ms 87044 KB Output is correct
6 Correct 605 ms 86312 KB Output is correct
7 Correct 591 ms 86300 KB Output is correct
8 Correct 596 ms 84412 KB Output is correct
9 Correct 453 ms 52964 KB Output is correct
10 Correct 606 ms 84608 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 51192 KB Output is correct
2 Correct 52 ms 51320 KB Output is correct
3 Correct 55 ms 51320 KB Output is correct
4 Correct 54 ms 51320 KB Output is correct
5 Correct 54 ms 51320 KB Output is correct
6 Correct 56 ms 51448 KB Output is correct
7 Correct 56 ms 51452 KB Output is correct
8 Correct 55 ms 51448 KB Output is correct
9 Correct 56 ms 51320 KB Output is correct
10 Correct 55 ms 51448 KB Output is correct
11 Correct 67 ms 51788 KB Output is correct
12 Correct 71 ms 52728 KB Output is correct
13 Correct 72 ms 52860 KB Output is correct
14 Correct 81 ms 52856 KB Output is correct
15 Correct 84 ms 52984 KB Output is correct
16 Correct 79 ms 52968 KB Output is correct
17 Correct 77 ms 52728 KB Output is correct
18 Correct 77 ms 52988 KB Output is correct
19 Correct 1321 ms 111228 KB Output is correct
20 Correct 1331 ms 111312 KB Output is correct
21 Correct 1262 ms 111296 KB Output is correct
22 Correct 1289 ms 111464 KB Output is correct
23 Correct 1261 ms 111508 KB Output is correct
24 Correct 1469 ms 120700 KB Output is correct
25 Correct 1466 ms 120740 KB Output is correct
26 Correct 1640 ms 120608 KB Output is correct
27 Correct 1536 ms 120712 KB Output is correct
28 Correct 1566 ms 120948 KB Output is correct
29 Correct 1509 ms 121008 KB Output is correct
30 Correct 1526 ms 120992 KB Output is correct
31 Correct 1531 ms 121068 KB Output is correct
32 Correct 1557 ms 121016 KB Output is correct
33 Correct 1509 ms 121036 KB Output is correct
34 Correct 1327 ms 121076 KB Output is correct
35 Correct 1300 ms 120844 KB Output is correct
36 Correct 1300 ms 120996 KB Output is correct
37 Correct 1278 ms 120868 KB Output is correct
38 Correct 1362 ms 120948 KB Output is correct
39 Correct 1356 ms 117880 KB Output is correct
40 Correct 1179 ms 96892 KB Output is correct
41 Correct 1267 ms 116924 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 51192 KB Output is correct
2 Correct 52 ms 51320 KB Output is correct
3 Correct 55 ms 51320 KB Output is correct
4 Correct 54 ms 51320 KB Output is correct
5 Correct 54 ms 51320 KB Output is correct
6 Correct 56 ms 51448 KB Output is correct
7 Correct 56 ms 51452 KB Output is correct
8 Correct 55 ms 51448 KB Output is correct
9 Correct 56 ms 51320 KB Output is correct
10 Correct 55 ms 51448 KB Output is correct
11 Correct 67 ms 51788 KB Output is correct
12 Correct 71 ms 52728 KB Output is correct
13 Correct 72 ms 52860 KB Output is correct
14 Correct 81 ms 52856 KB Output is correct
15 Correct 84 ms 52984 KB Output is correct
16 Correct 79 ms 52968 KB Output is correct
17 Correct 77 ms 52728 KB Output is correct
18 Correct 77 ms 52988 KB Output is correct
19 Runtime error 1310 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
20 Halted 0 ms 0 KB -