oj.uz

Submission #440134

# Submission time Handle Problem Language Result Execution time Memory
440134 2021-07-01T16:03:34 Z FatihSolak Index (COCI21_index) C++17
110 / 110
 1665 ms 151840 KB 
#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

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:8: 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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 972 KB Output is correct
2 Correct 4 ms 972 KB Output is correct
3 Correct 5 ms 972 KB Output is correct
4 Correct 4 ms 972 KB Output is correct
5 Correct 4 ms 972 KB Output is correct
6 Correct 5 ms 972 KB Output is correct
7 Correct 4 ms 972 KB Output is correct
8 Correct 4 ms 972 KB Output is correct
9 Correct 4 ms 972 KB Output is correct
10 Correct 4 ms 1028 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 972 KB Output is correct
2 Correct 4 ms 972 KB Output is correct
3 Correct 5 ms 972 KB Output is correct
4 Correct 4 ms 972 KB Output is correct
5 Correct 4 ms 972 KB Output is correct
6 Correct 5 ms 972 KB Output is correct
7 Correct 4 ms 972 KB Output is correct
8 Correct 4 ms 972 KB Output is correct
9 Correct 4 ms 972 KB Output is correct
10 Correct 4 ms 1028 KB Output is correct
11 Correct 283 ms 37188 KB Output is correct
12 Correct 265 ms 37060 KB Output is correct
13 Correct 271 ms 37136 KB Output is correct
14 Correct 280 ms 37168 KB Output is correct
15 Correct 269 ms 37136 KB Output is correct
16 Correct 273 ms 37292 KB Output is correct
17 Correct 274 ms 37136 KB Output is correct
18 Correct 295 ms 37188 KB Output is correct
19 Correct 280 ms 37120 KB Output is correct
20 Correct 272 ms 37152 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 972 KB Output is correct
2 Correct 4 ms 972 KB Output is correct
3 Correct 5 ms 972 KB Output is correct
4 Correct 4 ms 972 KB Output is correct
5 Correct 4 ms 972 KB Output is correct
6 Correct 5 ms 972 KB Output is correct
7 Correct 4 ms 972 KB Output is correct
8 Correct 4 ms 972 KB Output is correct
9 Correct 4 ms 972 KB Output is correct
10 Correct 4 ms 1028 KB Output is correct
11 Correct 283 ms 37188 KB Output is correct
12 Correct 265 ms 37060 KB Output is correct
13 Correct 271 ms 37136 KB Output is correct
14 Correct 280 ms 37168 KB Output is correct
15 Correct 269 ms 37136 KB Output is correct
16 Correct 273 ms 37292 KB Output is correct
17 Correct 274 ms 37136 KB Output is correct
18 Correct 295 ms 37188 KB Output is correct
19 Correct 280 ms 37120 KB Output is correct
20 Correct 272 ms 37152 KB Output is correct
21 Correct 1665 ms 147960 KB Output is correct
22 Correct 1620 ms 151600 KB Output is correct
23 Correct 1589 ms 151472 KB Output is correct
24 Correct 1624 ms 151664 KB Output is correct
25 Correct 1614 ms 151596 KB Output is correct
26 Correct 1622 ms 151688 KB Output is correct
27 Correct 1641 ms 151840 KB Output is correct
28 Correct 1658 ms 151688 KB Output is correct
29 Correct 1621 ms 151572 KB Output is correct
30 Correct 1665 ms 151672 KB Output is correct