Submission #799285

#	Time	Username	Problem	Language	Result	Execution time	Memory
799285		radaiosm7	Stone Arranging 2 (JOI23_ho_t1)	C++98	100 / 100	253 ms	30116 KiB

Main

#include <bits/stdc++.h>
using namespace std;
int n, m, i, x;
int seg[800020];
int ans[200005];
map<int, vector<int> > col;

void update(int from, int to, int l=1, int r=n, int indx=1) {
  if (from == l && to == r) {
    seg[indx] = x;
    return;
  }

  int mid = (l+r)/2;

  if (seg[indx] != 0) {
    seg[2*indx] = seg[indx];
    seg[2*indx+1] = seg[indx];
    seg[indx] = 0;
  }

  if (to <= mid) update(from, to, l, mid, 2*indx);
  else if (from > mid) update(from, to, mid+1, r, 2*indx+1);
  
  else {
    update(from, mid, l, mid, 2*indx);
    update(mid+1, to, mid+1, r, 2*indx+1);
  }
}

int query(int pos, int l=1, int r=n, int indx=1) {
  if (l == r) return seg[indx];
  int mid = (l+r)/2;

  if (seg[indx] != 0) {
    seg[2*indx] = seg[indx];
    seg[2*indx+1] = seg[indx];
    seg[indx] = 0;
  }

  if (pos <= mid) return query(pos, l, mid, 2*indx);
  else return query(pos, mid+1, r, 2*indx+1);
}

void build(int l=1, int r=n, int indx=1) {
  if (l == r) {
    ans[l] = seg[indx];
    return;
  }

  int mid = (l+r)/2;

  if (seg[indx] != 0) {
    seg[2*indx] = seg[indx];
    seg[2*indx+1] = seg[indx];
    seg[indx] = 0;
  }

  build(l, mid, 2*indx);
  build(mid+1, r, 2*indx+1);
}

int main() {
  scanf("%d", &n);
  fill(seg, seg+800015, 0);

  for (i=1; i <= n; ++i) {
    scanf("%d", &x);
    if (col.find(x) == col.end()) col[x] = {};
    while (!col[x].empty() && query(col[x].back()) != x) col[x].pop_back();
    if (!col[x].empty()) update(col[x].back(), i);
    else update(i, i);
    col[x].push_back(i);
  }

  build();
  for (i=1; i <= n; ++i) printf("%d\n", ans[i]);
  return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:64:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |   scanf("%d", &n);
      |   ~~~~~^~~~~~~~~~
Main.cpp:68:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |     scanf("%d", &x);
      |     ~~~~~^~~~~~~~~~

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