oj.uz

Submission #430628

# Submission time Handle Problem Language Result Execution time Memory
430628 2021-06-16T17:34:34 Z Runtime_error_ Global Warming (CEOI18_glo) C++14
0 / 100
 1546 ms 39020 KB 
//
//#include <bits/stdc++.h>
//#define pi pair<int,int>
//#define pb push_back
//using namespace std;
//const int inf = 1e5+9;
//int n,sz[inf],ans;
//vector<int> adj[inf];
//set<pi> *lis[inf],*lds[inf];
//
//int querylis(int u,int x){
//    if(lis[u]->empty() || lis[u]->begin()->first > x)
//        return 1;
//    set<pi> ::iterator it = lis[u]->lower_bound(pi(x,0));
//    it--;
//    return it->second+1;
//}
//
//void insertlis(int u,pi x){
//    if(lis[u]->empty())
//        return void(lis[u]->insert(x));
//    set<pi> ::iterator it;
//    if(!lis[u]->empty()){
//         it = lis[u]->lower_bound(pi(x.first+1,0));
//        if(it != lis[u]->begin() && (--it)->second >= x.second)
//            return ;
//    }
//
//    it = lis[u]->lower_bound(pi(x.first,0));
//    if(it != lis[u]->end() && it->first == x.first && it->second <= x.second)
//        it = lis[u]->erase(it);
//
//    while(it != lis[u]->end() && it->second <= x.second)
//        it = lis[u]->erase(it);
//    lis[u]->insert(x);
//}
//
//int querylds(int u,int x){
//    if(lds[u]->empty() || lds[u]->rbegin()->first < x)
//        return 1;
//    set<pi> ::iterator it = lds[u]->lower_bound(pi(x,0));
//
//    return  it->second + 1;
//}
//
//void insertlds(int u,pi x){
//    if(lds[u]->empty())
//        return void(lds[u]->insert(x));
//    set<pi> ::iterator it;
//
//    if(!lds[u]->empty()){
//         it = lds[u]->lower_bound(pi(x.first,0));
//        if(it != lds[u]->end() && it->second >= x.second)
//            return ;
//    }
//
//    it = lds[u]->lower_bound(pi(x.first,0));
//    if(it != lds[u]->end() && it->first == x.first && it->second <= x.second)
//        it = lds[u]->erase(it);
//
//    while(it != lds[u]->begin() && (--it)->second <= x.second)
//        it = lds[u]->erase(it);
//    lds[u]->insert(x);
//}
//
//void dfs(int u,int p){
//    int curans = 0;
//    sz[u] = 1;
//    int mx = 0,heavy = -1;
//    for(auto v:adj[u]){
//        if(v == p)
//            continue;
//        dfs(v,u);
//        sz[u] += sz[v];
//        if(sz[v] > mx)
//            mx = sz[v],heavy = v;
//    }
//
//    if(heavy == -1)
//        lis[u] = new set<pi> (),
//        lds[u] = new set<pi> ();
//    else
//        lis[u] = lis[heavy],
//        lds[u] = lds[heavy];
//
//    insertlis(u,pi(u,querylis(u,u)));
//    insertlds(u,pi(u,querylds(u,u)));
//    //light lis with (heavy lds + previous light lds)
//    for(auto v:adj[u]){
//        if(v == p || v == heavy)continue;
//        for(auto o:*lis[v])
//            curans = max(curans,o.second + querylds(u,o.first)-1);
//        for(auto o:*lds[v])
//            insertlds(u,o);
//        insertlds(u,pi(u, querylds(v,u) ));
//    }
//    //light lds with (heavy lis + previous light lis)
//    for(auto v:adj[u]){
//        if(v == p || v == heavy)
//            continue;
//        for(auto o:*lds[v])
//            curans = max(curans,o.second + querylis(u,o.first)-1);
//
//        for(auto o:*lis[v])
//            insertlis(u,pi(u,querylis(v,u)));
//        insertlis(u,pi(u, querylis(v,u) ));
//
//    }
//    curans = max(curans,lis[u]->rbegin()->second);
//    curans = max(curans,lds[u]->begin()->second);
//    ans = max(ans,curans);
//}
//
//void TestCases(){
//    scanf("%d",&n);
//    ans = 0;
//    for(int i=1;i<=n;i++){
//        adj[i].clear();
//        lis[i] = new set<pi> ();
//        lds[i] = new set<pi> ();
////        if(lis[i]!=NULL)
////            delete lis[i];
////        if(lds[i] != NULL)
////            delete lds[i];
//    }
//    for(int i=1;i<n;++i){
//        int a,b;
//        scanf("%d%d",&a,&b);
//        adj[a].pb(b);
//        adj[b].pb(a);
//    }
//    dfs(1,0);
//    printf("%d\n",ans);
//}
//
//int main(){
//
//    int t;
//    scanf("%d",&t);
//    while(t--)
//        TestCases();
//}
///*
//1
//3
//1 2
//1 3
//
//*/

