/ SeriousOJ /

Record Detail

Wrong Answer


  
# Status Time Cost Memory Cost
#1 Wrong Answer 1ms 324.0 KiB
#2 Wrong Answer 1ms 328.0 KiB

Code

#include <bits/stdc++.h>
using namespace std;

struct node {
	int minimum;
	int maximum;
};
int getMid(int s, int e) { return s + (e - s) / 2; }

struct node MaxMinUntill(struct node* st, int ss, int se,
						int qs, int qe, int index)
{
	struct node tmp, left, right;
	if (qs <= ss && qe >= se)
		return st[index];

	if (se < qs || ss > qe) {
		tmp.minimum = INT_MAX;
		tmp.maximum = INT_MIN;
		return tmp;
	}

	int mid = getMid(ss, se);
	left = MaxMinUntill(st, ss, mid, qs, qe, 2 * index + 1);
	right = MaxMinUntill(st, mid + 1, se, qs, qe,
						2 * index + 2);
	tmp.minimum = min(left.minimum, right.minimum);
	tmp.maximum = max(left.maximum, right.maximum);
	return tmp;
}

struct node MaxMin(struct node* st, int n, int qs, int qe)
{
	struct node tmp;

	if (qs < 0 || qe > n - 1 || qs > qe) {
		printf("Invalid Input");
		tmp.minimum = INT_MAX;
		tmp.maximum = INT_MIN;
		return tmp;
	}

	return MaxMinUntill(st, 0, n - 1, qs, qe, 0);
}
void constructSTUtil(int arr[], int ss, int se,
					struct node* st, int si)
{
	if (ss == se) {
		st[si].minimum = arr[ss];
		st[si].maximum = arr[ss];
		return;
	}

	int mid = getMid(ss, se);
	constructSTUtil(arr, ss, mid, st, si * 2 + 1);
	constructSTUtil(arr, mid + 1, se, st, si * 2 + 2);

	st[si].minimum = min(st[si * 2 + 1].minimum,
						st[si * 2 + 2].minimum);
	st[si].maximum = max(st[si * 2 + 1].maximum,
						st[si * 2 + 2].maximum);
}

struct node* constructST(int arr[], int n)
{

	int x = (int)(ceil(log2(n)));


	int max_size = 2 * (int)pow(2, x) - 1;

	struct node* st = new struct node[max_size];


	constructSTUtil(arr, 0, n - 1, st, 0);


	return st;
}

int main()
{
    int n, k;
    cin>>n>>k;
	int arr[n];
    for(int i = 0; i < n; i++){
        cin>>arr[i];
    }
	struct node* st = constructST(arr, n);

	int qs = 0; 
	int qe = 8; 
	
    int pre[n];
    pre[0] = 0;
    for(int i = 1; i < n; i++){
        if(arr[i-1] <= arr[i])pre[i] = 0;
        else pre[i]  = 1;
        pre[i] += pre[i-1];
    }

    for(int i = k-1; i < n; i++){
        int l = i - k + 1;
        struct node result = MaxMin(st, n, l, i);
        int bc = pre[n] - pre[i];
        int ft = 0;
        if(i-1 > 0)pre[i-1];
        if(bc == 0 and ft == 0){
            if(arr[i-1] <= result.minimum){
                if(i + 1 < n){
                    if(result.maximum <= arr[i+1]){
                        cout<<"YES"<<endl;
                        cout<<l<<" "<<i<<endl;
                        return 0;
                    }
                }
                else{
                    cout<<"YES"<<endl;
                    cout<<l<<" "<<i<<endl;
                    return 0;
                }
            }
        }
    }

	return 0;
}

Information

Submit By
Type
Submission
Problem
P1120 Stairway to the Skyline
Contest
Brain Booster #7
Language
C++17 (G++ 13.2.0)
Submit At
2024-11-05 15:14:08
Judged At
2024-11-11 02:31:10
Judged By
Score
0
Total Time
1ms
Peak Memory
328.0 KiB