제출 #1271107

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1271107		hoangtien69	Stone Arranging 2 (JOI23_ho_t1)	C++20	60 / 100	2093 ms	30312 KiB

Main

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 5;

int n;
vector<int> peal;
int a[MAXN];
vector<int> st[4 * MAXN];
int lazy[4 * MAXN];
unordered_map<int,int> mp;

int findd(int x)
{
    return lower_bound(peal.begin(), peal.end(), x) - peal.begin() + 1;
}
void push(int id, int l, int r)
{
    if (lazy[id] == 0) return;
    st[id].clear();
    st[id].push_back(lazy[id]);
    if (l != r)
    {
        lazy[id * 2] = lazy[id];
        lazy[id * 2 + 1] = lazy[id];
    }
    lazy[id] = 0;
}
void pull(int id)
{
    vector<int> tmp;
    tmp.reserve(st[id * 2].size() + st[id * 2 + 1].size());
    merge(st[id * 2].begin(), st[id * 2].end(), st[id * 2 + 1].begin(), st[id * 2 + 1].end(), back_inserter(tmp));
    tmp.erase(unique(tmp.begin(), tmp.end()), tmp.end());
    st[id].swap(tmp);
}
bool ck(int id, int val)
{
    if (st[id].empty()) return false;
    auto it = lower_bound(st[id].begin(), st[id].end(), val);
    if (it == st[id].end()) return false;
    return (*it == val);
}
int find_pos(int id, int l, int r, int val)
{
    push(id, l, r);
    if (!ck(id, val)) return -1;
    if (l == r) return l;
    int m = (l + r) >> 1;
    int left = id * 2, right = id * 2 + 1;
    push(right, m + 1, r);
    if (ck(right, val))
    {
        return find_pos(right, m + 1, r, val);
    }
    else
    {
        push(left, l, m);
        return find_pos(left, l, m, val);
    }
}
void update(int id, int l, int r, int u, int v, int val)
{
    push(id, l, r);
    if (v < l || r < u) return;
    if (u <= l && r <= v)
    {
        lazy[id] = val;
        push(id, l, r);
        return;
    }
    int m = (l + r) >> 1;
    update(id * 2, l, m, u, v, val);
    update(id * 2 + 1, m + 1, r, u, v, val);
    pull(id);
}
int gett(int id, int l, int r, int pos)
{
    push(id, l, r);
    if (l == r)
    {
        if (st[id].empty()) return 0;
        return st[id][0];
    }
    int m = (l + r) >> 1;
    if (pos <= m) return gett(id * 2, l, m, pos);
    else return gett(id * 2 + 1, m + 1, r, pos);
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        peal.push_back(a[i]);
    }
    sort(peal.begin(), peal.end());
    peal.erase(unique(peal.begin(), peal.end()), peal.end());
    for (int i = 1; i <= n; i++)
    {
        int cur = findd(a[i]);
        mp[cur] = a[i];
        a[i] = cur;
    }
    for (int i = 1; i <= n; i++)
    {
        int cak = find_pos(1, 1, n, a[i]);
        if (cak == -1)
        {
            update(1, 1, n, i, i, a[i]);
        }
        else
        {
            update(1, 1, n, cak, i, a[i]);
        }
    }
    for (int i = 1; i <= n; i++)
    {
        int cur = gett(1, 1, n, i);
        if (cur == 0) cout << 0 << "\n";
        else cout << mp[cur] << "\n";
    }
}

• Subtask 1: 25 / 25
• Subtask 2: 35 / 35
• Subtask 3: 0 / 40