oj.uz

Submission #237461

# Submission time Handle Problem Language Result Execution time Memory
237461 2020-06-06T17:26:18 Z ASDF123 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
77 / 100
 1107 ms 262148 KB 
#include <bits/stdc++.h>
#define all(s) s.begin(), s.end()
#define pii pair<int, int>
#define fr first
#define sc second
#define pb push_back
using namespace std;

const int N = (int)1e6 + 6;
const int INF = (int)2e9 + 9;
int a[N];


struct T {
  int mx, best;
  vector <int> vec = {};
};
T tree[N * 4];
int n, Q;

void build(int v, int tl, int tr) {
  if (tl == tr) {
    tree[v].mx = a[tl];
    tree[v].vec = {a[tl]};
    tree[v].best = 0;
    return;
  }
  int mid = tl + tr >> 1;
  build(v + v, tl, mid);
  build(v + v + 1, mid + 1, tr);
  merge(tree[v + v].vec.begin(), tree[v + v].vec.end(), tree[v + v + 1].vec.begin(), tree[v + v + 1].vec.end(), back_inserter(tree[v].vec));
  tree[v].mx = max(tree[v + v].mx, tree[v + v + 1].mx);
  tree[v].best = max(tree[v + v].best, tree[v + v + 1].best);
  int another = 0;
  if (tree[v + v].mx > tree[v + v + 1].vec[0]) {
    another = tree[v + v].mx + *(--lower_bound(all(tree[v + v + 1].vec), tree[v + v].mx));
  }
  tree[v].best = max(tree[v].best, another);
}

pii get(int l, int r, int v = 1, int tl = 1, int tr = n, int Curmx = 0) { // best / maximum in l...r
  if (l > tr || tl > r) {
    return {0, 0};
  }
  if (l <= tl && tr <= r) {
    int another = 0;
    if (tree[v].vec[0] < Curmx) {
      another = Curmx + *(--lower_bound(all(tree[v].vec), Curmx));
    }
    return {max(tree[v].best, another), tree[v].mx};
  }
  int mid = tl + tr >> 1;
  int ans = 0;
  pii q1 = get(l, r, v + v, tl, mid, Curmx);
  pii q2 = get(l, r, v + v + 1, mid + 1, tr, max(Curmx, q1.sc));
  return {max(q1.fr, q2.fr), max(q1.sc, q2.sc)};
}

void subtask3(vector <pair<pii, int>> query) {
  bool ok = 1;
  int mn = INF;
  for (int i = 1; i <= n; i++) {
    mn = min(mn, a[i]);
  }

  for (auto c : query) {
    ok &= (c.sc < mn);
  }
  if (ok) {
    vector <int> pref(n + 5, 0);
    a[n + 1] = 2e9 + 9;
    for (int i = 1; i <= n; i++) {
      pref[i] = pref[i - 1];
      if (a[i] > a[i + 1]) {
        pref[i]++;
      }
    }
    for (auto c : query) {
      int l = c.fr.fr, r = c.fr.sc, k = c.sc;
      if (l == r) {
        puts("1");
      } else {
        if (pref[r - 1] - pref[l - 1]) {
          puts("0");
        } else {
          puts("1");
        }
      }
    }
    exit(0);
  } else {
    return;
  }
}

main() {
  cin >> n >> Q;
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
  }
  vector <pair<pii, int>> query;
  while (Q--) {
    int l, r, k;
    scanf("%d %d %d", &l, &r, &k);
    query.pb({{l, r}, k});
  }
  subtask3(query);

  build(1, 1, n);
  for (auto c : query) {
    if (get(c.fr.fr, c.fr.sc).fr <= c.sc) {
      puts("1");
    } else {
      puts("0");
    }
  }
}

Compilation message

sortbooks.cpp: In function 'void build(int, int, int)':
sortbooks.cpp:28:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid = tl + tr >> 1;
             ~~~^~~~
sortbooks.cpp: In function 'std::pair<int, int> get(int, int, int, int, int, int)':
sortbooks.cpp:52:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid = tl + tr >> 1;
             ~~~^~~~
