Submission #96473

#TimeUsernameProblemLanguageResultExecution timeMemory
96473rajarshi_basuGlobal Warming (NOI13_gw)C++14
40 / 40
862 ms29532 KiB
#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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...