Submission #857336

#	Time	Username	Problem	Language	Result	Execution time	Memory
857336		Marceantasy	Stone Arranging 2 (JOI23_ho_t1)	C++17	35 / 100	66 ms	12912 KiB

Main

#include <bits/stdc++.h> 
using namespace std; 
 
#define ll long long 
#define ar array
#define rep(i, n) for(int i = 0; i<(int)n; ++i)
 
const int mxN = 2e5+5, MOD = 998244353; 

map<int, vector<int>> mp;

void solve(){
    int n;
    cin >> n;
    vector<int> ans(n);
    multiset<int> vals;
    for(int i = 0; i<n; ++i){
        int x;
        cin >> x; 
        vals.insert(i);
        if(mp.count(x) && mp[x].size() >= 1){
            int idx = i-1;
            while(idx > mp[x].back()){
                mp[ans[idx]].pop_back();
                vals.erase(vals.find(idx));
                idx--;
            }
        }
        mp[x].push_back(i);
        ans[i] = x;
    }
    vector<int> f;
    for(int val : vals)f.push_back(val);
    for(int i = 1; i<f.size(); ++i){
        int idx = f[i-1];
        if(ans[idx] == ans[f[i]]){
            while(idx < f[i]){
                ans[idx++] = ans[f[i]];
            }
        }
    }
    rep(i, n){
        cout << ans[i] << "\n";
    }
}
 

int main(){ 
#ifdef _DEBUG
//	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
    std::ios_base::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0);
 
    solve();
}

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:34:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     for(int i = 1; i<f.size(); ++i){
      |                    ~^~~~~~~~~

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