/ SeriousOJ /

Record Detail

Accepted


  
# Status Time Cost Memory Cost
#1 Accepted 3ms 2.32 MiB
#2 Accepted 33ms 2.754 MiB
#3 Accepted 40ms 2.863 MiB
#4 Accepted 41ms 4.852 MiB
#5 Accepted 65ms 7.316 MiB
#6 Accepted 68ms 5.824 MiB

Code

/*
ALLAH IS GREAT
*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define nl "\n"
#define mod 10000007
#define boost ios_base::sync_with_stdio(false);cin.tie(NULL);
#define mx 2000007
ll arr[mx];
ll tree[mx * 3]; 
void init(ll node, ll b, ll e)
{
    if (b == e) {
        tree[node] = b; 
        return;
    }
    ll Left = node * 2;
    ll Right = node * 2 + 1;
    ll mid = (b + e) / 2;
    init(Left, b, mid);
    init(Right, mid + 1, e);
    if (arr[tree[Left]] < arr[tree[Right]]) {
        tree[node] = tree[Left];
    } else {
        tree[node] = tree[Right];
    }
}
ll query(ll node, ll b, ll e, ll i, ll j)
{
    if (i > e || j < b)
        return -1; // out of range, invalid index
    if (b >= i && e <= j)
        return tree[node]; // Relevant Segment
    ll Left = node * 2;
    ll Right = node * 2 + 1;
    ll mid = (b + e) / 2;
    
    ll p1 = query(Left, b, mid, i, j);
    ll p2 = query(Right, mid + 1, e, i, j);

    if (p1 == -1) return p2; 
    if (p2 == -1) return p1; 
    if (arr[p1] < arr[p2]) {
        return p1;
    } else {
        return p2;
    }
}
void update(ll node, ll b, ll e, ll index, ll new_value)
{
    if (b == e) {
        arr[b] = new_value;
        tree[node] = b;
        return;
    }

    ll Left = node * 2;
    ll Right = node * 2 + 1;
    ll mid = (b + e) / 2;
    if (index <= mid) {
        update(Left, b, mid, index, new_value);
    } else {
        update(Right, mid + 1, e, index, new_value);
    }
    if (arr[tree[Left]] < arr[tree[Right]]) {
        tree[node] = tree[Left];
    } else {
        tree[node] = tree[Right];
    }
}

int main()
{
    boost;
 
    ll n;
    cin >> n;
    for (ll i = 1; i <= n; i++) {
        cin >> arr[i];
    }
    init(1, 1, n);
    ll q;
    cin>>q;
    while (q--) {
        ll l=1, r=n, new_value;
        cin >> new_value;
        ll min_pos = query(1, 1, n, l, r);
        cout<<min_pos<<nl;
        update(1, 1, n, min_pos, new_value);
    }

    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 16:08:42
Judged At
2024-10-03 13:28:28
Judged By
Score
100
Total Time
68ms
Peak Memory
7.316 MiB