oj.uz

Submission #96473

# Submission time Handle Problem Language Result Execution time Memory
96473 2019-02-09T14:54:08 Z rajarshi_basu Global Warming (NOI13_gw) C++14
40 / 40
 862 ms 29532 KB 
#include <iostream>
#include <vector>
#include <set>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <stdio.h>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <complex>
#include <stack>
#include <set>

#define FOR(i,n) for (int i = 0;i<n;i++)
#define FORE(i, a, b) for (int i = a;i<= b;i++)
#define ll long long int
#define ff first
#define ss second
#define ii pair<int,int>
#define pb push_back
#define mp make_pair

using namespace std;

int* arr;
int N;



vector<int> _begs_;
vector<int> _ends_;
void preProcess(){

	FOR(i,N){
		if(i==0)continue;
		if(arr[i] != arr[i-1]){
			_begs_.pb(min(arr[i],arr[i-1]));
			_ends_.pb(max(arr[i],arr[i-1])-1);
		}
	}
	sort(_begs_.begin(), _begs_.end());
	sort(_ends_.begin(), _ends_.end());
}


// sl == sealevel
int query(int& sl){
	int cnt = 0;

	//FOR(i,all.size())if(sl >= all[i].ff and sl <= all[i].ss)cnt++;
	int eliminate = _begs_.end() - lower_bound(_begs_.begin(), _begs_.end() , sl+1);
	eliminate += lower_bound(_ends_.begin(), _ends_.end() , sl) - _ends_.begin();
	cnt = _begs_.size() - eliminate;
	if(arr[0] > sl)cnt++;
	if(arr[N-1] > sl)cnt++;
	//if((arr[0] > sl and arr[N-1]>sl)or(arr[0] <= sl and arr[N-1] <= sl))cnt++;
	return cnt/2;
}

int gw(int nn){
	N = nn;
	ii crdcmprs[N];
	//cout << N << endl;
	FOR(i,N){crdcmprs[i].ff = arr[i];crdcmprs[i].ss = i;}

	//delete[] H;
	//cout << " la la " << endl;
	sort(crdcmprs,crdcmprs+N);
	int PtR = 0;
	FOR(i,N){
		if(i > 0 and crdcmprs[i].ff > crdcmprs[i-1].ff)PtR++;
		arr[crdcmprs[i].ss] = PtR;
	}

	int mx = 0;
	preProcess();
	//FOR(i,N)cout << arr[i] << " ";cout << endl;
	
	FOR(i,min(crdcmprs[N-1].ff+1,N+2)){
		int val;
		mx = max(mx,val = query(i));
		//cout << val << endl;
	}
	return mx;
}


int main(){
	int n;
	cin >> n;
	arr = new int[n];

	FOR(i,n)cin >> arr[i];
	//cout << "blue" << endl;
	cout << gw(n) << endl;
	return 0;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 2 ms 376 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 2548 KB Output is correct
2 Correct 39 ms 2548 KB Output is correct
3 Correct 38 ms 2532 KB Output is correct
4 Correct 38 ms 2420 KB Output is correct
5 Correct 36 ms 2520 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 2432 KB Output is correct
2 Correct 68 ms 2548 KB Output is correct
3 Correct 70 ms 2548 KB Output is correct
4 Correct 70 ms 2548 KB Output is correct
5 Correct 71 ms 2548 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 795 ms 20256 KB Output is correct
2 Correct 767 ms 20224 KB Output is correct
3 Correct 778 ms 29520 KB Output is correct
4 Correct 765 ms 29532 KB Output is correct
5 Correct 862 ms 28996 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 775 ms 20940 KB Output is correct
2 Correct 787 ms 21004 KB Output is correct
3 Correct 749 ms 28808 KB Output is correct
4 Correct 412 ms 22880 KB Output is correct
5 Correct 393 ms 23040 KB Output is correct