Submission #1046972

#	Time	Username	Problem	Language	Result	Execution time	Memory
1046972		vjudge1	Index (COCI21_index)	C++17	110 / 110	1104 ms	143304 KiB

index

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 1e18, MOD = 1e9 + 7;
const int mxQ = 2e5 + 7;
struct PersistentSegTree
{
	struct Node
	{
		int val;
		Node *left, *right;
		Node() : val(0), left(nullptr), right(nullptr) {}
		Node(Node* l,Node* r)
		{
			left = l;
			right = r;
			if(l) val += l->val;
			if(r) val += r->val;
		}
		Node(Node* old_root) 
		{
			left = old_root->left;
			right = old_root->right;
			val = old_root->val;
		}
		Node(int _val)
		{
			val = _val;
		}
	};
	vector<Node*> tree;
	PersistentSegTree()
	{
		tree.resize(200007);
	}
	Node* Build(int l,int r,int* a)
	{
		if(l == r) return new Node(a[l]);
		int mid = (l + r) / 2;
		return new Node(Build(l,mid,a),Build(mid + 1,r,a));
	}
	Node* Update(int pl,int value,int l,int r,Node* pos)
	{
		//cout << l << " " << r << endl;
		if(l == r) return new Node(pos->val + value);
		//cout << pl << " " << value << " " << l << " " << r << " " << (pos->left)->val << " " << (pos->right)->val << endl;
		int mid = (l + r) / 2;
		if(pl > mid) return new Node(pos->left,Update(pl,value,mid + 1,r,pos->right));
		else return new Node(Update(pl,value,l,mid,pos->left),pos->right);
	}
	int Query(int tl,int tr,int l,int r,Node* pos)
	{
		//cout << l << " " << r << " " << tl << " " << tr << " " << pos->val << endl;
		if(l > r || tl > tr || tl > r || l > tr) return 0;
		if(tr >= r && l >= tl) return pos->val;
		int mid = (l + r) / 2;
		return Query(tl,tr,l,mid,pos->left) + Query(tl,tr,mid + 1,r,pos->right);
	}
	Node* Set(Node* val)
	{
		return new Node(val);
	}
};
void solve()
{
	int n,q;
	cin >> n >> q;
	PersistentSegTree pst;
	int a[n];
	int sz = 0;
	for(int i = 0;n > i;i++)
	{
		cin >> a[i];
	}
	int bos[mxQ + 1];
	memset(bos,0,sizeof(bos));
	pst.tree[++sz] = pst.Build(1,mxQ,bos);
	pst.tree[sz] = pst.Update(a[0], 1, 1, mxQ, pst.tree[sz]);
	for(int i = 1;n > i;i++)
	{
		pst.tree[sz + 1] = pst.Set(pst.tree[sz]);
		sz++;
		pst.tree[sz] = pst.Update(a[i], 1, 1 , mxQ, pst.tree[sz]);
	}
	//for(int i = 1;sz >= i;i++) cout << pst.Query(1, n + 7, 1, n + 7, pst.tree[i]) << endl;
	sort(a,a+n);
	vector<int> vec;
	for(auto it : a)
	{
		if(vec.size() == 0 || vec.back() != it) vec.push_back(it);
	}
	while(q--)
	{
		int l,r;
		cin >> l >> r;
		l--;
		int l1 = 1, r1 = mxQ;
		int ans = 0;
		while(r1 > l1)
		{
			int mid = (l1 + r1) / 2;
			int azalt = 0;
			if(l != 0) azalt = pst.Query(mid, mxQ, 1, mxQ, pst.tree[l]);
		//	cout << pst.Query(vec[mid], n + 7, 1, n + 7, pst.tree[r]) << " " << azalt << " " << rmp[a[mid]] << endl;
			if(pst.Query(mid, mxQ, 1, mxQ, pst.tree[r]) - azalt >= mid)
			{
				l1 = mid + 1;
				ans = max(ans, mid);
			}
			else r1 = mid;
		}
		cout << ans << endl;
	}
}

int32_t main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int tt = 1;
	//cin >> tt;
	while(tt--) solve();
}

	

• Subtask 1: 20 / 20
• Subtask 2: 40 / 40
• Subtask 3: 50 / 50