Submission #1689575
Source Code Expand
#include <iostream>
#include <vector>
#include <string.h>
#include <stack>
#include <queue>
#include <algorithm>
#include <climits>
#include <cmath>
#include <map>
#include <set>
#include <assert.h>
#include <sstream>
#define REP(i,n) for(ll i=0;i<(n);i++)
#define MOD 1000000007
#define int long long
#ifdef int
const long long INF = LLONG_MAX / 10;
#else
const int INF = 1010101010;
#endif
using namespace std;
typedef long long ll;
typedef vector<vector<ll>> mat;
typedef pair<int, int> P;
//typedef pair<double, double> P;
#ifdef LOCAL
#define dump(...) \
do { \
std::ostringstream os; \
os << __LINE__ << ":\t" << #__VA_ARGS__ << " = "; \
print_to(os, ", ", "\n", __VA_ARGS__); \
std::cerr << os.str(); \
} while (0)
#define dump_(a) \
do { \
std::ostringstream os; \
os << __LINE__ << ":\t" << #a << " = ["; \
print_to_(os, ", ", "]\n", all(a)); \
std::cerr << os.str(); \
} while (0)
#else
#define dump(...)
#define dump_(...)
#endif
template <typename T>
void print_to(std::ostream &os, const char *, const char *tail, const T &fst) {
os << fst << tail;
}
template <typename Fst, typename... Rst>
void print_to(std::ostream &os, const char *del, const char *tail, const Fst &fst, const Rst &... rst) {
os << fst << del;
print_to(os, del, tail, rst...);
}
template <typename Iter>
void print_to_(std::ostream &os, const char *del, const char *tail, Iter bgn, Iter end) {
for (Iter it = bgn; it != end;) {
os << *it;
if (++it != end) {
os << del;
} else {
os << tail;
}
}
}
template <typename Fst, typename... Rst>
void println(const Fst &fst, const Rst &... rst) {
print_to(std::cout, "\n", "\n", fst, rst...);
}
template <typename Fst, typename... Rst>
void print(const Fst &fst, const Rst &... rst) {
print_to(std::cout, " ", "\n", fst, rst...);
}
template <typename Iter>
void println_(Iter bgn, Iter end) {
print_to_(std::cout, "\n", "\n", bgn, end);
}
template <typename Iter>
void print_(Iter bgn, Iter end) {
print_to_(std::cout, " ", "\n", bgn, end);
}
// const int MOD = 1000000007;
namespace trush {
int _ = (std::cout.precision(10), std::cout.setf(std::ios::fixed), std::cin.tie(0),
std::ios::sync_with_stdio(0), 0);
}
struct SegmentTree
{
private:
int n;
vector<int> node;
public:
//元配列v(vector)をセグメント木で表現する
SegmentTree(vector<int> v)
{
//最下段のノード数は元配列のサイズ以上になる最小の2冪→これをnとおく
//セグメント木全体で必要なノード数は2n-1である
int sz = v.size();
n = 1;
while (n < sz) n *= 2;
node.resize(2 * n - 1, INF);
//最下段に値を入れたあとに、下の段から埋めていく
//値を埋めるときは自分の2つの子を見ればいい
REP(i,sz) node[i+(n-1)] = v[i];
for (int i=n-2; i>=0; i--) {
//★セグ木の処理を書き換えるときはここを書き換える
node[i] = min(node[2*i+1], node[2*i+2]);
}
}
void update(int x, int val)
{
//最下段のノードにアクセスする
x += n - 1;
//最下段のノードを更新したら、あとは親に登って更新していく
node[x] = val;
while (x > 0) {
//x=0でないなら親がある
x = (x - 1) / 2;
node[x] = min(node[2*x+1], node[2*x+2]);
}
}
//要求区間[a,b)の要素の最小値を答える
//k:=自分がいるノードのインデックス
//対象区間は[l,r)にあたる
int getmin(int a, int b, int k = 0, int l = 0, int r = -1)
{
//最初に呼び出されたときの対象区間は[0,n)
if (r < 0) r = n;
//要求区間と対象区間が交わらない→答えに影響を与えない値を返す
//★セグ木の機能によって変える
if (r <= a || b <= l) return INF;
//要求区間が対象区間を完全に被覆→対象区間を答えの計算に使う
if (a <= l && r <= b) return node[k];
//要求区間が対象区間の一部を被覆→子について探索を行う
//左の子をvl、右の子をvrとしている
//新しい対象区間は現在の対象区間を半分にしたもの
int vl = getmin(a, b, 2 * k + 1, l, (l + r) / 2);
int vr = getmin(a, b, 2 * k + 2, (l + r) / 2, r);
return min(vl, vr);
}
};
int N, T;
vector<int> A;
map<int, int> cnt;
int maxDiff = 0;
signed main()
{
cin >> N >> T;
A.resize(N);
REP(i,N) {
cin >> A[i];
}
int mi = A[0];
for (int i=1; i<N; i++) {
int diff = A[i] - mi;
cnt[diff]++;
if (maxDiff < diff) {
maxDiff = diff;
}
mi = min(mi, A[i]);
}
cout << cnt[maxDiff] << endl;
}
Submission Info
Submission Time |
|
Task |
D - An Invisible Hand |
User |
hiyokko2 |
Language |
C++14 (GCC 5.4.1) |
Score |
400 |
Code Size |
5518 Byte |
Status |
AC |
Exec Time |
44 ms |
Memory |
7296 KB |
Judge Result
Set Name |
sample |
All |
Score / Max Score |
0 / 0 |
400 / 400 |
Status |
|
|
Set Name |
Test Cases |
sample |
sample_01.txt, sample_02.txt, sample_03.txt |
All |
large_01.txt, large_02.txt, random_01.txt, random_02.txt, sample_01.txt, sample_02.txt, sample_03.txt, small_01.txt, small_02.txt, spec_01.txt, spec_02.txt, spec_03.txt, spec_04.txt, spec_05.txt, spec_06.txt |
Case Name |
Status |
Exec Time |
Memory |
large_01.txt |
AC |
12 ms |
1024 KB |
large_02.txt |
AC |
37 ms |
7296 KB |
random_01.txt |
AC |
43 ms |
7296 KB |
random_02.txt |
AC |
43 ms |
7296 KB |
sample_01.txt |
AC |
1 ms |
256 KB |
sample_02.txt |
AC |
1 ms |
256 KB |
sample_03.txt |
AC |
1 ms |
256 KB |
small_01.txt |
AC |
1 ms |
256 KB |
small_02.txt |
AC |
1 ms |
256 KB |
spec_01.txt |
AC |
44 ms |
7296 KB |
spec_02.txt |
AC |
43 ms |
7296 KB |
spec_03.txt |
AC |
42 ms |
7040 KB |
spec_04.txt |
AC |
42 ms |
7040 KB |
spec_05.txt |
AC |
40 ms |
6656 KB |
spec_06.txt |
AC |
36 ms |
5888 KB |