Submission #156006

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
156006	2019-10-02T14:50:43 Z	ASDF123	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	13 / 100	3000 ms	26744 KB

sortbooks

#include <bits/stdc++.h>
//#define int long long
#define fr first
#define sc second
#define all(s) s.begin(), s.end()
#define szof(s) (int)s.size()
using namespace std;

const int N = (int)1e6 + 5;
const int INF = 1e9 + 7;
const int MOD = (int)1e9 + 7;

int tests = 1;
int n, l, r, k;
int a[N];


pair<int, int> tree[N * 4];
int pref[N];

void build(int v = 1, int tl = 1, int tr = N) {
  if (tl == tr) {
    tree[v].fr = a[tl];
    tree[v].sc = a[tl];
    return;
  }
  int mid = tl + tr >> 1;
  build(v + v, tl, mid);
  build(v + v + 1, mid + 1, tr);
  tree[v].fr = min(tree[v + v].fr, tree[v + v + 1].fr);
  tree[v].sc = max(tree[v + v].sc, tree[v + v + 1].sc);
}

pair<int, int> get(int l, int r, int v = 1, int tl = 1, int tr = N) {
  if (l <= tl && tr <= r) {
    return tree[v];
  }
  if (l > tr || tl > r) {
    return {INF, -INF};
  }
  int mid = tl + tr >> 1;
  pair<int, int> p1 = get(l, r, v + v, tl, mid);
  pair<int, int> p2 = get(l, r, v + v + 1, mid + 1, tr);
  return {min(p1.fr, p2.fr), max(p1.sc, p2.sc)};
}

int bad(int l, int r) {
  return pref[r - 1] - pref[l - 1];
}


void solve() {
  scanf("%d%d%d", &l, &r, &k);

  if (k < get(l, r).fr) {
    if (bad(l, r)) {
      puts("0");
    } else {
      puts("1");
    }
    return;
  }

  set <int> st;
  set <int> ::iterator it;
  bool ok = true;
  int mn = INF;

//  for (int i = r; i >= l; i--) {
//    if (i == r) {
//      st.insert(a[i]);
//      mn = min(mn, a[i]);
//      continue;
//    }
//    if (mn < a[i]) {
//      it = st.lower_bound(a[i]);
//      it--;
//      if (*it + a[i] > k) {
//        ok = false;
//        break;
//      }
//    }
//    st.insert(a[i]);
//    mn = min(mn, a[i]);
//  }

  for (int i = r; i >= l; i--) {
    int mx = get(l, max(l, i - 1)).sc;
    if (mx > a[i] && mx + a[i] > k) {
      ok = false;
      break;
    }
    int j = i;
    while (j >= 1 && a[j] >= i) {
      j--;
    }
    i = j + 1;
  }

  if (ok) {
    puts("1");
  } else {
    puts("0");
  }
}

main() {
  scanf("%d%d", &n, &tests);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
  }
  build();

  for (int i = 1; i <= n; i++) {
    pref[i] = pref[i - 1] + (a[i] > a[i + 1]);
  }

//  for (int i = 1; i <= n; i++) {
//    cout << pref[i] << " ";
//  }cout << endl;
//
//  while (1) {
//    int l, r;
//    cin >> l >> r;
//    cout << get(l, r) << endl;
//  }


  while (tests--) {
    solve();
  }
}

Compilation message

sortbooks.cpp: In function 'void build(int, int, int)':
sortbooks.cpp:27: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)':
sortbooks.cpp:41:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid = tl + tr >> 1;
             ~~~^~~~
sortbooks.cpp: In function 'void solve()':
sortbooks.cpp:67:7: warning: unused variable 'mn' [-Wunused-variable]
   int mn = INF;
       ^~
sortbooks.cpp: At global scope:
sortbooks.cpp:107:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
sortbooks.cpp: In function 'void solve()':
sortbooks.cpp:53:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &l, &r, &k);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp: In function 'int main()':
sortbooks.cpp:108:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &n, &tests);
   ~~~~~^~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:110:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &a[i]);
     ~~~~~^~~~~~~~~~~~~

Subtask #1
0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	3098 ms	16760 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	3098 ms	16760 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #3
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1491 ms	26696 KB	Output is correct
2	Correct	1502 ms	26588 KB	Output is correct
3	Correct	1520 ms	26628 KB	Output is correct
4	Correct	1526 ms	26732 KB	Output is correct
5	Correct	1454 ms	26744 KB	Output is correct