oj.uz

Submission #525225

# Submission time Handle Problem Language Result Execution time Memory
525225 2022-02-11T06:52:50 Z Pety Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
64 / 100
 557 ms 262148 KB 
#include <iostream>
#include<vector>
#include<algorithm>
#pragma GCC optimize("O2")
#pragma GCC optimize("Os")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("O1")
#pragma GCC optimize("O3")
#pragma GCC target("avx,avx2,fma")
 
 
using namespace std;
 
const long long N = 1e6;
long long n, m, w[N + 2], cnt, lg2[N + 2];
struct nodA {
  long long inv, st, dr;
  bool sorted;
} aint[4 * N + 2];
vector<long long>all;
long long ans = 0, mx = 0;
 
 
void build (long long nod, long long st, long long dr) {
  if (st == dr) {
    aint[nod].inv = 0;
    aint[nod].st = all.size();
    all.push_back(w[st]);
    aint[nod].dr = all.size();
    aint[nod].sorted = 1;
    return;
  }
  long long mid = (st + dr) / 2;
  build(2 * nod, st, mid);
  build(2 * nod + 1, mid + 1, dr);
  aint[nod].inv = max(aint[2 * nod].inv, aint[2 * nod + 1].inv);
  auto it = lower_bound(all.begin() + aint[2 * nod + 1].st,  all.begin() + aint[2 * nod + 1].dr, all[aint[2 * nod].dr - 1])-all.begin();
  if (it != aint[2 * nod + 1].st) {
    it--;
    aint[nod].inv = max(aint[nod].inv, all[aint[2 * nod].dr - 1] + all[it]);
  }
  aint[nod].st = all.size();
  long long i = aint[2* nod].st, j = aint[2 * nod + 1].st;
  while (i < aint[2 * nod].dr&& j < aint[2 * nod + 1].dr) {
    if (all[i] == all[j]) {
      long long x = all[i];
      all.push_back(all[i]);
      all.push_back(all[i]);
      i++;
      j++;
    }
    else if (all[i]< all[j]) {
      all.push_back(all[i]);
      i++;
    }
    else if (all[i] > all[j]) {
      all.push_back(all[j]);
      j++;
    }
  }
  while (i < aint[2 * nod].dr)
    all.push_back(all[i++]);
  while (j < aint[2 * nod + 1].dr)
    all.push_back(all[j++]);
  aint[nod].dr = all.size();
  aint[nod].sorted = (aint[2 * nod].sorted & aint[2 * nod + 1].sorted & w[mid] <= w[mid + 1]);
}
 
long long lastdr;
bool ok;
 
void query (long long nod, long long st, long long dr, long long a, long long b) {
  if (a <= st && dr <= b) {
    if (mx == -1) {
      ans = aint[nod].inv;
      mx = max(mx, all[aint[nod].dr - 1]);
      ok &= aint[nod].sorted;
      lastdr = dr;
    }
    else {
      if (n <= 200000) {
        ans = max(ans, aint[nod].inv);
        long long poz = aint[nod].st - 1;
        long long l = lg2[dr - st + 1];
        for (long long pas = (1 << (l + 1)); pas; (pas >>= 1))
          if (poz + pas < aint[nod].dr && all[poz + pas] < mx)
            poz += pas;
        if (poz != aint[nod].st - 1) {
          ans = max(ans, mx + all[poz]);
        }
      }
      ok &= aint[nod].sorted;
      ok &= (w[lastdr] <= w[lastdr + 1]);
      mx = max(mx, all[aint[nod].dr - 1]);
      lastdr = dr;
    }
    return;
  }
  long long mid = (st + dr) / 2;
  if (a <= mid)
    query(2 * nod, st, mid, a, b);
  if (b > mid)
    query(2 * nod + 1, mid + 1, dr, a, b);
}
 
int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  cin >> n >> m;
  for (long long i = 2; i <= n; i++)
    lg2[i] = lg2[i / 2] + 1;
  for (long long i = 1; i <= n; i++)
    cin >> w[i];
  build(1, 1, n);
  for (long long i = 1; i <= m; i++) {
    long long l, r, k;
    cin >> l >> r >> k;
    ans = mx = lastdr = -1;
    ok = 1;
    query(1, 1, n, l, r);
    if (n > 200000) {
      cout << ok << "\n";
    }
    else {
      cout << (ans <= k) << "\n";
    }
  }
  return 0;
}

