| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 436049 | meatrow | Arcade (NOI20_arcade) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
const int MOD = 998244353;
ll binpow(ll a, ll p, int mod = MOD) {
ll res = 1;
while (p) {
if (p & 1) {
(res *= a) %= mod;
}
p >>= 1;
(a *= a) %= mod;
}
return res;
}
ll gcd(ll a, ll b) {
return b == 0 ? a : gcd(b, a % b);
}
struct FT {
vector<ll> s;
FT(int n) : s(n) {}
void update(int pos, ll dif) { // a[pos] += dif
for (; pos < s.size(); pos |= pos + 1) s[pos] = max(s[pos], dif);
}
ll query(int pos) { // sum of values in [0, pos)
ll res = 0;
for (; pos > 0; pos &= pos - 1) res = max(res, s[pos-1]);
return res;
}
};
struct FT2 {
vector<vector<int>> ys; vector<FT> ft;
FT2(int limx) : ys(limx) {}
void fakeUpdate(int x, int y) {
for (; x < ys.size(); x |= x + 1) ys[x].push_back(y);
}
void init() {
for (auto& v : ys) sort(v.begin(), v.end()), ft.emplace_back(v.size());
}
int ind(int x, int y) {
return (int)(lower_bound(ys[x].begin(), ys[x].end(), y) - ys[x].begin()); }
void update(int x, int y, ll dif) {
for (; x < ys.size(); x |= x + 1)
ft[x].update(ind(x, y), dif);
}
ll query(int x, int y) {
ll sum = 0;
for (; x; x &= x - 1)
sum = max(sum, ft[x-1].query(ind(x-1, y)));
return sum;
}
};
template <class T>
void compress(vector<T>& vec) {
sort(vec.begin(), vec.end());
vec.resize(unique(vec.begin(), vec.end()) - vec.begin());
}
void solve() {
int n, m;
cin >> n >> m;
vector<pair<int, int>> a(m);
for (int i = 0; i < m; i++) {
cin >> a[i].first;
}
for (int i = 0; i < m; i++) {
cin >> a[i].second;
}
vector<int> x(m), y(m);
for (int i = 0; i < m; i++) {
x[i] = a[i].first + a[i].second;
y[i] = a[i].second - a[i].first;
a[i] = {x[i], y[i]};
}
compress(a);
sort(a.begin(), a.end(), [](auto& f, auto& s) {
return f.first < s.first || f.first = s.first && f.second > s.second;
});
compress(x);
compress(y);
FT2 fenw(x.size() + 1);
m = a.size();
for (int i = 0; i < m; i++) {
int pos1X = lower_bound(x.begin(), x.end(), a[i].first) - x.begin();
int pos1Y = lower_bound(y.begin(), y.end(), a[i].second) - y.begin();
fenw.fakeUpdate(pos1X, pos1Y);
}
fenw.init();
int ans = 1;
for (int i = 0; i < m; i++) {
int posX = lower_bound(x.begin(), x.end(), a[i].first) - x.begin();
int posY = lower_bound(y.begin(), y.end(), a[i].second) - y.begin();
int val = fenw.query(posX + 1, posY);
ans = max(ans, val + 1);
fenw.update(posX, posY, val + 1);
}
cout << ans << endl;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T = 1;
// cin >> T;
for (int tc = 1; tc <= T; tc++) {
// cout << "Case #" << tc << ": ";
solve();
}
return 0;
}