답안 #651228

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
651228	2022-10-18T03:17:08 Z	weakweakweak	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	13 / 100	1149 ms	14584 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];
  if(n<=5000&&m<=5000){
    while(m--){
      int l, r, k;
      cin>>l>>r>>k;
      int mx=o[l], chk=1;
      for(int i=l; i<=r; i++){
        if(o[i]<=mx&&mx+o[i]>k)chk=0;
        mx=max(mx, o[i]);}
      cout<<chk<<'\n';
    }  
  }
  else{
    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

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Incorrect	1 ms	212 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #2
0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Incorrect	1 ms	212 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #3
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1107 ms	14324 KB	Output is correct
2	Correct	1149 ms	14404 KB	Output is correct
3	Correct	1118 ms	14416 KB	Output is correct
4	Correct	998 ms	14376 KB	Output is correct
5	Correct	921 ms	14584 KB	Output is correct