/ SeriousOJ /

Record Detail

Wrong Answer


  
# Status Time Cost Memory Cost
#1 Accepted 2ms 528.0 KiB
#2 Accepted 2ms 540.0 KiB
#3 Accepted 2ms 332.0 KiB
#4 Accepted 2ms 512.0 KiB
#5 Accepted 2ms 528.0 KiB
#6 Wrong Answer 2ms 492.0 KiB
#7 Accepted 2ms 332.0 KiB
#8 Wrong Answer 2ms 480.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];
    }
    if(k >= n){
        cout<<"YES"<<endl;
        cout<<1<<" "<<n<<endl;
        return 0;
    }
	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++) {
        pre[i] = pre[i - 1] + (arr[i - 1] >= arr[i] ? 1 : 0);
    }

   

    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 - 1] - ((i + 1 < n) ? pre[i + 1] : 0);
        int ft = (l - 1 >= 0) ? pre[l - 1] : 0;
       
        if(bc or ft)continue;
        if(l > 0 and i + 1 < n){
            if(arr[l-1] <= result.minimum and result.maximum <= arr[i+1]){
                cout<<"YES"<<endl;
                cout<<l+1<<" "<<i+1<<endl;
                return 0;
            }
        }
        else if(l > 0){
            if(arr[l-1] <= result.minimum){
                cout<<"YES"<<endl;
                cout<<l+1<<" "<<i+1<<endl;
                return 0;
            }
        }
        else if(i+1 < n){
            if(result.maximum <= arr[i+1]){
                cout<<"YES"<<endl;
                cout<<l+1<<" "<<i+1<<endl;
                return 0;
            }
        }
        else{
            cout<<"YES"<<endl;
            cout<<l+1<<" "<<i+1<<endl;
            return 0;
        }
        // cout<<l<<" "<<i<<" "<<result.minimum<<" "<<result.maximum<<endl;
    }
    cout<<"NO"<<endl;

	return 0;
}
/*
0 0 1 1 1 
*/

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 16:14:13
Judged At
2024-11-11 02:27:59
Judged By
Score
15
Total Time
2ms
Peak Memory
540.0 KiB