제출 #428911

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
428911		Pety	Global Warming (CEOI18_glo)	C++14	100 / 100	1582 ms	40792 KiB

glo

#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;
}

컴파일 시 표준 에러 (stderr) 메시지

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: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 13 / 13
• Subtask 4: 10 / 10
• Subtask 5: 20 / 20
• Subtask 6: 17 / 17
• Subtask 7: 25 / 25