Submission #422035

#	Time	Username	Problem	Language	Result	Execution time	Memory
422035		Chaska	Index (COCI21_index)	C++11	60 / 110	2585 ms	40580 KiB

index

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef double lf;
typedef long double Lf;
typedef pair <int,int> pii;
typedef pair <ll, ll> pll;

#define TRACE(x) cerr << #x << "  " << x << endl
#define FOR(i, a, b) for (int i = (a); i < int(b); i++)
#define REP(i, n) FOR(i, 0, n)
#define all(x) (x).begin(), (x).end()
#define _ << " " <<

#define fi first
#define sec second
#define mp make_pair
#define pb push_back

const int MAXN = 200005;
const int offset = (1 << 18);

struct tournament {
  vector <int> v[offset * 2];

  void insert(int a, int b) {
    a += offset;
    while (a) {
      v[a].pb(b);
      a /= 2;
    }
  }

  void init() {
    REP(i, offset * 2) {sort(all(v[i]));
    if (v[i].size()>0) {
    ///cerr << i << " ";
    ///for (int u : v[i]) cerr << u << " ";
    ///cerr << "\n";
    }}
  }

  int get(int cvor, int l, int r, int &a, int &b, int &x) {
    if (l > b || r < a) return 0;
    if (l >= a && r <= b) return (lower_bound(all(v[cvor]), x) - v[cvor].begin());

    int mid = (l + r) / 2;
    return get(cvor * 2, l, mid, a, b, x) + get(cvor * 2 + 1, mid + 1, r, a, b, x);
  }
}T;

int n, q;

int main() {
  scanf("%d %d",&n,&q);
  REP(i, n) {
    int x;
    scanf("%d",&x);
    T.insert(i, x);
  }
  T.init();
  REP(t, q) {
    int l, r;
    scanf("%d %d",&l,&r);
    l--; r--;
    int lo = 1, hi = MAXN, mid;
    while (lo != hi) {
      mid = (lo + hi + 1) / 2;
      int x = r - l + 1 - T.get(1, 0, offset - 1, l, r, mid);
      if (x >= mid) lo = mid;
      else hi = mid - 1;
    }
    printf("%d\n",lo);
  }
  return 0;
}

Compilation message (stderr)

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

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