Submission #70809773

---

Source Code Expand

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
//using mint = modint1000000007;
//const int mod = 1000000007;
//using mint = modint998244353;
//const int mod = 998244353;
//const int INF = 1e9;
//const long long LINF = 1e18;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep2(i,l,r)for(int i=(l);i<(r);++i)
#define rrep(i, n) for (int i = (n) - 1; i >= 0; --i)
#define rrep2(i,l,r)for(int i=(r) - 1;i>=(l);--i)
#define all(x) (x).begin(),(x).end()
#define allR(x) (x).rbegin(),(x).rend()
#define P pair<int,int>
template<typename A, typename B> inline bool chmax(A & a, const B & b) { if (a < b) { a = b; return true; } return false; }
template<typename A, typename B> inline bool chmin(A & a, const B & b) { if (a > b) { a = b; return true; } return false; }

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <class T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	int n, q; cin >> n >> q;
	vector<int>a(n);
	rep(i, n) cin >> a[i];

	vector<pair<long long, int>> query;
	rep(i, q) {
		long long k; cin >> k;
		query.push_back({ k - 1, i });
	}
	sort(allR(query));
	vector<pair<int, int>> ans(q);

	ordered_set<pair<int, int>> st;
	for (int i = 0; i < n; i++) st.insert({ a[i], -i });

	long long cnt = 0;
	// 操作後に小さくなる
	rep(l, n) {
		st.erase({ a[l],-l });
		long long lim = st.order_of_key({ a[l], -(1 << 30) });//未満の数
		while (!query.empty()) {
			auto[k, idx] = query.back();

			long long k1 = k - cnt;
			if (k1 >= lim) break;

			// find_by_order : 0-indexed で k 番目に小さい値を指すイテレータを取得する
			auto r = -(*st.find_by_order(k1)).second;
			ans[idx] = { l,r };
			query.pop_back();
		}
		cnt += lim;
	}

	// 操作して普遍
	{
		vector<int>c(n + 1, 0), idx(n + 1, -1);
		P p;
		rep(i, n) {
			if (idx[a[i]] != -1) p = { idx[a[i]],i };
			cnt += c[a[i]];
			c[a[i]]++;
			idx[a[i]] = i;
		}
		while (!query.empty()) {
			auto[k, idx] = query.back();

			if (k >= cnt)break;

			ans[idx] = p;
			query.pop_back();
		}
	}
	// 操作して大きくなる
	rrep(l, n) {
		int offset = st.order_of_key({ a[l], 1 << 30 });//未満の数
		while (!query.empty()) {
			auto[k, idx] = query.back();

			long long k1 = k - cnt + offset;
			if (k1 >= st.size())break;
			auto r = (*st.find_by_order(k1)).second;
			ans[idx] = { l, r };
			query.pop_back();
		}

		cnt += st.size() - offset;
		st.insert({ a[l],l });
	}
	for (auto[l, r] : ans)cout << l + 1 << " " << r + 1 << endl;
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function 'int main()':
./Main.cpp:89:32: warning: comparison of integer expressions of different signedness: 'long long int' and '__gnu_pbds::detail::bin_search_tree_set<std::pair<int, int>, __gnu_pbds::null_type, std::less<std::pair<int, int> >, __gnu_pbds::detail::tree_traits<std::pair<int, int>, __gnu_pbds::null_type, std::less<std::pair<int, int> >, __gnu_pbds::tree_order_statistics_node_update, __gnu_pbds::rb_tree_tag, std::allocator<char> >, std::allocator<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |                         if (k1 >= st.size())break;
      |                             ~~~^~~~~~~~~~~~

Judge Result