Submission #436047

#	Time	Username	Problem	Language	Result	Execution time	Memory
436047		meatrow	Arcade (NOI20_arcade)	C++17	51 / 100	43 ms	3200 KiB

Arcade

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

Compilation message (stderr)

Arcade.cpp: In member function 'void FT::update(int, ll)':
Arcade.cpp:30:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |   for (; pos < s.size(); pos |= pos + 1) s[pos] = max(s[pos], dif);
      |          ~~~~^~~~~~~~~~
Arcade.cpp: In member function 'void FT2::fakeUpdate(int, int)':
Arcade.cpp:43:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |   for (; x < ys.size(); x |= x + 1) ys[x].push_back(y);
      |          ~~^~~~~~~~~~~
Arcade.cpp: In member function 'void FT2::update(int, int, ll)':
Arcade.cpp:51:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |   for (; x < ys.size(); x |= x + 1)
      |          ~~^~~~~~~~~~~

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