Compilation message

sortbooks.cpp: In function 'void build(long long int, long long int, long long int)':
sortbooks.cpp:46:17: warning: unused variable 'x' [-Wunused-variable]
   46 |       long long x = all[i];
      |                 ^
sortbooks.cpp:66:80: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
   66 |   aint[nod].sorted = (aint[2 * nod].sorted & aint[2 * nod + 1].sorted & w[mid] <= w[mid + 1]);
      |                                                                         ~~~~~~~^~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 320 KB Output is correct
2 Correct 1 ms 296 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 308 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 3 ms 460 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 460 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 320 KB Output is correct
2 Correct 1 ms 296 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 308 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 3 ms 460 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 3 ms 844 KB Output is correct
12 Correct 6 ms 1608 KB Output is correct
13 Correct 4 ms 1636 KB Output is correct
14 Correct 6 ms 2252 KB Output is correct
15 Correct 9 ms 2160 KB Output is correct
16 Correct 5 ms 2124 KB Output is correct
17 Correct 8 ms 1360 KB Output is correct
18 Correct 4 ms 2096 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 384 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 26272 KB Output is correct
2 Correct 144 ms 26160 KB Output is correct
3 Correct 235 ms 26256 KB Output is correct
4 Correct 241 ms 26268 KB Output is correct
5 Correct 216 ms 26248 KB Output is correct
6 Correct 145 ms 26180 KB Output is correct
7 Correct 157 ms 26004 KB Output is correct
8 Correct 143 ms 25868 KB Output is correct
9 Correct 39 ms 1868 KB Output is correct
10 Correct 143 ms 25932 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 320 KB Output is correct
2 Correct 1 ms 296 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 308 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 3 ms 460 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 3 ms 844 KB Output is correct
12 Correct 6 ms 1608 KB Output is correct
13 Correct 4 ms 1636 KB Output is correct
14 Correct 6 ms 2252 KB Output is correct
15 Correct 9 ms 2160 KB Output is correct
16 Correct 5 ms 2124 KB Output is correct
17 Correct 8 ms 1360 KB Output is correct
18 Correct 4 ms 2096 KB Output is correct
19 Correct 471 ms 56220 KB Output is correct
20 Correct 478 ms 56228 KB Output is correct
21 Correct 375 ms 55988 KB Output is correct
22 Correct 380 ms 56012 KB Output is correct
23 Correct 334 ms 56068 KB Output is correct
24 Correct 365 ms 56028 KB Output is correct
25 Correct 355 ms 55972 KB Output is correct
26 Correct 490 ms 56168 KB Output is correct
27 Correct 453 ms 56116 KB Output is correct
28 Correct 536 ms 56092 KB Output is correct
29 Correct 484 ms 56236 KB Output is correct
30 Correct 516 ms 56232 KB Output is correct
31 Correct 544 ms 56236 KB Output is correct
32 Correct 557 ms 56172 KB Output is correct
33 Correct 523 ms 56172 KB Output is correct
34 Correct 331 ms 55788 KB Output is correct
35 Correct 360 ms 55776 KB Output is correct
36 Correct 373 ms 55620 KB Output is correct
37 Correct 351 ms 55636 KB Output is correct
38 Correct 355 ms 55760 KB Output is correct
39 Correct 384 ms 54716 KB Output is correct
40 Correct 256 ms 44488 KB Output is correct
41 Correct 350 ms 54300 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 320 KB Output is correct
2 Correct 1 ms 296 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 308 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 3 ms 460 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 3 ms 844 KB Output is correct
12 Correct 6 ms 1608 KB Output is correct
13 Correct 4 ms 1636 KB Output is correct
14 Correct 6 ms 2252 KB Output is correct
15 Correct 9 ms 2160 KB Output is correct
16 Correct 5 ms 2124 KB Output is correct
17 Correct 8 ms 1360 KB Output is correct
18 Correct 4 ms 2096 KB Output is correct
19 Runtime error 384 ms 262148 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -