Submission #1150092

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150092		LinkedArray	Arcade (NOI20_arcade)	C++20	100 / 100	198 ms	13472 KiB

Arcade

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
#define pb push_back

vector<int> t, a;
vector<pair<int, int>> bf, nrm;
set<int> max_cresc;

int main () {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, m, i, b, f, val, idx;

  cin >> n >> m;

  t = vector<int>(m + 1);
  for (i = 1; i <= m; i++) {
    cin >> t[i];
  }

  a = vector<int>(m + 1);
  bf = vector<pair<int, int>>(m + 1);
  for (i = 1; i <= m; i++) {
    cin >> a[i];

    f = t[i] - a[i];
    b = t[i] + a[i];
    bf[i] = make_pair(f, b);
  }
  sort(bf.begin() + 1, bf.end());

  nrm = vector<pair<int, int>>(m + 1);
  for (i = 1; i <= m; i++) {
    val = bf[i].second;
    idx = i;
    nrm[i] = make_pair(val, idx);
  }
  sort(nrm.begin() + 1, nrm.end());

  for (i = 1; i <= m; i++) {
    auto it = max_cresc.lower_bound(nrm[i].second);
    if (it == max_cresc.begin()) {
      max_cresc.insert(nrm[i].second);
      continue;
    }
    max_cresc.erase(prev(it));
    max_cresc.insert(nrm[i].second);
  }

  cout << max_cresc.size() << "\n";
  return 0;
}

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 12 / 12
• Subtask 4: 21 / 21
• Subtask 5: 14 / 14
• Subtask 6: 20 / 20
• Subtask 7: 15 / 15