Submission #436049

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
436049	2021-06-24T06:58:08 Z	meatrow	Arcade (NOI20_arcade)	C++17	Compilation error	0 ms	0 KB

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

Compilation message

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)
      |          ~~^~~~~~~~~~~
Arcade.cpp: In instantiation of 'solve()::<lambda(auto:23&, auto:24&)> [with auto:23 = std::pair<int, int>; auto:24 = std::pair<int, int>]':
/usr/include/c++/10/bits/predefined_ops.h:156:30:   required from 'constexpr bool __gnu_cxx::__ops::_Iter_comp_iter<_Compare>::operator()(_Iterator1, _Iterator2) [with _Iterator1 = __gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >; _Iterator2 = __gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >; _Compare = solve()::<lambda(auto:23&, auto:24&)>]'
/usr/include/c++/10/bits/stl_algo.h:82:17:   required from 'void std::__move_median_to_first(_Iterator, _Iterator, _Iterator, _Iterator, _Compare) [with _Iterator = __gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<solve()::<lambda(auto:23&, auto:24&)> >]'
/usr/include/c++/10/bits/stl_algo.h:1924:34:   required from '_RandomAccessIterator std::__unguarded_partition_pivot(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<solve()::<lambda(auto:23&, auto:24&)> >]'
/usr/include/c++/10/bits/stl_algo.h:1958:38:   required from 'void std::__introsort_loop(_RandomAccessIterator, _RandomAccessIterator, _Size, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >; _Size = long int; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<solve()::<lambda(auto:23&, auto:24&)> >]'
/usr/include/c++/10/bits/stl_algo.h:1974:25:   required from 'void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<solve()::<lambda(auto:23&, auto:24&)> >]'
/usr/include/c++/10/bits/stl_algo.h:4892:18:   required from 'void std::sort(_RAIter, _RAIter, _Compare) [with _RAIter = __gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >; _Compare = solve()::<lambda(auto:23&, auto:24&)>]'
Arcade.cpp:88:6:   required from here
Arcade.cpp:87:34: error: lvalue required as left operand of assignment
   87 |         return f.first < s.first || f.first = s.first && f.second > s.second;
      |                ~~~~~~~~~~~~~~~~~~^~~~~~~~~~