oj.uz

Submission #153684

# Submission time Handle Problem Language Result Execution time Memory
153684 2019-09-15T06:24:38 Z semiauto Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
64 / 100
 2041 ms 262148 KB 
#include <bits/stdc++.h>
using namespace std;
int n,m,i,j,l,r,ans,N=1024*1024;
int mas[1000001],par[1000001],val[1000001],tree[2048*1024];
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 x,int y,int p,int l,int r) {
    if (l>y || x>r)
        return 0;
    if (l>=x && r<=y)
        return tree[p];
    return max(solve(x,y,2*p,l,(l+r)/2),solve(x,y,2*p+1,(l+r)/2+1,r));
}
void build_tree(int p) {
    if (p>=N) {
        if ((p-N+1)<=n)
            tree[p]=mas[p-N+1];
        return;
    }
    build_tree(2*p);
    build_tree(2*p+1);
    tree[p]=max(tree[2*p],tree[2*p+1]);
}
int main() {
    for (i=0;i<=1000000;i++)
        {for (j=0;j<=19;j++)
    p[i][j]={0,0};mas[i]=0;par[i]=0;val[i]=0;v[i].clear();}
    for (i=0;i<(2048*1024);i++)tree[i]=0;
    cin>>n>>m;
    for (i=1;i<=n;i++)
        scanf("%d",&(mas[i]));
    build_tree(1);
    for (i=n;i>0;i--) {
        for (;r>0;r--)
            if (mas[val[r]]>=mas[i])
                break;
        par[i]=val[r];
        v[val[r]].push_back(i);
        val[++r]=i;
    }
    for (i=1;i<=n;i++) {
        if (par[i]>(i+1))
            val[i]=mas[i]+solve(i+1+N-1,par[i]-1+N-1,1,N,2*N-1);
        else
            val[i]=0;
    }
    for (i=0;i<(v[0].size());i++)
        dfs(v[0][i]);
    for (mas[0]=1;mas[0]<=m;mas[0]++) {
        scanf("%d %d %d",&l,&r,&j);
        if (l==r) {
            printf("1\n");
            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+N-1,r+N-1,1,N,2*N-1));
        if (ans>j)
            printf("0\n");
        else
            printf("1\n");
    }
}

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:35:10: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
         {for (j=0;j<=19;j++)
          ^~~
sortbooks.cpp:36:19: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
     p[i][j]={0,0};mas[i]=0;par[i]=0;val[i]=0;v[i].clear();}
                   ^~~
sortbooks.cpp:56:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<(v[0].size());i++)
              ~^~~~~~~~~~~~~~
sortbooks.cpp:40:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&(mas[i]));
         ~~~~~^~~~~~~~~~~~~~~~
