oj.uz

Submission #393924

# Submission time Handle Problem Language Result Execution time Memory
393924 2021-04-24T23:30:51 Z tostes Global Warming (CEOI18_glo) C++17
0 / 100
 2000 ms 17860 KB 
#include<bits/stdc++.h>
//#include<iostream>
//#include<vector>
using namespace std;
#define _ << ' ' <<
#define pb push_back
#define all(x) begin(x), end(x)
#define mp make_pair
#define f first
#define s second
#define sz(x) int((x).size())
using ll = long long;
using db = long double;
using pl = pair<ll,ll>;
using pi = pair<int,int>;

void trad(vector<ll>a, ll x){
  int n=a.size();
  set < pl > lis;
  vector < int > tr(n,1);
  for(int i=n-1; i>=0; i--){
    auto p = lis.upper_bound({a[i],0});
    if(p!=lis.end()){
      tr[i]+=p->s;
    }
    lis.insert({a[i],tr[i]});
    auto pp = lis.find({a[i],tr[i]});
    if(pp!=lis.end() and (next(pp)->s == tr[i])) lis.erase(pp);
    if(pp!=lis.begin() and (prev(pp)->s == tr[i])) lis.erase(prev(pp));
  }

  ll ans = tr[0];
  set < pl > Lis;

  for(int i=0; i<n-1; i++){
    auto p = Lis.upper_bound({a[i]-x,0});
    if(p!=Lis.end()){
      if(p->f > a[i]-x){
        Lis.insert({a[i]-x, p->s});
        Lis.erase(p);
      }
    }
    else Lis.insert({a[i]-x, Lis.size()+1});

    auto w = Lis.lower_bound({a[i+1],0});
    int ct=Lis.size();
    if(w!=Lis.end()) ct = (w->s)-1;
    ans = max(ans, (ll)ct + tr[i+1]);
  }

  cout << ans << endl;
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  //freopen("nocross.in", "r", stdin);
  //freopen("nocross.out", "w", stdout);
  int n; ll x;
  cin >> n >> x;
  vector < ll > a(n);
  for(auto &w: a) cin >> w;
  trad(a,x);
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2079 ms 204 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2079 ms 204 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2079 ms 204 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 6228 KB Output is correct
2 Correct 130 ms 6236 KB Output is correct
3 Correct 122 ms 6224 KB Output is correct
4 Correct 120 ms 6220 KB Output is correct
5 Incorrect 153 ms 17840 KB Output isn't correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 1740 KB Output is correct
2 Correct 32 ms 1824 KB Output is correct
3 Correct 28 ms 1840 KB Output is correct
4 Execution timed out 2075 ms 1484 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 3276 KB Output is correct
2 Correct 53 ms 3280 KB Output is correct
3 Correct 111 ms 6224 KB Output is correct
4 Correct 173 ms 17860 KB Output is correct
5 Correct 87 ms 9108 KB Output is correct
6 Execution timed out 2090 ms 5188 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2079 ms 204 KB Time limit exceeded
2 Halted 0 ms 0 KB -