oj.uz

Submission #153693

# Submission time Handle Problem Language Result Execution time Memory
153693 2019-09-15T06:52:34 Z semiauto Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
64 / 100
 3000 ms 262144 KB 
#include <bits/stdc++.h>
using namespace std;
int n,m,i,j,l,r,ans,N=1024*1024;
int mas[1000001],val[1000001],tree[2048*1024];
pair <int,int> p[1000001][20];
vector <int> v[1000001];
void dfs(int u) {
    int i;
    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() {
    scanf("%d %d",&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;
        p[i][0].first=val[r];
        if (val[r]>(i+1))
            p[i][0].second=mas[i]+solve(i+1+N-1,val[r]-1+N-1,1,N,2*N-1);
        v[val[r]].push_back(i);
        val[++r]=i;
    }
    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);
        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:12: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:47:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<(v[0].size());i++)
              ~^~~~~~~~~~~~~~
sortbooks.cpp:33:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&n,&m);
     ~~~~~^~~~~~~~~~~~~~~
sortbooks.cpp:35:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&(mas[i]));
         ~~~~~^~~~~~~~~~~~~~~~
sortbooks.cpp:50: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 34 ms 27896 KB Output is correct
2 Correct 35 ms 28024 KB Output is correct
3 Correct 35 ms 28024 KB Output is correct
4 Correct 40 ms 28100 KB Output is correct
5 Correct 35 ms 28024 KB Output is correct
6 Correct 35 ms 28024 KB Output is correct
7 Correct 35 ms 28024 KB Output is correct
8 Correct 35 ms 28024 KB Output is correct
9 Correct 35 ms 28024 KB Output is correct
10 Correct 35 ms 28080 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 27896 KB Output is correct
2 Correct 35 ms 28024 KB Output is correct
3 Correct 35 ms 28024 KB Output is correct
4 Correct 40 ms 28100 KB Output is correct
5 Correct 35 ms 28024 KB Output is correct
6 Correct 35 ms 28024 KB Output is correct
7 Correct 35 ms 28024 KB Output is correct
8 Correct 35 ms 28024 KB Output is correct
9 Correct 35 ms 28024 KB Output is correct
10 Correct 35 ms 28080 KB Output is correct
11 Correct 37 ms 28280 KB Output is correct
12 Correct 39 ms 28856 KB Output is correct
13 Correct 40 ms 28968 KB Output is correct
14 Correct 42 ms 29048 KB Output is correct
15 Correct 42 ms 28920 KB Output is correct
16 Correct 40 ms 29176 KB Output is correct
17 Correct 39 ms 28896 KB Output is correct
18 Correct 44 ms 29048 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1913 ms 215788 KB Output is correct
2 Correct 1911 ms 210716 KB Output is correct
3 Correct 1965 ms 210732 KB Output is correct
4 Correct 1928 ms 210684 KB Output is correct
5 Execution timed out 3001 ms 262144 KB Time limit exceeded

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 47352 KB Output is correct
2 Correct 184 ms 47936 KB Output is correct
3 Correct 265 ms 53028 KB Output is correct
4 Correct 228 ms 53064 KB Output is correct
5 Correct 269 ms 53036 KB Output is correct
6 Correct 152 ms 52408 KB Output is correct
7 Correct 148 ms 52472 KB Output is correct
8 Correct 192 ms 50780 KB Output is correct
9 Correct 81 ms 29560 KB Output is correct
10 Correct 188 ms 50976 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 27896 KB Output is correct
2 Correct 35 ms 28024 KB Output is correct
3 Correct 35 ms 28024 KB Output is correct
4 Correct 40 ms 28100 KB Output is correct
5 Correct 35 ms 28024 KB Output is correct
6 Correct 35 ms 28024 KB Output is correct
7 Correct 35 ms 28024 KB Output is correct
8 Correct 35 ms 28024 KB Output is correct
9 Correct 35 ms 28024 KB Output is correct
10 Correct 35 ms 28080 KB Output is correct
11 Correct 37 ms 28280 KB Output is correct
12 Correct 39 ms 28856 KB Output is correct
13 Correct 40 ms 28968 KB Output is correct
14 Correct 42 ms 29048 KB Output is correct
15 Correct 42 ms 28920 KB Output is correct
16 Correct 40 ms 29176 KB Output is correct
17 Correct 39 ms 28896 KB Output is correct
18 Correct 44 ms 29048 KB Output is correct
19 Correct 384 ms 67004 KB Output is correct
20 Correct 383 ms 66828 KB Output is correct
21 Correct 339 ms 66680 KB Output is correct
22 Correct 339 ms 66552 KB Output is correct
23 Correct 344 ms 66680 KB Output is correct
24 Correct 412 ms 76816 KB Output is correct
25 Correct 392 ms 76664 KB Output is correct
26 Correct 532 ms 76720 KB Output is correct
27 Correct 478 ms 76856 KB Output is correct
28 Correct 496 ms 76664 KB Output is correct
29 Correct 471 ms 76740 KB Output is correct
30 Correct 467 ms 76664 KB Output is correct
31 Correct 479 ms 76664 KB Output is correct
32 Correct 496 ms 76756 KB Output is correct
33 Correct 490 ms 76824 KB Output is correct
34 Correct 304 ms 76796 KB Output is correct
35 Correct 299 ms 76680 KB Output is correct
36 Correct 316 ms 76752 KB Output is correct
37 Correct 300 ms 76772 KB Output is correct
38 Correct 301 ms 76664 KB Output is correct
39 Correct 412 ms 73316 KB Output is correct
40 Correct 291 ms 59640 KB Output is correct
41 Correct 377 ms 72872 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 27896 KB Output is correct
2 Correct 35 ms 28024 KB Output is correct
3 Correct 35 ms 28024 KB Output is correct
4 Correct 40 ms 28100 KB Output is correct
5 Correct 35 ms 28024 KB Output is correct
6 Correct 35 ms 28024 KB Output is correct
7 Correct 35 ms 28024 KB Output is correct
8 Correct 35 ms 28024 KB Output is correct
9 Correct 35 ms 28024 KB Output is correct
10 Correct 35 ms 28080 KB Output is correct
11 Correct 37 ms 28280 KB Output is correct
12 Correct 39 ms 28856 KB Output is correct
13 Correct 40 ms 28968 KB Output is correct
14 Correct 42 ms 29048 KB Output is correct
15 Correct 42 ms 28920 KB Output is correct
16 Correct 40 ms 29176 KB Output is correct
17 Correct 39 ms 28896 KB Output is correct
18 Correct 44 ms 29048 KB Output is correct
19 Correct 1913 ms 215788 KB Output is correct
20 Correct 1911 ms 210716 KB Output is correct
21 Correct 1965 ms 210732 KB Output is correct
22 Correct 1928 ms 210684 KB Output is correct
23 Execution timed out 3001 ms 262144 KB Time limit exceeded