sortbooks.cpp:59:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d",&l,&r,&j);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 200440 KB Output is correct
2 Correct 184 ms 200312 KB Output is correct
3 Correct 201 ms 200312 KB Output is correct
4 Correct 186 ms 200236 KB Output is correct
5 Correct 185 ms 200436 KB Output is correct
6 Correct 184 ms 200272 KB Output is correct
7 Correct 185 ms 200440 KB Output is correct
8 Correct 184 ms 200372 KB Output is correct
9 Correct 185 ms 200356 KB Output is correct
10 Correct 186 ms 200312 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 200440 KB Output is correct
2 Correct 184 ms 200312 KB Output is correct
3 Correct 201 ms 200312 KB Output is correct
4 Correct 186 ms 200236 KB Output is correct
5 Correct 185 ms 200436 KB Output is correct
6 Correct 184 ms 200272 KB Output is correct
7 Correct 185 ms 200440 KB Output is correct
8 Correct 184 ms 200372 KB Output is correct
9 Correct 185 ms 200356 KB Output is correct
10 Correct 186 ms 200312 KB Output is correct
11 Correct 189 ms 200312 KB Output is correct
12 Correct 201 ms 200440 KB Output is correct
13 Correct 193 ms 200528 KB Output is correct
14 Correct 191 ms 200332 KB Output is correct
15 Correct 190 ms 200460 KB Output is correct
16 Correct 190 ms 200512 KB Output is correct
17 Correct 189 ms 200540 KB Output is correct
18 Correct 190 ms 200568 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2008 ms 218792 KB Output is correct
2 Correct 2021 ms 218672 KB Output is correct
3 Correct 2041 ms 218500 KB Output is correct
4 Correct 2007 ms 218684 KB Output is correct
5 Runtime error 838 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 328 ms 202136 KB Output is correct
2 Correct 309 ms 202216 KB Output is correct
3 Correct 356 ms 206840 KB Output is correct
4 Correct 348 ms 206748 KB Output is correct
5 Correct 352 ms 206960 KB Output is correct
6 Correct 289 ms 206488 KB Output is correct
7 Correct 284 ms 206532 KB Output is correct
8 Correct 319 ms 205176 KB Output is correct
9 Correct 231 ms 200568 KB Output is correct
10 Correct 321 ms 205268 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 200440 KB Output is correct
2 Correct 184 ms 200312 KB Output is correct
3 Correct 201 ms 200312 KB Output is correct
4 Correct 186 ms 200236 KB Output is correct
5 Correct 185 ms 200436 KB Output is correct
6 Correct 184 ms 200272 KB Output is correct
7 Correct 185 ms 200440 KB Output is correct
8 Correct 184 ms 200372 KB Output is correct
9 Correct 185 ms 200356 KB Output is correct
10 Correct 186 ms 200312 KB Output is correct
11 Correct 189 ms 200312 KB Output is correct
12 Correct 201 ms 200440 KB Output is correct
13 Correct 193 ms 200528 KB Output is correct
14 Correct 191 ms 200332 KB Output is correct
15 Correct 190 ms 200460 KB Output is correct
16 Correct 190 ms 200512 KB Output is correct
17 Correct 189 ms 200540 KB Output is correct
18 Correct 190 ms 200568 KB Output is correct
19 Correct 541 ms 204056 KB Output is correct
20 Correct 548 ms 203980 KB Output is correct
21 Correct 470 ms 203904 KB Output is correct
22 Correct 475 ms 203896 KB Output is correct
23 Correct 477 ms 203896 KB Output is correct
24 Correct 536 ms 213256 KB Output is correct
25 Correct 531 ms 213332 KB Output is correct
26 Correct 626 ms 213324 KB Output is correct
27 Correct 575 ms 213384 KB Output is correct
28 Correct 682 ms 213416 KB Output is correct
29 Correct 682 ms 213336 KB Output is correct
30 Correct 614 ms 213348 KB Output is correct
31 Correct 624 ms 213368 KB Output is correct
32 Correct 621 ms 213240 KB Output is correct
33 Correct 613 ms 213304 KB Output is correct
34 Correct 436 ms 213240 KB Output is correct
35 Correct 434 ms 213368 KB Output is correct
36 Correct 439 ms 213240 KB Output is correct
37 Correct 426 ms 213240 KB Output is correct
38 Correct 465 ms 213192 KB Output is correct
39 Correct 566 ms 210228 KB Output is correct
40 Correct 465 ms 207880 KB Output is correct
41 Correct 505 ms 209700 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 200440 KB Output is correct
2 Correct 184 ms 200312 KB Output is correct
3 Correct 201 ms 200312 KB Output is correct
4 Correct 186 ms 200236 KB Output is correct
5 Correct 185 ms 200436 KB Output is correct
6 Correct 184 ms 200272 KB Output is correct
7 Correct 185 ms 200440 KB Output is correct
8 Correct 184 ms 200372 KB Output is correct
9 Correct 185 ms 200356 KB Output is correct
10 Correct 186 ms 200312 KB Output is correct
11 Correct 189 ms 200312 KB Output is correct
12 Correct 201 ms 200440 KB Output is correct
13 Correct 193 ms 200528 KB Output is correct
14 Correct 191 ms 200332 KB Output is correct
15 Correct 190 ms 200460 KB Output is correct
16 Correct 190 ms 200512 KB Output is correct
17 Correct 189 ms 200540 KB Output is correct
18 Correct 190 ms 200568 KB Output is correct
19 Correct 2008 ms 218792 KB Output is correct
20 Correct 2021 ms 218672 KB Output is correct
21 Correct 2041 ms 218500 KB Output is correct
22 Correct 2007 ms 218684 KB Output is correct
23 Runtime error 838 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)