oj.uz

Submission #1008379

# Submission time Handle Problem Language Result Execution time Memory
1008379 2024-06-26T10:14:19 Z pudelos Global Warming (CEOI18_glo) C++17
27 / 100
 504 ms 38340 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define FOR(i, a, b) for(int i=a; i<=b; ++i)
#define ll long long
#define eb emplace_back
#define V vector
const int base=(1<<20);
int n, X;
V<int> A;
map<int, int> ch;

struct SegTree {
  int T[2*base];
  void update(int v, int x) {
    v+=base;
    T[v]=max(T[v], x);
    v/=2;
    while(v>0) {
      T[v]=max(T[2*v], T[2*v+1]);
      v/=2;
    }
  }
  int query(int a, int b) {
    int res=0;
    a+=base-1;
    b+=base+1;
    while(a/2!=b/2) {
      if(a%2==0) res=max(res, T[a+1]);
      if(b%2==1) res=max(res, T[b-1]);
      a/=2; b/=2;
    }
    return res;
  }
} AT, BT;

signed main() {
  cin.tie(0) -> ios_base::sync_with_stdio(0);
  cin >> n >> X;
  A.resize(n+1);
  V<int> all;
  FOR(i, 1, n) {
    cin >> A[i];
    all.eb(A[i]);
    all.eb(A[i]+X);
  }
  sort(all.begin(), all.end());
  int t=0;
  for(int u : all) {
    if(ch[u]==0) ch[u]=++t;
  }
  
  FOR(i, 1, n) {
    int x = A[i];
    AT.update(ch[x], AT.query(0, ch[x]-1)+1);
    BT.update(ch[x], BT.query(0, ch[x]-1)+1);
    BT.update(ch[x], AT.query(0, ch[x+X]-1)+1);
  }

  cout << max(AT.T[1], BT.T[1]) << '\n';
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 13.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 374 ms 25900 KB Output is correct
2 Correct 380 ms 25792 KB Output is correct
3 Correct 428 ms 25824 KB Output is correct
4 Correct 382 ms 25792 KB Output is correct
5 Correct 186 ms 15664 KB Output is correct

Subtask #5
0 / 20.0

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

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 224 ms 19540 KB Output is correct
2 Correct 250 ms 19400 KB Output is correct
3 Correct 504 ms 38340 KB Output is correct
4 Correct 231 ms 22064 KB Output is correct
5 Correct 146 ms 19184 KB Output is correct
6 Correct 294 ms 35776 KB Output is correct
7 Correct 282 ms 36476 KB Output is correct
8 Correct 177 ms 19392 KB Output is correct

Subtask #7
0 / 25.0

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