oj.uz

Submission #536563

# Submission time Handle Problem Language Result Execution time Memory
536563 2022-03-13T14:20:09 Z cig32 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
47 / 100
 532 ms 164104 KB 
#include "bits/stdc++.h"
using namespace std;
const int MAXN = 1e6 + 10;
const int MOD = 1e9 + 7;
 
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x, int y) {
  int u = uniform_int_distribution<int>(x, y)(rng); return u;
}
 
struct node {
  int ans; // maximum sum inversion in range
  vector<int> v; // SORTED!!! crazy memory moment
} st[4*MAXN];
int n, m;
vector<int> v[MAXN];
void bu(int l, int r, int idx) {
  v[l].push_back(idx);
  st[idx].v.resize(r-l+1);
  if(l == r) {
    int w;
    cin >> w;
    st[idx].v[0] = w;
    st[idx].ans = -1;
    return;
  }
  int mid = (l + r) >> 1;
  bu(l, mid, 2*idx + 1);
  bu(mid+1, r, 2*idx + 2);
  int lptr = 0, rptr = 0;
  int nxt = 0;
  while(!(lptr == st[2*idx + 1].v.size() && rptr == st[2*idx + 2].v.size())) {
    if(lptr == st[2*idx+1].v.size()) {
      st[idx].v[nxt] = st[2*idx+2].v[rptr];
      rptr++;
      nxt++;
    }
    else if(rptr == st[2*idx+2].v.size()) {
      st[idx].v[nxt] = st[2*idx+1].v[lptr];
      lptr++;
      nxt++;
    }
    else {
      if(st[2*idx+1].v[lptr] < st[2*idx+2].v[rptr]) {
        st[idx].v[nxt] = st[2*idx+1].v[lptr];
        lptr++;
        nxt++;
      }
      else {
        st[idx].v[nxt] = st[2*idx+2].v[rptr];
        rptr++;
        nxt++;
      }
    }
  }
  st[idx].ans = max(st[2*idx+1].ans, st[2*idx+2].ans);
  int ma = st[2*idx+1].v[st[2*idx+1].v.size() - 1];
  int lb = 0, rb = st[2*idx+2].v.size() - 1;
  while(lb < rb) {
    int mid = (lb + rb + 1) >> 1;
    if(st[2*idx+2].v[mid] < ma) lb = mid;
    else rb = mid - 1;
  }
  if(st[2*idx+2].v[lb] < ma) {
    st[idx].ans = max(st[idx].ans, st[2*idx+2].v[lb] + ma);
  }
}
 
void build() {
  bu(1, n, 0);
}

int calc(int idx1) {
  return st[idx1].v.size() - 1;
}
bool cmp(int a, int b) {
  return calc(a) < calc(b);
}
void solve(int tc) {
  cin >> n >> m;
  if(n >= 200000) {
    int s[n+1];
    for(int i=1; i<=n; i++) cin >> s[i];
    int ps[n+1];
    ps[0] = 0;
    for(int i=1; i<=n; i++) ps[i] = ps[i-1] + (s[i] > s[i+1]);
    for(int i=0; i<m; i++) {
      int l, r, k;
      cin >> l >> r >> k;
      cout << (ps[r-1] - ps[l-1] > 0 ? "0\n" : "1\n");
    }
    return;
  }
  build();
  for(int i=1; i<=n; i++) sort(v[i].begin(), v[i].end(), cmp);
  for(int i=0; i<m; i++) {
    int l, r, k;
    cin >> l >> r >> k;
    int ma = -2e9;
    int ans = -2e9;
    while(l <= r) {
      int lb = 0, rb = v[l].size() - 1;
      while(lb < rb) {
        int mid = (lb + rb + 1) >> 1;
        int idx1 = v[l][mid];
        int range = l + st[idx1].v.size() - 1;
        if(range <= r) lb = mid;
        else rb = mid - 1;
      }
      int idx = v[l][lb];
      ans = max(ans, st[idx].ans);
      int lb2 = 0, rb2 = st[idx].v.size() - 1;
      while(lb2 < rb2) {
        int mid = (lb2 + rb2 + 1) >> 1;
        if(st[idx].v[mid] < ma) lb2 = mid;
        else rb2 = mid - 1;
      }
      if(st[idx].v[lb2] < ma) ans = max(ans, ma + st[idx].v[lb2]);
      ma = max(ma, st[idx].v[st[idx].v.size() - 1]);
      int idx1 = v[l][lb];
      int range = l + st[idx1].v.size() - 1;
      l = range + 1;
    }
    cout << (ans > k ? "0\n" : "1\n");
  }
}
int32_t main(){
  ios::sync_with_stdio(0); cin.tie(0);
  int t = 1; //cin >> t;
  for(int i=1; i<=t; i++) solve(i);
}

Compilation message

