oj.uz

Submission #428914

# Submission time Handle Problem Language Result Execution time Memory
428914 2021-06-15T15:25:38 Z Pety Global Warming (CEOI18_glo) C++14
37 / 100
 1437 ms 262148 KB 
#include <bits/stdc++.h>
     
using namespace std;
     
     
int n, x, pref[200002], suf[200002], v[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[nod] = 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 > b)
    //return;
  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]) {
      nr++;
      mp[aux[i]] = nr;
    }
  int sol = 0;
  for (int i = 1; i <= n; i++) {
    ans = 0;
    assert(mp[v[i]]);
    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]);
    //cout << pref[i] << "\n";
  }
  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] - 1);
    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:50:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |   for (int i = 0; i < aux.size(); i++)
      |                   ~~^~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 216 KB Output is correct
8 Runtime error 153 ms 262148 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 216 KB Output is correct
8 Runtime error 153 ms 262148 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 216 KB Output is correct
8 Runtime error 153 ms 262148 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 512 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 300 ms 9880 KB Output is correct
2 Correct 227 ms 9896 KB Output is correct
3 Correct 265 ms 9824 KB Output is correct
4 Correct 106 ms 5580 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 84 ms 4540 KB Output is correct
7 Correct 194 ms 8248 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 619 ms 19500 KB Output is correct
2 Correct 658 ms 19504 KB Output is correct
3 Correct 1437 ms 38748 KB Output is correct
4 Correct 643 ms 21840 KB Output is correct
5 Correct 264 ms 19500 KB Output is correct
6 Correct 450 ms 37048 KB Output is correct
7 Correct 470 ms 37116 KB Output is correct
8 Correct 443 ms 19496 KB Output is correct

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 216 KB Output is correct
8 Runtime error 153 ms 262148 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -