| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1046969 |
2024-08-07T07:08:37 Z |
vjudge1 |
Index (COCI21_index) |
C++17 |
|
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);
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 = 0, r1 = vec.size() - 1;
int ans = 0;
while(r1 > l1)
{
int mid = (l1 + r1) / 2;
int azalt = 0;
if(l != 0) azalt = pst.Query(vec[mid], n + 7, 1, n + 7, pst.tree[l]);
// cout << pst.Query(vec[mid], n + 7, 1, n + 7, pst.tree[r]) << " " << azalt << " " << rmp[a[mid]] << endl;
if(pst.Query(vec[mid], n + 7, 1, n + 7, pst.tree[r]) - azalt >= rmp[vec[mid]])
{
l1 = mid + 1;
}
else r1 = mid;
}
int azalt = 0;
if(l != 0) azalt = pst.Query(vec[l1], n + 7, 1, n + 7, pst.tree[l]);
if(pst.Query(vec[l1], n + 7, 1, n + 7, pst.tree[r]) - azalt < rmp[vec[l1]])
cout << vec[l1] - 1 << endl;
else
cout << vec[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 function 'void solve()':
index.cpp:108:7: warning: unused variable 'ans' [-Wunused-variable]
108 | int ans = 0;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
2396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
2396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
2396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
