Submission #757629

#	Time	Username	Problem	Language	Result	Execution time	Memory
757629		mdub	Stone Arranging 2 (JOI23_ho_t1)	C++14	0 / 100	1 ms	596 KiB

Main

#include <bits/stdc++.h>

using namespace std;

int main () {
  int n; cin >> n;
  vector<int> a(n);
  set<int> s;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    s.insert(a[i]);
  }
  map<int, int> compression;
  vector<int> revertedCompression(n + 1);
  auto it = s.begin();
  for (int i = 1; i <= s.size(); i++) {
    compression[*it] = i;
    revertedCompression[i] = *it;
    it++;
  }
  for (int i = 0; i < n; i++) {
    a[i] = compression[a[i]];
  }
			      
    
  vector<pair<int, int>> bornes(n, {0, -1});
  vector<set<int>> js(n + 1);
  
  for (int i = 0; i < n; i++) {
    //cout << a[i] << endl;
    if (js[a[i]].size()) {
      auto it = js[a[i]].end();
      it--;
      int ind = *it;
      while (ind < i) {
	if (bornes[ind].first > 0) {
	  ind = bornes[ind].second;
	  js[-bornes[ind].first].erase(bornes[ind].second);
	}
	else {
	  js[a[ind]].erase(ind);
	}
	ind++;
      }

      bornes[*it].first = a[i];
      bornes[*it].second = i;
      bornes[i].first = -a[i];
      bornes[i].second = i;
    }
    
    js[a[i]].insert(i);
  }
  
  int cur = -1;
  for (int i = 0; i < bornes.size(); i++) {
    pair<int, int> elem = bornes[i];
    if (elem.first > 0 && cur == -1) {
      cur = elem.first;
    }
    if (cur == -1) {
      cout << revertedCompression[a[i]] << '\n';
    }
    else cout << revertedCompression[cur] << '\n';
    if (elem.first == -cur) cur = -1;
  }
    
  
				
				
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:16:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::set<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |   for (int i = 1; i <= s.size(); i++) {
      |                   ~~^~~~~~~~~~~
Main.cpp:56:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |   for (int i = 0; i < bornes.size(); i++) {
      |                   ~~^~~~~~~~~~~~~~~

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