oj.uz

Submission #482591

# Submission time Handle Problem Language Result Execution time Memory
482591 2021-10-25T17:55:32 Z Hazem Global Warming (CEOI18_glo) C++14
48 / 100
 750 ms 262148 KB 
#include <bits/stdc++.h>

#define LL long long


using namespace std;

const int N = 2e5+1;
const LL MOD = 1e9+7;

int a[N],dp[N][2],tree[N*4],b[N];
int n,k;
map<int,int>mp;
set<int>st;

void update(int v,int tl,int tr,int pos,int val){

    if(tl==tr){
        tree[v] = val;
        return ;
    }

    int mid = (tl+tr)/2;
    if(pos<=mid)update(v*2,tl,mid,pos,val);
    else update(v*2+1,mid+1,tr,pos,val);

    tree[v] = max(tree[v*2],tree[v*2+1]);
}

int get(int v,int tl,int tr,int l,int r){

    if(tl>r||tr<l)
        return 0;

    if(tl>=l&&tr<=r)
        return tree[v];

    int mid = (tl+tr)/2;
    return max(get(v*2,tl,mid,l,r),get(v*2+1,mid+1,tr,l,r));
}

void calc(){

    for(int i=1;i<=n;i++){
        dp[i][0] = get(1,1,n,1,b[i]-1)+1;
        if(get(1,1,n,b[i],b[i])<dp[i][0])update(1,1,n,b[i],dp[i][0]);
    }
    for(int i=1;i<=n;i++)
        update(1,1,n,b[i],0);

    for(int i=n;i>=1;i--){
        dp[i][1] = get(1,1,n,b[i]+1,n)+1;
        if(get(1,1,n,b[i],b[i])<dp[i][1])update(1,1,n,b[i],dp[i][1]);
    }
}

void op(int l,int r,int x){

    for(int i=l;i<=r;i++)
        a[i] += x;
}

struct Vertex {
    int left, right;
    int sum = 0;
    Vertex *left_child = nullptr, *right_child = nullptr;

    Vertex(int lb, int rb) {
        left = lb;
        right = rb;
    }

    void extend() {
        if (!left_child && left + 1 < right) {
            int t = (left + right) / 2;
            left_child = new Vertex(left, t);
            right_child = new Vertex(t, right);
        }
    }

    void add(int k, int x) {
        extend();
        sum = max(sum,x);
        if (left_child) {
            if (k < left_child->right)
                left_child->add(k, x);
            else
                right_child->add(k, x);
        }
    }

    int get_sum(int lq, int rq) {
        if (lq <= left && right <= rq)
            return sum;
        if (max(left, lq) >= min(right, rq))
            return 0;
        extend();
        return max(left_child->get_sum(lq, rq),right_child->get_sum(lq, rq));
    }
};

int main(){

    scanf("%d%d",&n,&k);

    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        st.insert(a[i]);
        }

    int cnt = 1;
    for(auto x:st)
        mp[x] = cnt++;

    for(int i=1;i<=n;i++)
        b[i] = mp[a[i]];

    calc();
    Vertex root = Vertex(0,1e9);
    int ans = 0;
    for(int i=n;i>=1;i--){
        ans = max(ans,dp[i][0]+root.get_sum(max(0,a[i]-k+1),min(a[i]+k-1,(int)1e9)));
        root.add(a[i],dp[i][1]);
    }
    Vertex root1 = Vertex(0,1e9);
    for(int i=1;i<=n;i++){
        ans = max(ans,dp[i][1]+root1.get_sum(max(0,a[i]-k+1),min(a[i]+k-1,(int)1e9)));
        root1.add(a[i],dp[i][0]);
    }

    printf("%d\n",ans);
}

Compilation message

glo.cpp: In function 'int main()':
glo.cpp:104:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  104 |     scanf("%d%d",&n,&k);
      |     ~~~~~^~~~~~~~~~~~~~
glo.cpp:107:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  107 |         scanf("%d",&a[i]);
      |         ~~~~~^~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 332 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 0 ms 332 KB Output is correct
11 Correct 0 ms 332 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 332 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 0 ms 332 KB Output is correct
11 Correct 0 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 0 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 0 ms 332 KB Output is correct
17 Correct 0 ms 332 KB Output is correct
18 Correct 1 ms 332 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 332 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 0 ms 332 KB Output is correct
11 Correct 0 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 0 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 0 ms 332 KB Output is correct
17 Correct 0 ms 332 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 12 ms 10188 KB Output is correct
20 Correct 10 ms 9036 KB Output is correct
21 Correct 9 ms 7884 KB Output is correct
22 Correct 5 ms 4172 KB Output is correct
23 Correct 5 ms 3544 KB Output is correct
24 Correct 5 ms 4172 KB Output is correct
25 Correct 2 ms 460 KB Output is correct
26 Correct 2 ms 588 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 750 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 323 ms 181700 KB Output is correct
2 Correct 315 ms 181516 KB Output is correct
3 Correct 322 ms 181572 KB Output is correct
4 Correct 157 ms 95840 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 89 ms 13284 KB Output is correct
7 Correct 228 ms 126696 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 538 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 332 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 0 ms 332 KB Output is correct
11 Correct 0 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 0 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 0 ms 332 KB Output is correct
17 Correct 0 ms 332 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 12 ms 10188 KB Output is correct
20 Correct 10 ms 9036 KB Output is correct
21 Correct 9 ms 7884 KB Output is correct
22 Correct 5 ms 4172 KB Output is correct
23 Correct 5 ms 3544 KB Output is correct
24 Correct 5 ms 4172 KB Output is correct
25 Correct 2 ms 460 KB Output is correct
26 Correct 2 ms 588 KB Output is correct
27 Runtime error 750 ms 262148 KB Execution killed with signal 9
28 Halted 0 ms 0 KB -