Submission #1022543

#	Time	Username	Problem	Language	Result	Execution time	Memory
1022543		pera	Stone Arranging 2 (JOI23_ho_t1)	C++17	100 / 100	162 ms	36340 KiB

Main

#include<bits/stdc++.h>
using namespace std;
int main(){
   int n;
   cin >> n;
   vector<pair<int , int>> v;
   vector<int> bef(n + 1) , a(n + 1);
   for(int i = 1;i <= n;i ++){
      cin >> bef[i];
      v.push_back({bef[i] , i});
   }
   sort(v.begin() , v.end());
   for(int i = 0;i < n;i ++){
      a[v[i].second] = (i == 0 ? 1 : a[v[i - 1].second] + (v[i].first != v[i - 1].first));
   }
   vector<int> color(n + 1);
   set<int> alive , p[n + 1];
   for(int i = 1;i <= n;i ++){
      if(!p[a[i]].empty()){
         int pos = *--p[a[i]].end();
         while(alive.upper_bound(pos) != alive.end()){
            auto it = alive.upper_bound(pos);
            color[*it] = i;
            p[a[*it]].erase(*it);
            alive.erase(*it);
         }
      }
      p[a[i]].insert(i);
      alive.insert(i);
   }
   for(int i = n;i >= 1;i --){
      color[i] = (color[i] == 0 ? bef[i] : color[color[i]]);
   }
   for(int i = 1;i <= n;i ++){
      cout << color[i] << " ";
   }
   cout << endl;
}

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