oj.uz

Submission #724591

# Submission time Handle Problem Language Result Execution time Memory
724591 2023-04-15T15:30:24 Z awu Arcade (NOI20_arcade) C++14
0 / 100
 1 ms 212 KB 
#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

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.0

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

Subtask #2
0 / 11.0

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

Subtask #3
0 / 12.0

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

Subtask #4
0 / 21.0

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

Subtask #5
0 / 14.0

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

Subtask #6
0 / 20.0

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

Subtask #7
0 / 15.0

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