Submission #651220

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
651220	2022-10-18T03:13:28 Z	weakweakweak	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	13 / 100	1160 ms	14852 KB

sortbooks

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")

const int MXN=1010000;
int n, m, o[MXN];

struct seg1{
  int a[MXN*4];
  int f(int i, int j){return min(i, j);}
  void build(int l, int r, int id){
    if(l==r){a[id]=o[l]; return;}
    int mid=(l+r)/2;
    build(l, mid, id*2); build(mid+1, r, id*2+1);
    a[id]=f(a[id*2], a[id*2+1]);}
  int query(int l, int r, int ql, int qr ,int id){
    if(ql<=l&&r<=qr)return a[id];
    int res=INT_MAX, mid=(l+r)/2;
    if(ql<=mid)res=f(res, query(l, mid, ql, qr, id*2));
    if(qr>mid)res=f(res, query(mid+1, r, ql, qr, id*2+1));
    return res;}
}s1;

int main(){
  ios_base::sync_with_stdio(false); cin.tie(0);
  cin>>n>>m;
  for(int i=1; i<=n; i++)cin>>o[i];
  
    for(int i=1; i<=n; i++)o[i]=o[i+1]-o[i];
    s1.build(1, n-1, 1);
    while(m--){
      int l, r, k;
      cin>>l>>r>>k;
      if(l==r){cout<<1<<'\n'; continue;}
      int x=s1.query(1, n-1, l, r-1, 1);
      if(x<0)cout<<0<<'\n';
      else cout<<1<<'\n';}
return 0;}

Subtask #1
0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	0 ms	212 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	0 ms	212 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #3
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1016 ms	14560 KB	Output is correct
2	Correct	1037 ms	14552 KB	Output is correct
3	Correct	1160 ms	14460 KB	Output is correct
4	Correct	1018 ms	14584 KB	Output is correct
5	Correct	956 ms	14852 KB	Output is correct