Submission #345697

#	Time	Username	Problem	Language	Result	Execution time	Memory
345697		Matteo_Verz	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	0 / 100	1516 ms	53484 KiB

sortbooks

/*
                `-/oo+/-   ``
              .oyhhhhhhyo.`od
             +hhhhyyoooos. h/
            +hhyso++oosy- /s
           .yoooossyyo:``-y`
            ..----.` ``.-/+:.`
                   `````..-::/.
                  `..```.-::///`
                 `-.....--::::/:
                `.......--::////:
               `...`....---:::://:
             `......``..--:::::///:`
            `---.......--:::::////+/`
            ----------::::::/::///++:
            ----:---:::::///////////:`
            .----::::::////////////:-`
            `----::::::::::/::::::::-
             `.-----:::::::::::::::-
               ...----:::::::::/:-`
                 `.---::/+osss+:`
                   ``.:://///-.
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <stack>
#include <queue>
#include <bitset>
#include <random>
#include <deque>
#include <set>
#include <map>
#include <cmath>
#define debug(x) cerr << #x << " " << x << '\n'
#define debugsp(x) cerr << #x << " " << x << ' '

using namespace std;

const int INF = 2e9;
const int N = 1e6;

int n;
int v[1 + N];

class SegTree {
  private:
    struct Node {
      int diff, minv, maxv;

      Node() {
        diff = maxv = minv = 0;
      } 
    };
    
    vector <Node> a;

    Node Query (int node, int l, int r, int x, int y) {
      if(x <= l && r <= y) return a[node];
      
      int mid = (l + r) >> 1;
      if(x <= mid && y <= mid) return Query(node << 1, l, mid, x, y);
      else if(x > mid && y > mid) return Query(node << 1 | 1, mid + 1, r, x, y);
      else {
        Node ansl, ansr, ans;
        ansl = Query(node << 1, l, mid, x, mid);
        ansr = Query(node << 1 | 1, mid + 1, r, mid + 1, y);

        ans.maxv = max(ansl.maxv, ansr.maxv);
        ans.minv = min(ansl.minv, ansr.minv);
        ans.diff = max(ansl.diff, ansr.diff);

        if(ansr.minv <= ansl.maxv) 
          ans.diff = max(ans.diff, ansl.maxv + ansr.minv);

        return ans;
      }
    }

  public:
    SegTree(int n) {
      a.resize(1 + 4 * n);
    }

    void Build(int node, int l, int r) {
      if(l == r) {
        a[node].diff = 0;
        a[node].minv = a[node].maxv = v[l];
      }
      else {
        int mid = (l + r) >> 1;
        Build(node << 1, l, mid);
        Build(node << 1 | 1, mid + 1, r);
        
        a[node].maxv = max(a[node << 1].maxv, a[node << 1 | 1].maxv);
        a[node].minv = min(a[node << 1].minv, a[node << 1 | 1].minv);
        a[node].diff = max(a[node << 1].diff, a[node << 1 | 1].diff);
        if(a[node << 1].maxv >= a[node << 1 | 1].minv)
          a[node].diff = max(a[node].diff, a[node << 1].maxv + a[node << 1 | 1].minv); 
      }
    }
    
    bool _Query(int node, int l, int r, int x, int y, int mood) {
      return (Query(node, l, r, x, y).diff <= mood);
    }
};

int main() {
  int q;
  scanf("%d%d", &n, &q);
    
  SegTree aint(n);
  for(int i = 1; i <= n; i++) 
    scanf("%d", &v[i]);
  
  aint.Build(1, 1, n);

  while(q--) {
    int x, y, m;
    scanf("%d%d%d", &x, &y, &m);
    printf("%d\n", aint._Query(1, 1, n, x, y, m));
  }
  return 0;
}

Compilation message (stderr)

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:112:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  112 |   scanf("%d%d", &n, &q);
      |   ~~~~~^~~~~~~~~~~~~~~~
sortbooks.cpp:116:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  116 |     scanf("%d", &v[i]);
      |     ~~~~~^~~~~~~~~~~~~
sortbooks.cpp:122:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  122 |     scanf("%d%d%d", &x, &y, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 8
• Subtask 2: 0 / 9
• Subtask 3: 0 / 13
• Subtask 4: 0 / 17
• Subtask 5: 0 / 30
• Subtask 6: 0 / 23