oj.uz

Submission #153683

# Submission time Handle Problem Language Result Execution time Memory
153683 2019-09-15T06:21:44 Z semiauto Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
64 / 100
 2050 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;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[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;v[i].clear();}
                   ^~~
sortbooks.cpp:53: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:56: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 188 ms 204284 KB Output is correct
2 Correct 190 ms 204176 KB Output is correct
3 Correct 188 ms 204188 KB Output is correct
4 Correct 222 ms 204268 KB Output is correct
5 Correct 189 ms 204152 KB Output is correct
6 Correct 204 ms 204280 KB Output is correct
7 Correct 198 ms 204316 KB Output is correct
8 Correct 212 ms 204200 KB Output is correct
9 Correct 189 ms 204212 KB Output is correct
10 Correct 191 ms 204280 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 204284 KB Output is correct
2 Correct 190 ms 204176 KB Output is correct
3 Correct 188 ms 204188 KB Output is correct
4 Correct 222 ms 204268 KB Output is correct
5 Correct 189 ms 204152 KB Output is correct
6 Correct 204 ms 204280 KB Output is correct
7 Correct 198 ms 204316 KB Output is correct
8 Correct 212 ms 204200 KB Output is correct
9 Correct 189 ms 204212 KB Output is correct
10 Correct 191 ms 204280 KB Output is correct
11 Correct 191 ms 204240 KB Output is correct
12 Correct 194 ms 204280 KB Output is correct
13 Correct 196 ms 204280 KB Output is correct
14 Correct 202 ms 204336 KB Output is correct
15 Correct 196 ms 204360 KB Output is correct
16 Correct 196 ms 204408 KB Output is correct
17 Correct 192 ms 204380 KB Output is correct
18 Correct 195 ms 204412 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2009 ms 222652 KB Output is correct
2 Correct 2001 ms 222460 KB Output is correct
3 Correct 2050 ms 222544 KB Output is correct
4 Correct 2015 ms 222596 KB Output is correct
5 Runtime error 783 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 334 ms 206072 KB Output is correct
2 Correct 333 ms 206012 KB Output is correct
3 Correct 377 ms 210680 KB Output is correct
4 Correct 412 ms 210864 KB Output is correct
5 Correct 352 ms 210808 KB Output is correct
6 Correct 294 ms 210296 KB Output is correct
7 Correct 292 ms 210296 KB Output is correct
8 Correct 321 ms 208936 KB Output is correct
9 Correct 234 ms 204568 KB Output is correct
10 Correct 327 ms 209128 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 204284 KB Output is correct
2 Correct 190 ms 204176 KB Output is correct
3 Correct 188 ms 204188 KB Output is correct
4 Correct 222 ms 204268 KB Output is correct
5 Correct 189 ms 204152 KB Output is correct
6 Correct 204 ms 204280 KB Output is correct
7 Correct 198 ms 204316 KB Output is correct
8 Correct 212 ms 204200 KB Output is correct
9 Correct 189 ms 204212 KB Output is correct
10 Correct 191 ms 204280 KB Output is correct
11 Correct 191 ms 204240 KB Output is correct
12 Correct 194 ms 204280 KB Output is correct
13 Correct 196 ms 204280 KB Output is correct
14 Correct 202 ms 204336 KB Output is correct
15 Correct 196 ms 204360 KB Output is correct
16 Correct 196 ms 204408 KB Output is correct
17 Correct 192 ms 204380 KB Output is correct
18 Correct 195 ms 204412 KB Output is correct
19 Correct 535 ms 207856 KB Output is correct
20 Correct 555 ms 208120 KB Output is correct
21 Correct 465 ms 207864 KB Output is correct
22 Correct 476 ms 207984 KB Output is correct
23 Correct 483 ms 207912 KB Output is correct
24 Correct 564 ms 217300 KB Output is correct
25 Correct 530 ms 217100 KB Output is correct
26 Correct 573 ms 217208 KB Output is correct
27 Correct 563 ms 217336 KB Output is correct
28 Correct 629 ms 217260 KB Output is correct
29 Correct 623 ms 217148 KB Output is correct
30 Correct 705 ms 217172 KB Output is correct
31 Correct 622 ms 217332 KB Output is correct
32 Correct 624 ms 217184 KB Output is correct
33 Correct 619 ms 217208 KB Output is correct
34 Correct 469 ms 217280 KB Output is correct
35 Correct 458 ms 217220 KB Output is correct
36 Correct 463 ms 217144 KB Output is correct
37 Correct 428 ms 217176 KB Output is correct
38 Correct 426 ms 217208 KB Output is correct
39 Correct 538 ms 214232 KB Output is correct
40 Correct 432 ms 211832 KB Output is correct
41 Correct 545 ms 213596 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 204284 KB Output is correct
2 Correct 190 ms 204176 KB Output is correct
3 Correct 188 ms 204188 KB Output is correct
4 Correct 222 ms 204268 KB Output is correct
5 Correct 189 ms 204152 KB Output is correct
6 Correct 204 ms 204280 KB Output is correct
7 Correct 198 ms 204316 KB Output is correct
8 Correct 212 ms 204200 KB Output is correct
9 Correct 189 ms 204212 KB Output is correct
10 Correct 191 ms 204280 KB Output is correct
11 Correct 191 ms 204240 KB Output is correct
12 Correct 194 ms 204280 KB Output is correct
13 Correct 196 ms 204280 KB Output is correct
14 Correct 202 ms 204336 KB Output is correct
15 Correct 196 ms 204360 KB Output is correct
16 Correct 196 ms 204408 KB Output is correct
17 Correct 192 ms 204380 KB Output is correct
18 Correct 195 ms 204412 KB Output is correct
19 Correct 2009 ms 222652 KB Output is correct
20 Correct 2001 ms 222460 KB Output is correct
21 Correct 2050 ms 222544 KB Output is correct
22 Correct 2015 ms 222596 KB Output is correct
23 Runtime error 783 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)