Submission #58908

#TimeUsernameProblemLanguageResultExecution timeMemory
58908BenqGlobal Warming (NOI13_gw)C++11
40 / 40
455 ms25920 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/tree_policy.hpp> #include <ext/pb_ds/assoc_container.hpp> using namespace std; using namespace __gnu_pbds; typedef long long ll; typedef long double ld; typedef complex<ld> cd; typedef pair<int, int> pi; typedef pair<ll,ll> pl; typedef pair<ld,ld> pd; typedef vector<int> vi; typedef vector<ld> vd; typedef vector<ll> vl; typedef vector<pi> vpi; typedef vector<pl> vpl; typedef vector<cd> vcd; template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>; #define FOR(i, a, b) for (int i=a; i<(b); i++) #define F0R(i, a) for (int i=0; i<(a); i++) #define FORd(i,a,b) for (int i = (b)-1; i >= a; i--) #define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--) #define sz(x) (int)(x).size() #define mp make_pair #define pb push_back #define f first #define s second #define lb lower_bound #define ub upper_bound #define all(x) x.begin(), x.end() const int MOD = 1000000007; const ll INF = 1e18; const int MX = 1000005; int N, co = 0; int ins[MX], del[MX]; int lst = 0; void process(int x) { ins[co] = min(x,lst); del[co] = max(x,lst); co ++; lst = x; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> N; FOR(i,1,N+1) { int x; cin >> x; process(x); } process(0); sort(ins,ins+N+1); sort(del,del+N+1); int cur = 0, ind = 0, ans = 0; F0R(i,N+1) { int a = ins[i]; cur ++; while (ind < N+1 && del[ind] <= a) { ind ++; cur --; } ans = max(ans,cur); } cout << ans/2; } /* Look for: * the exact constraints (multiple sets are too slow for n=10^6 :( ) * special cases (n=1?) * overflow (ll vs int?) * array bounds */
#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...