sortbooks.cpp: In function 'void bu(int, int, int)':
sortbooks.cpp:32:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |   while(!(lptr == st[2*idx + 1].v.size() && rptr == st[2*idx + 2].v.size())) {
      |           ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:32:50: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |   while(!(lptr == st[2*idx + 1].v.size() && rptr == st[2*idx + 2].v.size())) {
      |                                             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:33:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |     if(lptr == st[2*idx+1].v.size()) {
      |        ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:38:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     else if(rptr == st[2*idx+2].v.size()) {
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 149004 KB Output is correct
2 Correct 76 ms 149012 KB Output is correct
3 Correct 68 ms 149052 KB Output is correct
4 Correct 71 ms 148928 KB Output is correct
5 Correct 76 ms 149056 KB Output is correct
6 Correct 74 ms 149052 KB Output is correct
7 Correct 71 ms 149248 KB Output is correct
8 Correct 70 ms 148976 KB Output is correct
9 Correct 75 ms 149004 KB Output is correct
10 Correct 80 ms 149052 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 149004 KB Output is correct
2 Correct 76 ms 149012 KB Output is correct
3 Correct 68 ms 149052 KB Output is correct
4 Correct 71 ms 148928 KB Output is correct
5 Correct 76 ms 149056 KB Output is correct
6 Correct 74 ms 149052 KB Output is correct
7 Correct 71 ms 149248 KB Output is correct
8 Correct 70 ms 148976 KB Output is correct
9 Correct 75 ms 149004 KB Output is correct
10 Correct 80 ms 149052 KB Output is correct
11 Correct 74 ms 149220 KB Output is correct
12 Correct 78 ms 149656 KB Output is correct
13 Correct 77 ms 149552 KB Output is correct
14 Correct 77 ms 149640 KB Output is correct
15 Correct 88 ms 149692 KB Output is correct
16 Correct 79 ms 149576 KB Output is correct
17 Correct 77 ms 149576 KB Output is correct
18 Correct 78 ms 149792 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 503 ms 158868 KB Output is correct
2 Correct 473 ms 158832 KB Output is correct
3 Correct 495 ms 158876 KB Output is correct
4 Correct 507 ms 158792 KB Output is correct
5 Correct 532 ms 158768 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 400 ms 163976 KB Output is correct
2 Correct 302 ms 164076 KB Output is correct
3 Correct 394 ms 164104 KB Output is correct
4 Correct 366 ms 164004 KB Output is correct
5 Correct 348 ms 163908 KB Output is correct
6 Correct 310 ms 164056 KB Output is correct
7 Correct 247 ms 163932 KB Output is correct
8 Correct 298 ms 164020 KB Output is correct
9 Correct 112 ms 149260 KB Output is correct
10 Correct 280 ms 164068 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 149004 KB Output is correct
2 Correct 76 ms 149012 KB Output is correct
3 Correct 68 ms 149052 KB Output is correct
4 Correct 71 ms 148928 KB Output is correct
5 Correct 76 ms 149056 KB Output is correct
6 Correct 74 ms 149052 KB Output is correct
7 Correct 71 ms 149248 KB Output is correct
8 Correct 70 ms 148976 KB Output is correct
9 Correct 75 ms 149004 KB Output is correct
10 Correct 80 ms 149052 KB Output is correct
11 Correct 74 ms 149220 KB Output is correct
12 Correct 78 ms 149656 KB Output is correct
13 Correct 77 ms 149552 KB Output is correct
14 Correct 77 ms 149640 KB Output is correct
15 Correct 88 ms 149692 KB Output is correct
16 Correct 79 ms 149576 KB Output is correct
17 Correct 77 ms 149576 KB Output is correct
18 Correct 78 ms 149792 KB Output is correct
19 Incorrect 159 ms 150960 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 149004 KB Output is correct
2 Correct 76 ms 149012 KB Output is correct
3 Correct 68 ms 149052 KB Output is correct
4 Correct 71 ms 148928 KB Output is correct
5 Correct 76 ms 149056 KB Output is correct
6 Correct 74 ms 149052 KB Output is correct
7 Correct 71 ms 149248 KB Output is correct
8 Correct 70 ms 148976 KB Output is correct
9 Correct 75 ms 149004 KB Output is correct
10 Correct 80 ms 149052 KB Output is correct
11 Correct 74 ms 149220 KB Output is correct
12 Correct 78 ms 149656 KB Output is correct
13 Correct 77 ms 149552 KB Output is correct
14 Correct 77 ms 149640 KB Output is correct
15 Correct 88 ms 149692 KB Output is correct
16 Correct 79 ms 149576 KB Output is correct
17 Correct 77 ms 149576 KB Output is correct
18 Correct 78 ms 149792 KB Output is correct
19 Correct 503 ms 158868 KB Output is correct
20 Correct 473 ms 158832 KB Output is correct
21 Correct 495 ms 158876 KB Output is correct
22 Correct 507 ms 158792 KB Output is correct
23 Correct 532 ms 158768 KB Output is correct
24 Correct 400 ms 163976 KB Output is correct
25 Correct 302 ms 164076 KB Output is correct
26 Correct 394 ms 164104 KB Output is correct
27 Correct 366 ms 164004 KB Output is correct
28 Correct 348 ms 163908 KB Output is correct
29 Correct 310 ms 164056 KB Output is correct
30 Correct 247 ms 163932 KB Output is correct
31 Correct 298 ms 164020 KB Output is correct
32 Correct 112 ms 149260 KB Output is correct
33 Correct 280 ms 164068 KB Output is correct
34 Incorrect 159 ms 150960 KB Output isn't correct
35 Halted 0 ms 0 KB -