oj.uz

Submission #153681

# Submission time Handle Problem Language Result Execution time Memory
153681 2019-09-15T06:19:01 Z semiauto Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
64 / 100
 2097 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],hey[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;hey[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[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+N-1,par[i]-1+N-1,1,N,2*N-1);
    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;hey[i]=0;}
                   ^~~
sortbooks.cpp:52:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<(v[0].size());i++)
              ~^~~~~~~~~~~~~~
sortbooks.cpp:39:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&(mas[i]));
         ~~~~~^~~~~~~~~~~~~~~~
sortbooks.cpp:55: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 183 ms 200164 KB Output is correct
2 Correct 184 ms 200080 KB Output is correct
3 Correct 213 ms 200064 KB Output is correct
4 Correct 192 ms 200060 KB Output is correct
5 Correct 203 ms 200056 KB Output is correct
6 Correct 184 ms 200184 KB Output is correct
7 Correct 186 ms 200192 KB Output is correct
8 Correct 184 ms 200312 KB Output is correct
9 Correct 184 ms 200148 KB Output is correct
10 Correct 196 ms 200140 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 200164 KB Output is correct
2 Correct 184 ms 200080 KB Output is correct
3 Correct 213 ms 200064 KB Output is correct
4 Correct 192 ms 200060 KB Output is correct
5 Correct 203 ms 200056 KB Output is correct
6 Correct 184 ms 200184 KB Output is correct
7 Correct 186 ms 200192 KB Output is correct
8 Correct 184 ms 200312 KB Output is correct
9 Correct 184 ms 200148 KB Output is correct
10 Correct 196 ms 200140 KB Output is correct
11 Correct 193 ms 200188 KB Output is correct
12 Correct 188 ms 200336 KB Output is correct
13 Correct 189 ms 200364 KB Output is correct
14 Correct 192 ms 200256 KB Output is correct
15 Correct 191 ms 200184 KB Output is correct
16 Correct 187 ms 200440 KB Output is correct
17 Correct 188 ms 200440 KB Output is correct
18 Correct 190 ms 200528 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2097 ms 222328 KB Output is correct
2 Correct 2036 ms 222316 KB Output is correct
3 Correct 2005 ms 222228 KB Output is correct
4 Correct 1996 ms 222412 KB Output is correct
5 Runtime error 778 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 327 ms 202360 KB Output is correct
2 Correct 317 ms 202360 KB Output is correct
3 Correct 359 ms 207116 KB Output is correct
4 Correct 357 ms 206960 KB Output is correct
5 Correct 392 ms 206988 KB Output is correct
6 Correct 295 ms 206660 KB Output is correct
7 Correct 308 ms 206712 KB Output is correct
8 Correct 330 ms 205176 KB Output is correct
9 Correct 232 ms 200320 KB Output is correct
10 Correct 326 ms 205432 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 200164 KB Output is correct
2 Correct 184 ms 200080 KB Output is correct
3 Correct 213 ms 200064 KB Output is correct
4 Correct 192 ms 200060 KB Output is correct
5 Correct 203 ms 200056 KB Output is correct
6 Correct 184 ms 200184 KB Output is correct
7 Correct 186 ms 200192 KB Output is correct
8 Correct 184 ms 200312 KB Output is correct
9 Correct 184 ms 200148 KB Output is correct
10 Correct 196 ms 200140 KB Output is correct
11 Correct 193 ms 200188 KB Output is correct
12 Correct 188 ms 200336 KB Output is correct
13 Correct 189 ms 200364 KB Output is correct
14 Correct 192 ms 200256 KB Output is correct
15 Correct 191 ms 200184 KB Output is correct
16 Correct 187 ms 200440 KB Output is correct
17 Correct 188 ms 200440 KB Output is correct
18 Correct 190 ms 200528 KB Output is correct
19 Correct 513 ms 204680 KB Output is correct
20 Correct 535 ms 204500 KB Output is correct
21 Correct 477 ms 204668 KB Output is correct
22 Correct 463 ms 204660 KB Output is correct
23 Correct 462 ms 204536 KB Output is correct
24 Correct 506 ms 213880 KB Output is correct
25 Correct 508 ms 213980 KB Output is correct
26 Correct 572 ms 213944 KB Output is correct
27 Correct 627 ms 213912 KB Output is correct
28 Correct 623 ms 213884 KB Output is correct
29 Correct 678 ms 214088 KB Output is correct
30 Correct 605 ms 213872 KB Output is correct
31 Correct 614 ms 213848 KB Output is correct
32 Correct 722 ms 213868 KB Output is correct
33 Correct 618 ms 213944 KB Output is correct
34 Correct 425 ms 213932 KB Output is correct
35 Correct 420 ms 213872 KB Output is correct
36 Correct 420 ms 213880 KB Output is correct
37 Correct 428 ms 214008 KB Output is correct
38 Correct 449 ms 213880 KB Output is correct
39 Correct 545 ms 210808 KB Output is correct
40 Correct 432 ms 208376 KB Output is correct
41 Correct 498 ms 210608 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 200164 KB Output is correct
2 Correct 184 ms 200080 KB Output is correct
3 Correct 213 ms 200064 KB Output is correct
4 Correct 192 ms 200060 KB Output is correct
5 Correct 203 ms 200056 KB Output is correct
6 Correct 184 ms 200184 KB Output is correct
7 Correct 186 ms 200192 KB Output is correct
8 Correct 184 ms 200312 KB Output is correct
9 Correct 184 ms 200148 KB Output is correct
10 Correct 196 ms 200140 KB Output is correct
11 Correct 193 ms 200188 KB Output is correct
12 Correct 188 ms 200336 KB Output is correct
13 Correct 189 ms 200364 KB Output is correct
14 Correct 192 ms 200256 KB Output is correct
15 Correct 191 ms 200184 KB Output is correct
16 Correct 187 ms 200440 KB Output is correct
17 Correct 188 ms 200440 KB Output is correct
18 Correct 190 ms 200528 KB Output is correct
19 Correct 2097 ms 222328 KB Output is correct
20 Correct 2036 ms 222316 KB Output is correct
21 Correct 2005 ms 222228 KB Output is correct
22 Correct 1996 ms 222412 KB Output is correct
23 Runtime error 778 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)