oj.uz

Submission #1046972

# Submission time Handle Problem Language Result Execution time Memory
1046972 2024-08-07T07:11:33 Z vjudge1 Index (COCI21_index) C++17
110 / 110
 1104 ms 143304 KB 
#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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 16732 KB Output is correct
2 Correct 12 ms 16732 KB Output is correct
3 Correct 12 ms 16732 KB Output is correct
4 Correct 13 ms 16552 KB Output is correct
5 Correct 12 ms 16644 KB Output is correct
6 Correct 12 ms 16732 KB Output is correct
7 Correct 12 ms 16728 KB Output is correct
8 Correct 12 ms 16516 KB Output is correct
9 Correct 12 ms 16732 KB Output is correct
10 Correct 12 ms 16732 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 16732 KB Output is correct
2 Correct 12 ms 16732 KB Output is correct
3 Correct 12 ms 16732 KB Output is correct
4 Correct 13 ms 16552 KB Output is correct
5 Correct 12 ms 16644 KB Output is correct
6 Correct 12 ms 16732 KB Output is correct
7 Correct 12 ms 16728 KB Output is correct
8 Correct 12 ms 16516 KB Output is correct
9 Correct 12 ms 16732 KB Output is correct
10 Correct 12 ms 16732 KB Output is correct
11 Correct 246 ms 47832 KB Output is correct
12 Correct 210 ms 47968 KB Output is correct
13 Correct 224 ms 47800 KB Output is correct
14 Correct 201 ms 47824 KB Output is correct
15 Correct 209 ms 47824 KB Output is correct
16 Correct 213 ms 47832 KB Output is correct
17 Correct 239 ms 47960 KB Output is correct
18 Correct 208 ms 47824 KB Output is correct
19 Correct 222 ms 48084 KB Output is correct
20 Correct 237 ms 47980 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 16732 KB Output is correct
2 Correct 12 ms 16732 KB Output is correct
3 Correct 12 ms 16732 KB Output is correct
4 Correct 13 ms 16552 KB Output is correct
5 Correct 12 ms 16644 KB Output is correct
6 Correct 12 ms 16732 KB Output is correct
7 Correct 12 ms 16728 KB Output is correct
8 Correct 12 ms 16516 KB Output is correct
9 Correct 12 ms 16732 KB Output is correct
10 Correct 12 ms 16732 KB Output is correct
11 Correct 246 ms 47832 KB Output is correct
12 Correct 210 ms 47968 KB Output is correct
13 Correct 224 ms 47800 KB Output is correct
14 Correct 201 ms 47824 KB Output is correct
15 Correct 209 ms 47824 KB Output is correct
16 Correct 213 ms 47832 KB Output is correct
17 Correct 239 ms 47960 KB Output is correct
18 Correct 208 ms 47824 KB Output is correct
19 Correct 222 ms 48084 KB Output is correct
20 Correct 237 ms 47980 KB Output is correct
21 Correct 1070 ms 143052 KB Output is correct
22 Correct 1092 ms 143056 KB Output is correct
23 Correct 1065 ms 143060 KB Output is correct
24 Correct 1095 ms 143048 KB Output is correct
25 Correct 1049 ms 143048 KB Output is correct
26 Correct 1091 ms 143304 KB Output is correct
27 Correct 1060 ms 143072 KB Output is correct
28 Correct 1104 ms 143048 KB Output is correct
29 Correct 1071 ms 143060 KB Output is correct
30 Correct 1088 ms 143044 KB Output is correct