oj.uz

Submission #427574

# Submission time Handle Problem Language Result Execution time Memory
427574 2021-06-14T17:22:51 Z Pety Global Warming (CEOI18_glo) C++14
0 / 100
 615 ms 262148 KB 
#include <bits/stdc++.h>

using namespace std;


int n, x, pref[200002], suf[200002], v[200002], norm[200002];
vector<int>aux;
int aint[4 * 3 * 200000 + 2];
unordered_map<int, int>mp;
void update (int nod, int st, int dr, int poz, int val) {
  if (st == dr) {
    aint[poz] = val;
    return;
  }
  int mij = (st + dr) / 2;
  if (poz <= mij)
    update(2 * nod, st, mij, poz, val);
  else
    update(2 * nod + 1, mij + 1, dr, poz, val);
  aint[nod] = max(aint[2 * nod], aint[2 * nod + 1]);
}

int ans = 0;

void query (int nod, int st, int dr, int a, int b) {
  if (a <= st && dr <= b) {
    ans = max(ans, aint[nod]);
    return;
  }
  int mij = (st + dr) / 2;
  if (a <= mij)
    query(2 * nod, st, mij, a, b);
  if (b > mij)
    query(2 * nod + 1, mij + 1, dr, a, b);
}

  int nr = 0;


void reset () {
  for (int i = 1; i <= 4*nr; i++)
    aint[i] = 0;
}


int main()
{
  cin >> n >> x;
  for (int i = 1; i <= n; i++) {
    cin >> v[i];
    aux.push_back(v[i] + x);
    aux.push_back(v[i] - x);
    aux.push_back(v[i]);
  }
  sort(aux.begin(), aux.end());
  for (int i = 0; i < aux.size(); i++)
    if (i == 0 || aux[i] != aux[i - 1]) {
      aux[nr++] = aux[i];
      mp[aux[nr - 1]] = nr;
    }
  int sol = 0;
  for (int i = 1; i <= n; i++) {
    ans = 0;
    query(1, 1, nr, 1, mp[v[i]] - 1);
    pref[i] = ans + 1;
    update(1, 1, nr, mp[v[i]], pref[i]);
    sol = max(ans, pref[i]);
  }
  reset();
  for (int i = n; i >= 1; i--) {
    ans = 0;
    query(1, 1, nr, mp[v[i]] + 1, nr);
    suf[i] = ans + 1;
    update(1, 1, nr, mp[v[i]], suf[i]);
  }
  reset();
  for (int i = 1; i <= n; i++) {
    ans = 0;
    query(1, 1, nr, 1, mp[v[i] + x]);
    sol = max(suf[i] + ans, sol);
    update(1, 1, nr, mp[v[i]], pref[i]);
  }
  reset();
  for (int i = n; i >= 1; i--) {
    ans = 0;
    query(1, 1, nr, mp[v[i] - x] + 1, nr);
    sol = max(sol, ans + pref[i]);
    update(1, 1, nr, mp[v[i]], suf[i]);
  }
  cout << sol << "\n";
  return 0;
}

Compilation message

glo.cpp: In function 'int main()':
glo.cpp:56:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |   for (int i = 0; i < aux.size(); i++)
      |                   ~~^~~~~~~~~~~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 13.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 20.0

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

Subtask #6
0 / 17.0

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

Subtask #7
0 / 25.0

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