oj.uz

답안 #1046961

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1046961 2024-08-07T06:58:51 Z vjudge1 Index (COCI21_index) C++17
0 / 110
 3 ms 2396 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;
	map<int,int> mp;
	map<int,int> rmp;
	for(int i = 0;n > i;i++)
	{
		cin >> a[i];
		mp[a[i]]++;
	}
	int t = 0;
	for(auto& it : mp) it.second = ++t;
	for(int i = 0;n > i;i++)
	{
		rmp[mp[a[i]]] = a[i];
		a[i] = mp[a[i]];
	}
	int bos[n + 8];
	memset(bos,0,sizeof(bos));
	pst.tree[++sz] = pst.Build(1,n + 7,bos);
	pst.tree[sz] = pst.Update(a[0], 1, 1, n + 7, 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 , n + 7, 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);
	while(q--)
	{
		int l,r;
		cin >> l >> r;
		l--;
		int l1 = 0, r1 = n - 1;
		while(r1 > l1)
		{
			int mid = (l1 + r1) / 2;
			int azalt = 0;
			if(l != 0) azalt = pst.Query(a[mid], n + 7, 1, n + 7, pst.tree[l]);
			//cout << pst.Query(a[mid], n + 7, 1, n + 7, pst.tree[r]) << " " << azalt << " " << rmp[a[mid]] << " " << mid << " " << r << " " << l << endl;
			if(pst.Query(a[mid], n + 7, 1, n + 7, pst.tree[r]) - azalt >= rmp[a[mid]])
			{
				l1 = mid + 1;
			}
			else r1 = mid;
		}
		cout << a[--l1] << endl;
	}
}

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

Compilation message

index.cpp: In constructor 'PersistentSegTree::Node::Node(PersistentSegTree::Node*)':
index.cpp:24:8: warning: '*<unknown>.PersistentSegTree::Node::val' is used uninitialized in this function [-Wuninitialized]
   24 |    val += old_root->val;
      |    ~~~~^~~~~~~~~~~~~~~~
index.cpp: In constructor 'PersistentSegTree::Node::Node(long long int)':
index.cpp:28:8: warning: '*<unknown>.PersistentSegTree::Node::val' is used uninitialized in this function [-Wuninitialized]
   28 |    val += _val;
      |    ~~~~^~~~~~~

Subtask #1
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -