Submission #739059

#	Time	Username	Problem	Language	Result	Execution time	Memory
739059		Toxtaq	Stone Arranging 2 (JOI23_ho_t1)	C++17	100 / 100	246 ms	19676 KiB

Main

#include<bits/stdc++.h>
using namespace std;
struct SegmentTree{
     vector<int>segTree;
     vector<int>lazy;
     SegmentTree(int n){
        segTree.resize(4 * n);
        lazy.resize(4 * n);
     }
     void Propagate(int node, int l, int r){
        if(!lazy[node])return;
        if(l == r){
            segTree[node] = lazy[node];
        }
        else{
            lazy[node * 2] = lazy[node];
            lazy[node * 2 + 1] = lazy[node];
        }
        lazy[node] = 0;
     }
     void Build(int node, int l, int r, vector<int>&v){
        if(l == r){
            segTree[node] = v[l];
        }
        else{
            int mid = (l + r) >> 1;
            Build(node * 2, l, mid, v);
            Build(node * 2 + 1, mid + 1, r, v);
        }
     }
     void Update(int node, int l, int r, int ql, int qr, int val){
        Propagate(node, l, r);
        if(ql <= l && r <= qr){
            lazy[node] = val;
            Propagate(node, l, r);
            return;
        }
        if(ql > r || l > qr)return;
        int mid = (l + r) >> 1;
        Update(node * 2, l, mid, ql, qr, val);
        Update(node * 2 + 1, mid + 1, r, ql, qr, val);
     }
     void Print(int node, int l, int r){
        Propagate(node, l, r);
        if(l == r){
            cout << segTree[node] << "\n";
        }
        else{
            int mid = (l + r) >> 1;
            Print(node * 2, l, mid);
            Print(node * 2 + 1, mid + 1, r);
        }
     }
     int Query(int node, int l, int r, int pos){
        Propagate(node, l, r);
        if(l == r)return segTree[node];
        int mid = (l + r) >> 1;
        if(pos <= mid)return Query(node * 2, l, mid, pos);
        else return Query(node * 2 + 1, mid + 1, r, pos);
     }
};
int main()
{
    int n;
    cin >> n;
    vector<int>stones(n + 1);
    for(int i = 1;i <= n;++i){
        cin >> stones[i];
    }
    SegmentTree tree(n);
    tree.Build(1, 1, n, stones);
    map<int, int>last;
    for(int i = 1;i <= n;++i){
        int cur = stones[i];
        if(cur == tree.Query(1, 1, n, last[cur]))tree.Update(1, 1, n, last[cur], i, cur);
        last[cur] = i;
    }
    tree.Print(1, 1, n);
}

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