Submission #1266230

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266230		canhnam357	Index (COCI21_index)	C++20	110 / 110	110 ms	6548 KiB

index

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;
namespace fastio {
static constexpr int SZ = 1 << 17;
char inbuf[SZ], outbuf[SZ];
int in_left = 0, in_right = 0, out_right = 0;

struct Pre {
  char num[40000];
  constexpr Pre() : num() {
    for (int i = 0; i < 10000; i++) {
      int n = i;
      for (int j = 3; j >= 0; j--) {
        num[i * 4 + j] = n % 10 + '0';
        n /= 10;
      }
    }
  }
} constexpr pre;

inline void load() {
  int len = in_right - in_left;
  memmove(inbuf, inbuf + in_left, len);
  in_right = len + fread(inbuf + len, 1, SZ - len, stdin);
  in_left = 0;
}

inline void flush() {
  fwrite(outbuf, 1, out_right, stdout);
  out_right = 0;
}

inline void skip_space() {
  if (in_left + 32 > in_right) load();
  while (inbuf[in_left] <= ' ') in_left++;
}

inline void rd(char& c) {
  if (in_left + 32 > in_right) load();
  c = inbuf[in_left++];
}
template <typename T>
inline void rd(T& x) {
  if (in_left + 32 > in_right) load();
  char c;
  do c = inbuf[in_left++];
  while (c < '-');
  [[maybe_unused]] bool minus = false;
  if constexpr (is_signed<T>::value == true) {
    if (c == '-') minus = true, c = inbuf[in_left++];
  }
  x = 0;
  while (c >= '0') {
    x = x * 10 + (c & 15);
    c = inbuf[in_left++];
  }
  if constexpr (is_signed<T>::value == true) {
    if (minus) x = -x;
  }
}
inline void rd() {}
template <typename Head, typename... Tail>
inline void rd(Head& head, Tail&... tail) {
  rd(head);
  rd(tail...);
}

inline void wt(char c) {
  if (out_right > SZ - 32) flush();
  outbuf[out_right++] = c;
}
inline void wt(bool b) {
  if (out_right > SZ - 32) flush();
  outbuf[out_right++] = b ? '1' : '0';
}
inline void wt(const string &s) {
  if (out_right + s.size() > SZ - 32) flush();
  memcpy(outbuf + out_right, s.data(), sizeof(char) * s.size());
  out_right += s.size();
}
template <typename T>
inline void wt(T x) {
  if (out_right > SZ - 32) flush();
  if (!x) {
    outbuf[out_right++] = '0';
    return;
  }
  if constexpr (is_signed<T>::value == true) {
    if (x < 0) outbuf[out_right++] = '-', x = -x;
  }
  int i = 12;
  char buf[16];
  while (x >= 10000) {
    memcpy(buf + i, pre.num + (x % 10000) * 4, 4);
    x /= 10000;
    i -= 4;
  }
  if (x < 100) {
    if (x < 10) {
      outbuf[out_right] = '0' + x;
      ++out_right;
    } else {
      uint32_t q = (uint32_t(x) * 205) >> 11;
      uint32_t r = uint32_t(x) - q * 10;
      outbuf[out_right] = '0' + q;
      outbuf[out_right + 1] = '0' + r;
      out_right += 2;
    }
  } else {
    if (x < 1000) {
      memcpy(outbuf + out_right, pre.num + (x << 2) + 1, 3);
      out_right += 3;
    } else {
      memcpy(outbuf + out_right, pre.num + (x << 2), 4);
      out_right += 4;
    }
  }
  memcpy(outbuf + out_right, buf + i + 4, 12 - i);
  out_right += 12 - i;
}
inline void wt() {}
template <typename Head, typename... Tail>
inline void wt(Head&& head, Tail&&... tail) {
  wt(head);
  wt(forward<Tail>(tail)...);
}
template <typename... Args>
inline void wtn(Args&&... x) {
  wt(forward<Args>(x)...);
  wt('\n');
}

struct Dummy {
  Dummy() { atexit(flush); }
} dummy;

}  // namespace fastio
using fastio::rd;
using fastio::skip_space;
using fastio::wt;
using fastio::wtn;

typedef long long ll;
typedef pair<int,int> pi;
const int MM = 2e5+5,B = 75;
int n,q,p[MM],res[MM],freq[MM],sum_h; // = freq[h] + freq[h+1] + ...
struct Query{
    int l,r,i;
    bool operator<(const Query& o){
        if(l/B == o.l/B) return ((l/B) & 1) ? r < o.r : r > o.r;
        return l/B < o.l/B;
    }
}qu[MM];

int l,r,ans;
int main(){
    cin.tie(0)->sync_with_stdio(0);
    rd(n,q);
    for(int i = 1; i <= n; i++){
        rd(p[i]);
    }
    for(int i = 1; i <= q; i++){
        rd(l,r);
        qu[i] = {l,r,i};
    }
    sort(qu+1,qu+1+q); l = 1; r = 0;
    auto add = [&](int i){
        freq[p[i]]++;
        if(p[i] >= ans){
            sum_h++;
        }
        if(sum_h-freq[ans] >= ans+1){
            sum_h -= freq[ans];
            ans++;
        }
    };
    auto rem = [&](int i){
        freq[p[i]]--;
        if(p[i] >= ans){
            sum_h--;
        }
        if(sum_h < ans){
            sum_h += freq[ans-1];
            ans--;
        }
    };
    for(int i = 1; i <= q; i++){
        while(l > qu[i].l) add(--l);
        while(r < qu[i].r) add(++r);
        while(l < qu[i].l) rem(l++);
        while(r > qu[i].r) rem(r--);
        res[qu[i].i] = ans;
    }
    for(int i = 1; i <= q; i++) wt(res[i],'\n');
}

• Subtask 1: 20 / 20
• Subtask 2: 40 / 40
• Subtask 3: 50 / 50