Submission #724591

#	Time	Username	Problem	Language	Result	Execution time	Memory
724591		awu	Arcade (NOI20_arcade)	C++14	0 / 100	1 ms	212 KiB

Arcade

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

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")

#define int long long
#define f first
#define s second
#define all(x) x.begin(), x.end()
#define debug(x) do{auto __tmp__ = x; cerr << #x << " = " << __tmp__ << endl;}while(0)
// #define endl "\n"
#define unordered_map __gnu_pbds::gp_hash_table
using pii = pair<int, int>;

const int inf = 1ll << 60;
// const int inf = 1 << 30;
const int MOD = 1e9 + 7;

struct segtree {
  vector<int> t;
  segtree(int s) {
    int n = 1;
    while(n < s) n *= 2;
    t.resize(n * 2);
  }
  void update(int i, int v, int n = 1, int tl = 0, int tr = -1) {
    if(tr == -1) tr = t.size() / 2;
    if(tl + 1 == tr) {
      t[n] = v;
      return;
    }
    int tm = (tl + tr) / 2;
    if(i < tm) update(i, v, n * 2, tl, tm);
    else update(i, v, n * 2 + 1, tm, tr);
    t[n] = max(t[n * 2], t[n * 2 + 1]);
  }
  int query(int ql, int qr, int n = 1, int tl = 0, int tr = -1) {
    if(tr == -1) tr = t.size() / 2;
    if(ql >= tr || qr <= tl) return 0;
    if(ql <= tl && qr >= tr) return t[n];
    int tm = (tl + tr) / 2;
    return max(query(ql, qr, n * 2, tl, tm),
               query(ql, qr, n * 2 + 1, tm, tr));
  }
};

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n, m; cin >> n >> m;
  vector<int> t(n), a(n);
  for(int i = 0; i < m; i++) {
    cin >> t[i];
  }
  for(int i = 0; i < m; i++) {
    cin >> a[i];
  }
  vector<pii> p(n);
  for(int i = 0; i < n; i++) {
    p[i] = {t[i] + a[i], t[i] - a[i]};
  }
  map<int, int> cc;
  for(int i = 0; i < n; i++) {
    cc[p[i].s] = 0;
  }
  cc[-inf] = 0;
  cc[inf] = 0;
  int j = 0;
  for(auto i : cc) {
    cc[i.f] = j++;
  }
  sort(all(p), [](pii a, pii b) {
    return a.f < b.f || a.f == b.f && a.s > b.s;
  });
  segtree st(cc.size());
  for(auto i : p) {
    st.update(cc[i.s], st.query(0, cc[i.s]) + 1);
  }
  cout << st.query(0, cc.size()) << endl;
}

Compilation message (stderr)

Arcade.cpp: In lambda function:
Arcade.cpp:74:36: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   74 |     return a.f < b.f || a.f == b.f && a.s > b.s;
      |                                    ^

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