sortbooks.cpp:53:7: warning: unused variable 'ans' [-Wunused-variable]
   int ans = 0;
       ^~~
sortbooks.cpp: In function 'void subtask3(std::vector<std::pair<std::pair<int, int>, int> >)':
sortbooks.cpp:79:37: warning: unused variable 'k' [-Wunused-variable]
       int l = c.fr.fr, r = c.fr.sc, k = c.sc;
                                     ^
sortbooks.cpp: At global scope:
sortbooks.cpp:96:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
sortbooks.cpp: In function 'int main()':
sortbooks.cpp:99:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &a[i]);
     ~~~~~^~~~~~~~~~~~~
sortbooks.cpp:104:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &l, &r, &k);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 125560 KB Output is correct
2 Correct 76 ms 125560 KB Output is correct
3 Correct 75 ms 125660 KB Output is correct
4 Correct 74 ms 125560 KB Output is correct
5 Correct 73 ms 125564 KB Output is correct
6 Correct 76 ms 125688 KB Output is correct
7 Correct 75 ms 125560 KB Output is correct
8 Correct 74 ms 125560 KB Output is correct
9 Correct 77 ms 125560 KB Output is correct
10 Correct 75 ms 125560 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 125560 KB Output is correct
2 Correct 76 ms 125560 KB Output is correct
3 Correct 75 ms 125660 KB Output is correct
4 Correct 74 ms 125560 KB Output is correct
5 Correct 73 ms 125564 KB Output is correct
6 Correct 76 ms 125688 KB Output is correct
7 Correct 75 ms 125560 KB Output is correct
8 Correct 74 ms 125560 KB Output is correct
9 Correct 77 ms 125560 KB Output is correct
10 Correct 75 ms 125560 KB Output is correct
11 Correct 76 ms 125816 KB Output is correct
12 Correct 81 ms 126328 KB Output is correct
13 Correct 83 ms 126328 KB Output is correct
14 Correct 82 ms 126456 KB Output is correct
15 Correct 81 ms 126456 KB Output is correct
16 Correct 83 ms 126468 KB Output is correct
17 Correct 80 ms 126200 KB Output is correct
18 Correct 80 ms 126328 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 761 ms 163624 KB Output is correct
2 Correct 769 ms 163316 KB Output is correct
3 Correct 769 ms 163364 KB Output is correct
4 Correct 774 ms 163496 KB Output is correct
5 Correct 744 ms 163428 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 321 ms 140880 KB Output is correct
2 Correct 286 ms 140880 KB Output is correct
3 Correct 243 ms 140880 KB Output is correct
4 Correct 257 ms 140880 KB Output is correct
5 Correct 249 ms 140888 KB Output is correct
6 Correct 204 ms 140880 KB Output is correct
7 Correct 206 ms 140752 KB Output is correct
8 Correct 241 ms 140880 KB Output is correct
9 Correct 118 ms 127980 KB Output is correct
10 Correct 236 ms 140844 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 125560 KB Output is correct
2 Correct 76 ms 125560 KB Output is correct
3 Correct 75 ms 125660 KB Output is correct
4 Correct 74 ms 125560 KB Output is correct
5 Correct 73 ms 125564 KB Output is correct
6 Correct 76 ms 125688 KB Output is correct
7 Correct 75 ms 125560 KB Output is correct
8 Correct 74 ms 125560 KB Output is correct
9 Correct 77 ms 125560 KB Output is correct
10 Correct 75 ms 125560 KB Output is correct
11 Correct 76 ms 125816 KB Output is correct
12 Correct 81 ms 126328 KB Output is correct
13 Correct 83 ms 126328 KB Output is correct
14 Correct 82 ms 126456 KB Output is correct
15 Correct 81 ms 126456 KB Output is correct
16 Correct 83 ms 126468 KB Output is correct
17 Correct 80 ms 126200 KB Output is correct
18 Correct 80 ms 126328 KB Output is correct
19 Correct 662 ms 156984 KB Output is correct
20 Correct 641 ms 156988 KB Output is correct
21 Correct 537 ms 156856 KB Output is correct
22 Correct 534 ms 156964 KB Output is correct
23 Correct 537 ms 157020 KB Output is correct
24 Correct 391 ms 156848 KB Output is correct
25 Correct 380 ms 156856 KB Output is correct
26 Correct 459 ms 156984 KB Output is correct
27 Correct 467 ms 156984 KB Output is correct
28 Correct 500 ms 156984 KB Output is correct
29 Correct 491 ms 156856 KB Output is correct
30 Correct 495 ms 156856 KB Output is correct
31 Correct 476 ms 156848 KB Output is correct
32 Correct 497 ms 157104 KB Output is correct
33 Correct 496 ms 156856 KB Output is correct
34 Correct 360 ms 156848 KB Output is correct
35 Correct 363 ms 156856 KB Output is correct
36 Correct 360 ms 157104 KB Output is correct
37 Correct 363 ms 156856 KB Output is correct
38 Correct 365 ms 156856 KB Output is correct
39 Correct 456 ms 156856 KB Output is correct
40 Correct 315 ms 144824 KB Output is correct
41 Correct 439 ms 156992 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 125560 KB Output is correct
2 Correct 76 ms 125560 KB Output is correct
3 Correct 75 ms 125660 KB Output is correct
4 Correct 74 ms 125560 KB Output is correct
5 Correct 73 ms 125564 KB Output is correct
6 Correct 76 ms 125688 KB Output is correct
7 Correct 75 ms 125560 KB Output is correct
8 Correct 74 ms 125560 KB Output is correct
9 Correct 77 ms 125560 KB Output is correct
10 Correct 75 ms 125560 KB Output is correct
11 Correct 76 ms 125816 KB Output is correct
12 Correct 81 ms 126328 KB Output is correct
13 Correct 83 ms 126328 KB Output is correct
14 Correct 82 ms 126456 KB Output is correct
15 Correct 81 ms 126456 KB Output is correct
16 Correct 83 ms 126468 KB Output is correct
17 Correct 80 ms 126200 KB Output is correct
18 Correct 80 ms 126328 KB Output is correct
19 Correct 761 ms 163624 KB Output is correct
20 Correct 769 ms 163316 KB Output is correct
21 Correct 769 ms 163364 KB Output is correct
22 Correct 774 ms 163496 KB Output is correct
23 Correct 744 ms 163428 KB Output is correct
24 Correct 321 ms 140880 KB Output is correct
25 Correct 286 ms 140880 KB Output is correct
26 Correct 243 ms 140880 KB Output is correct
27 Correct 257 ms 140880 KB Output is correct
28 Correct 249 ms 140888 KB Output is correct
29 Correct 204 ms 140880 KB Output is correct
30 Correct 206 ms 140752 KB Output is correct
31 Correct 241 ms 140880 KB Output is correct
32 Correct 118 ms 127980 KB Output is correct
33 Correct 236 ms 140844 KB Output is correct
34 Correct 662 ms 156984 KB Output is correct
35 Correct 641 ms 156988 KB Output is correct
36 Correct 537 ms 156856 KB Output is correct
37 Correct 534 ms 156964 KB Output is correct
38 Correct 537 ms 157020 KB Output is correct
39 Correct 391 ms 156848 KB Output is correct
40 Correct 380 ms 156856 KB Output is correct
41 Correct 459 ms 156984 KB Output is correct
42 Correct 467 ms 156984 KB Output is correct
43 Correct 500 ms 156984 KB Output is correct
44 Correct 491 ms 156856 KB Output is correct
45 Correct 495 ms 156856 KB Output is correct
46 Correct 476 ms 156848 KB Output is correct
47 Correct 497 ms 157104 KB Output is correct
48 Correct 496 ms 156856 KB Output is correct
49 Correct 360 ms 156848 KB Output is correct
50 Correct 363 ms 156856 KB Output is correct
51 Correct 360 ms 157104 KB Output is correct
52 Correct 363 ms 156856 KB Output is correct
53 Correct 365 ms 156856 KB Output is correct
54 Correct 456 ms 156856 KB Output is correct
55 Correct 315 ms 144824 KB Output is correct
56 Correct 439 ms 156992 KB Output is correct
57 Runtime error 1107 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
58 Halted 0 ms 0 KB -