oj.uz

Submission #422035

# Submission time Handle Problem Language Result Execution time Memory
422035 2021-06-09T15:32:21 Z Chaska Index (COCI21_index) C++11
60 / 110
 2500 ms 40580 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 = 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

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

# Verdict Execution time Memory Grader output
1 Correct 15 ms 12740 KB Output is correct
2 Correct 15 ms 12620 KB Output is correct
3 Correct 16 ms 12664 KB Output is correct
4 Correct 15 ms 12732 KB Output is correct
5 Correct 15 ms 12620 KB Output is correct
6 Correct 15 ms 12744 KB Output is correct
7 Correct 16 ms 12736 KB Output is correct
8 Correct 15 ms 12740 KB Output is correct
9 Correct 15 ms 12740 KB Output is correct
10 Correct 15 ms 12748 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 12740 KB Output is correct
2 Correct 15 ms 12620 KB Output is correct
3 Correct 16 ms 12664 KB Output is correct
4 Correct 15 ms 12732 KB Output is correct
5 Correct 15 ms 12620 KB Output is correct
6 Correct 15 ms 12744 KB Output is correct
7 Correct 16 ms 12736 KB Output is correct
8 Correct 15 ms 12740 KB Output is correct
9 Correct 15 ms 12740 KB Output is correct
10 Correct 15 ms 12748 KB Output is correct
11 Correct 800 ms 19708 KB Output is correct
12 Correct 862 ms 19716 KB Output is correct
13 Correct 813 ms 19728 KB Output is correct
14 Correct 797 ms 19824 KB Output is correct
15 Correct 816 ms 19856 KB Output is correct
16 Correct 799 ms 19740 KB Output is correct
17 Correct 806 ms 19876 KB Output is correct
18 Correct 842 ms 19844 KB Output is correct
19 Correct 802 ms 19676 KB Output is correct
20 Correct 798 ms 19916 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 12740 KB Output is correct
2 Correct 15 ms 12620 KB Output is correct
3 Correct 16 ms 12664 KB Output is correct
4 Correct 15 ms 12732 KB Output is correct
5 Correct 15 ms 12620 KB Output is correct
6 Correct 15 ms 12744 KB Output is correct
7 Correct 16 ms 12736 KB Output is correct
8 Correct 15 ms 12740 KB Output is correct
9 Correct 15 ms 12740 KB Output is correct
10 Correct 15 ms 12748 KB Output is correct
11 Correct 800 ms 19708 KB Output is correct
12 Correct 862 ms 19716 KB Output is correct
13 Correct 813 ms 19728 KB Output is correct
14 Correct 797 ms 19824 KB Output is correct
15 Correct 816 ms 19856 KB Output is correct
16 Correct 799 ms 19740 KB Output is correct
17 Correct 806 ms 19876 KB Output is correct
18 Correct 842 ms 19844 KB Output is correct
19 Correct 802 ms 19676 KB Output is correct
20 Correct 798 ms 19916 KB Output is correct
21 Execution timed out 2585 ms 40580 KB Time limit exceeded
22 Halted 0 ms 0 KB -