Submission #1177580

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177580		faiaratto	Index (COCI21_index)	C++20	110 / 110	943 ms	147992 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 = 200001;

struct node {
	int x;
  node* l;
  node* r;

  node (int y = 0,node *L = 0, node *R = 0) {
    x = y;
    l = L;
    r = R;
  }
};

node* nil() {
  node *x = new node();
  x -> r = x -> l = x;
  return x;
}

const int offset = (1 << 18);

int n, q, p[MAXN];
node* root[MAXN];
node* tmp;

vector <int> v;

node* update(node* cvor, int lo,int hi, int x) {
  if (x < lo || x > hi) return cvor;
  if (lo == hi && lo == x) return new node (cvor -> x + 1, nil(), nil());

  node* left;
  node* right;
  int mid = (lo + hi) / 2;

  left = update(cvor -> l, lo, mid, x);
  right = update(cvor -> r, mid + 1, hi, x);

  return new node (left -> x + right -> x, left, right);
}

int query(node *cvor, node* cvor1, int lo, int hi, int x) {
  if (hi < x || lo >= MAXN) return 0;
  if (lo >= x) return cvor -> x - cvor1 -> x;

  int mid = (lo + hi) >> 1;

  int ret = 0;
  ret += query(cvor -> l, cvor1 -> l, lo, mid, x);
  ret += query(cvor -> r, cvor1 -> r, mid + 1, hi, x);
  return ret;
}

int main() {
  scanf("%d %d",&n,&q);

	for (int i = 0;i < n; i++) {
    scanf("%d",&p[i]);
		tmp = nil();
		if (i) tmp = root[i - 1];
		root[i] = update(tmp, 0, offset - 1, p[i]);
	}

	for (int i = 0; i < q; i++) {
    int A, B;
		scanf("%d %d",&A,&B);
		A--; B--;
		tmp = nil();
    int lo = 0, hi = MAXN, mid;
    while (lo != hi) {
      mid = (lo + hi + 1) / 2;
		  if (A) tmp = root[A - 1];
		  int t = query(root[B], tmp, 0, offset - 1, mid);
      if (t >= mid) lo = mid;
      else hi = mid - 1;
    }
    printf("%d\n",lo);
	}
  return 0;
}

Compilation message (stderr)

index.cpp: In function 'int main()':
index.cpp:76:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |   scanf("%d %d",&n,&q);
      |   ~~~~~^~~~~~~~~~~~~~~
index.cpp:79:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |     scanf("%d",&p[i]);
      |     ~~~~~^~~~~~~~~~~~
index.cpp:87:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |                 scanf("%d %d",&A,&B);
      |                 ~~~~~^~~~~~~~~~~~~~~

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