#include <bits/stdc++.h>
#define ll long long
#define le node+node
#define ri node+node+1
#define mid (l+r)/2
using namespace std;
const int inf = 4e5+9;
int n,k,a[inf],cnt,id[inf],tree[inf<<2],lis[inf],lds[inf];
map<int,int> mp;

void update(int node,int l,int r,int idx,int val){
    if(l == r)
        return void(tree[node] = max(tree[node],val));
    if(idx <= mid)
        update(le,l,mid,idx,val);
    else
        update(ri,mid+1,r,idx,val);
    tree[node] = max(tree[le],tree[ri]);
}

int query(int node,int l,int r,int x,int y){
    if(x>y || y<l || x>r || l>r)
        return 0;
    if(l>=x && r<=y)
        return tree[node];
    return max(query(le,l,mid,x,y),query(ri,mid+1,r,x,y));
}


int main(){

    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
        scanf("%d",a+i),mp[a[i]],mp[a[i]+k-1];

    for(auto &o:mp)
        o.second = ++cnt;

    for(int i=1;i<=n;i++){
        lis[i]  = 1 + query(1,1,cnt,1,mp[a[i]]-1);
        update(1,1,cnt,mp[a[i]],lis[i]);
        //cout<<lis[i]<<" ";
    }
    memset(tree,0,sizeof(tree));

    for(int i=n;i>=1;i--){
        lds[i] = 1 + query(1,1,cnt,mp[a[i]]+1,cnt);
        update(1,1,cnt,mp[a[i]],lds[i]);
    }
    int ans = 0;
    memset(tree,0,sizeof(tree));
    for(int i=n;i>=1;i--)
        ans = max(ans,lis[i] + query(1,1,cnt,mp[a[i]-k+1],mp[a[i]])),update(1,1,n,mp[a[i]],lds[i]);

    cout<<ans<<endl;
}

Compilation message

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

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6476 KB Output is correct
2 Correct 5 ms 6588 KB Output is correct
3 Correct 5 ms 6476 KB Output is correct
4 Incorrect 4 ms 6476 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6476 KB Output is correct
2 Correct 5 ms 6588 KB Output is correct
3 Correct 5 ms 6476 KB Output is correct
4 Incorrect 4 ms 6476 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6476 KB Output is correct
2 Correct 5 ms 6588 KB Output is correct
3 Correct 5 ms 6476 KB Output is correct
4 Incorrect 4 ms 6476 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1444 ms 38964 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 194 ms 14656 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 558 ms 22764 KB Output is correct
2 Correct 648 ms 22784 KB Output is correct
3 Correct 1546 ms 39020 KB Output is correct
4 Correct 484 ms 24068 KB Output is correct
5 Correct 295 ms 22364 KB Output is correct
6 Correct 583 ms 36652 KB Output is correct
7 Correct 550 ms 37324 KB Output is correct
8 Incorrect 398 ms 22760 KB Output isn't correct

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6476 KB Output is correct
2 Correct 5 ms 6588 KB Output is correct
3 Correct 5 ms 6476 KB Output is correct
4 Incorrect 4 ms 6476 KB Output isn't correct
5 Halted 0 ms 0 KB -