/ SeriousOJ /

Record Detail

Accepted


  
# Status Time Cost Memory Cost
#1 Accepted 4ms 3.566 MiB
#2 Accepted 209ms 3.691 MiB
#3 Accepted 221ms 3.859 MiB
#4 Accepted 222ms 3.926 MiB
#5 Accepted 257ms 4.445 MiB
#6 Accepted 271ms 4.453 MiB

Code

#include<bits/stdc++.h>
typedef long long  ll;
#define endl       '\n'
#define Code ios_base::sync_with_stdio(false);
#define By cin.tie(NULL);
#define Abid cout.tie(NULL);
using namespace std;

const int N = 1e5 + 10;
int a[N];
vector<pair<int,int>>tree(4 * N);
void build(int node, int st, int en)//node 1 based
{
    if (st == en)
    {
        tree[node] = {a[st], st};
        return;
    }
    int mid = (st + en) / 2;
    build(2 * node, st, mid);                         // divide left side
    build(2 * node + 1, mid + 1, en);                 // divide right side
    // tree[node] = min (tree[2 * node] , tree[2 * node + 1]); // sum of left and right side
    if(tree[2 * node].first < tree[2 * node + 1].first){
        tree[node] = tree[2 * node];
    }
    else{
        tree[node] = tree[2 * node + 1];
    }
}
pair<int,int> query(int node, int st, int en, int l, int r)
{
    if (st > r || en < l) // No overlapping and out of range
    {
        return {INT_MAX, -1};
    }
    if (l <= st && en <= r) // Complete overlapped (l-r in range)
    {
        return tree[node];
    }
    // Partial overlapping
    int mid = (st + en) / 2;

    pair<int,int> q1 = query(2 * node, st, mid, l, r);
    pair<int,int> q2 = query(2 * node + 1, mid + 1, en, l, r);
    // return q1 + q2;
    if(q1.first < q2.first){
        return q1;
    }
    else{
        return q2;
    }
}
void update(int node, int st, int en, int idx, int val)
{
    if (st == en)
    {
        a[st] = val;
        tree[node] = {val, st};
        return;
    }
    int mid = (st + en) / 2;
    int left = 2 * node, right = 2 * node + 1;
    if (idx <= mid) update(left, st, mid, idx, val);
    else update(right, mid + 1, en, idx, val);
    if(tree[left].first < tree[right].first){
        tree[node] = tree[left];
    }
    else{
        tree[node] = tree[right];
    }
}
void solve()
{
    ll n, q, k1, c = 0, ans = 0;
    cin >> n;

    for (ll i = 0; i < n; i++)
    {
        ll x;
        cin >> x;
        a[i] = x;
    }
    build(1, 0, n - 1); // Createing Segment tree;
    cin >> q;
    while (q--)
    {
        int val;
        cin >> val;
        pair <int,int> ans = query(1, 0, n-1, 0, n-1);
        cout << ans.second + 1<< endl;
        update(1, 0, n-1, ans.second, val);
    }
    return;
}
int main()
{
    // Code By Abid
    int tc=1;
    // cin>>tc;
    for(int i=1; i<=tc; ++i)
    {
        // cout<<"Case "<<i<<":\n";
        solve();
    }
    return 0;
}

Information

Submit By
Type
Submission
Problem
P1086 KuZ the Position
Contest
Bangladesh 2.0
Language
C++20 (G++ 13.2.0)
Submit At
2024-08-16 15:48:22
Judged At
2024-11-11 03:17:14
Judged By
Score
100
Total Time
271ms
Peak Memory
4.453 MiB