Submission #386349

#	Time	Username	Problem	Language	Result	Execution time	Memory
386349		model_code	Index (COCI21_index)	C++17	60 / 110	2584 ms	37772 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]));
  }

  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:51:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   51 |   scanf("%d %d",&n,&q);
      |   ~~~~~^~~~~~~~~~~~~~~
index.cpp:54:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   54 |     scanf("%d",&x);
      |     ~~~~~^~~~~~~~~
index.cpp:60:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   60 |     scanf("%d %d",&l,&r);
      |     ~~~~~^~~~~~~~~~~~~~~

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