oj.uz

Submission #153685

# Submission time Handle Problem Language Result Execution time Memory
153685 2019-09-15T06:25:59 Z semiauto Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
64 / 100
 2054 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() {
    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:52:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<(v[0].size());i++)
              ~^~~~~~~~~~~~~~
sortbooks.cpp:36: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 35 ms 27968 KB Output is correct
2 Correct 34 ms 28024 KB Output is correct
3 Correct 35 ms 28028 KB Output is correct
4 Correct 35 ms 27896 KB Output is correct
5 Correct 35 ms 28024 KB Output is correct
6 Correct 35 ms 28152 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 28004 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 27968 KB Output is correct
2 Correct 34 ms 28024 KB Output is correct
3 Correct 35 ms 28028 KB Output is correct
4 Correct 35 ms 27896 KB Output is correct
5 Correct 35 ms 28024 KB Output is correct
6 Correct 35 ms 28152 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 28004 KB Output is correct
11 Correct 37 ms 28156 KB Output is correct
12 Correct 39 ms 28920 KB Output is correct
13 Correct 40 ms 28920 KB Output is correct
14 Correct 49 ms 28920 KB Output is correct
15 Correct 47 ms 28868 KB Output is correct
16 Correct 39 ms 29048 KB Output is correct
17 Correct 45 ms 28920 KB Output is correct
18 Correct 47 ms 29064 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2024 ms 218412 KB Output is correct
2 Correct 2054 ms 218376 KB Output is correct
3 Correct 2051 ms 218388 KB Output is correct
4 Correct 1985 ms 218456 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 193 ms 47024 KB Output is correct
2 Correct 178 ms 46968 KB Output is correct
3 Correct 221 ms 51580 KB Output is correct
4 Correct 250 ms 51888 KB Output is correct
5 Correct 214 ms 51704 KB Output is correct
6 Correct 156 ms 51320 KB Output is correct
7 Correct 151 ms 51292 KB Output is correct
8 Correct 188 ms 49912 KB Output is correct
9 Correct 81 ms 28280 KB Output is correct
10 Correct 210 ms 50104 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 27968 KB Output is correct
2 Correct 34 ms 28024 KB Output is correct
3 Correct 35 ms 28028 KB Output is correct
4 Correct 35 ms 27896 KB Output is correct
5 Correct 35 ms 28024 KB Output is correct
6 Correct 35 ms 28152 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 28004 KB Output is correct
11 Correct 37 ms 28156 KB Output is correct
12 Correct 39 ms 28920 KB Output is correct
13 Correct 40 ms 28920 KB Output is correct
14 Correct 49 ms 28920 KB Output is correct
15 Correct 47 ms 28868 KB Output is correct
16 Correct 39 ms 29048 KB Output is correct
17 Correct 45 ms 28920 KB Output is correct
18 Correct 47 ms 29064 KB Output is correct
19 Correct 420 ms 66172 KB Output is correct
20 Correct 455 ms 66080 KB Output is correct
21 Correct 340 ms 66080 KB Output is correct
22 Correct 341 ms 66168 KB Output is correct
23 Correct 364 ms 66236 KB Output is correct
24 Correct 402 ms 75384 KB Output is correct
25 Correct 394 ms 75324 KB Output is correct
26 Correct 479 ms 75512 KB Output is correct
27 Correct 495 ms 75376 KB Output is correct
28 Correct 589 ms 75396 KB Output is correct
29 Correct 532 ms 75408 KB Output is correct
30 Correct 598 ms 75384 KB Output is correct
31 Correct 517 ms 75384 KB Output is correct
32 Correct 498 ms 75356 KB Output is correct
33 Correct 554 ms 75460 KB Output is correct
34 Correct 307 ms 75328 KB Output is correct
35 Correct 301 ms 75256 KB Output is correct
36 Correct 322 ms 75292 KB Output is correct
37 Correct 302 ms 75408 KB Output is correct
38 Correct 309 ms 75276 KB Output is correct
39 Correct 510 ms 72372 KB Output is correct
40 Correct 298 ms 58168 KB Output is correct
41 Correct 380 ms 71804 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 27968 KB Output is correct
2 Correct 34 ms 28024 KB Output is correct
3 Correct 35 ms 28028 KB Output is correct
4 Correct 35 ms 27896 KB Output is correct
5 Correct 35 ms 28024 KB Output is correct
6 Correct 35 ms 28152 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 28004 KB Output is correct
11 Correct 37 ms 28156 KB Output is correct
12 Correct 39 ms 28920 KB Output is correct
13 Correct 40 ms 28920 KB Output is correct
14 Correct 49 ms 28920 KB Output is correct
15 Correct 47 ms 28868 KB Output is correct
16 Correct 39 ms 29048 KB Output is correct
17 Correct 45 ms 28920 KB Output is correct
18 Correct 47 ms 29064 KB Output is correct
19 Correct 2024 ms 218412 KB Output is correct
20 Correct 2054 ms 218376 KB Output is correct
21 Correct 2051 ms 218388 KB Output is correct
22 Correct 1985 ms 218456 KB Output is correct
23 Runtime error 838 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)