Submission #2082437


Source Code Expand

Copy
#include <bits/stdc++.h>

using namespace std;
#define FOR(i,n) for(int i = 0; i < (n); i++)
#define sz(c) ((int)c.size())
#define ten(n) ((int)1e##n)
using ll = long long;
using Pii = pair<int, int>;
using Pll = pair<ll, ll>;

template<typename ...> static inline int getchar_unlocked(void) { return getchar(); }
template<typename ...> static inline void putchar_unlocked(int c) { putchar(c); }
#define mygc(c) (c)=getchar_unlocked()
#define mypc(c) putchar_unlocked(c)
void reader(int& x) { int k, m = 0; x = 0; for (;;) { mygc(k); if (k == '-') { m = 1; break; }if ('0' <= k&&k <= '9') { x = k - '0'; break; } }for (;;) { mygc(k); if (k<'0' || k>'9')break; x = x * 10 + k - '0'; }if (m) x = -x; }
void reader(ll& x) { int k, m = 0; x = 0; for (;;) { mygc(k); if (k == '-') { m = 1; break; }if ('0' <= k&&k <= '9') { x = k - '0'; break; } }for (;;) { mygc(k); if (k<'0' || k>'9')break; x = x * 10 + k - '0'; }if (m) x = -x; }
int reader(char c[]) { int i, s = 0; for (;;) { mygc(i); if (i != ' '&&i != '\n'&&i != '\r'&&i != '\t'&&i != EOF) break; }c[s++] = i; for (;;) { mygc(i); if (i == ' ' || i == '\n' || i == '\r' || i == '\t' || i == EOF) break; c[s++] = i; }c[s] = '\0'; return s; }
int reader(string& c) { int i; for (;;) { mygc(i); if (i != ' '&&i != '\n'&&i != '\r'&&i != '\t'&&i != EOF) break; }c.push_back(i); for (;;) { mygc(i); if (i == ' ' || i == '\n' || i == '\r' || i == '\t' || i == EOF) break; c.push_back(i); }; return sz(c); }
template <class T, class S> void reader(T& x, S& y) { reader(x); reader(y); }
template <class T, class S, class U> void reader(T& x, S& y, U& z) { reader(x); reader(y); reader(z); }
template <class T, class S, class U, class V> void reader(T& x, S& y, U& z, V & w) { reader(x); reader(y); reader(z); reader(w); }
void writer(int x, char c) { int s = 0, m = 0; char f[10]; if (x<0)m = 1, x = -x; while (x)f[s++] = x % 10, x /= 10; if (!s)f[s++] = 0; if (m)mypc('-'); while (s--)mypc(f[s] + '0'); mypc(c); }
void writer(ll x, char c) { int s = 0, m = 0; char f[20]; if (x<0)m = 1, x = -x; while (x)f[s++] = x % 10, x /= 10; if (!s)f[s++] = 0; if (m)mypc('-'); while (s--)mypc(f[s] + '0'); mypc(c); }
void writer(const char c[]) { int i; for (i = 0; c[i] != '\0'; i++)mypc(c[i]); }
void writer(const string& x, char c) { int i; for (i = 0; x[i] != '\0'; i++)mypc(x[i]); mypc(c); }
void writer(const char x[], char c) { int i; for (i = 0; x[i] != '\0'; i++)mypc(x[i]); mypc(c); }
template<class T> void writerLn(T x) { writer(x, '\n'); }
template<class T, class S> void writerLn(T x, S y) { writer(x, ' '); writer(y, '\n'); }
template<class T, class S, class U> void writerLn(T x, S y, U z) { writer(x, ' '); writer(y, ' '); writer(z, '\n'); }
template<class T> void writerArr(T x[], int n) { if (!n) { mypc('\n'); return; }FOR(i, n - 1)writer(x[i], ' '); writer(x[n - 1], '\n'); }
template<class T> void writerArr(vector<T>& x) { writerArr(x.data(), (int)x.size()); }

template<class T> void chmin(T& a, const T& b) { if (a > b) a = b; }
template<class T> void chmax(T& a, const T& b) { if (a < b) a = b; }

template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template<class T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
ll mod_pow(ll a, ll n, ll mod) {
	ll ret = 1;
	ll p = a % mod;
	while (n) {
		if (n & 1) ret = ret * p % mod;
		p = p * p % mod;
		n >>= 1;
	}
	return ret;
}
template<class T> T extgcd(T a, T b, T& x, T& y) { for (T u = y = 1, v = x = 0; a;) { T q = b / a; swap(x -= q * u, u); swap(y -= q * v, v); swap(b -= q * a, a); } return b; }
ll mod_inv(ll a, ll m) { ll x, y; extgcd<ll>(a, m, x, y); return (m + x % m) % m; }

template<class val_t>
struct min_t {
	val_t val;
	static min_t zero() { return min_t(); }
	min_t() : val(numeric_limits<val_t>::max()) {}
	min_t(val_t val) : val(val) {}
	operator val_t () const { return val; }
	bool is_zero() const { return val == zero().val; }
	min_t operator+ (const min_t& r) const {
		if (is_zero()) return r;
		else if (r.is_zero()) return *this;

		min_t ret(min(val, r.val));
		return ret;
	}
};

using P = min_t<ll>;

class seg_tree {
public:
	vector<P> dat;
	int n;

	void propagate(int i) {
		dat[i] = dat[i * 2 + 1] + dat[i * 2 + 2];
	}

	void init(ll* d, int size) {
		n = 1;
		while (n < size) n <<= 1;
		dat.resize(2 * n - 1);
		fill(dat.begin(), dat.end(), P::zero());
		for (int i = 0; i < size; i++) dat[n - 1 + i] = d[i];
		for (int i = n - 2; i >= 0; i--) propagate(i);
	}

	//[a,b)
	P query(int a, int b) {
		return query(a, b, 0, 0, n);
	}

	P query(int a, int b, int k, int l, int r) {
		if (r <= a || b <= l) return P::zero();
		if (a <= l && r <= b) return dat[k];

		int md = (l + r) / 2; //[l,md),[md,r)
		int nl = k * 2 + 1, nr = nl + 1;
		P lval = query(a, b, nl, l, md);
		P rval = query(a, b, nr, md, r);

		return lval + rval;
	}
};

ll dsum[ten(5) + 1];
ll val[ten(5)];

int main() {
	int n; reader(n);
	vector<ll> d(n);
	FOR(i, n) reader(d[i]);
	reverse(d.begin(), d.end());
	FOR(i, n) dsum[i + 1] += dsum[i] + d[i];
	{
		int r = n - 1;
		FOR(k, n + 1) {
			if (k == 0) continue;
			ll base = k * ll(k - 1);
			while (r >= 0 && d[r] <= k) {
				r--;
			}
			ll k2 = max(r + 1, k);
			ll part1 =ll (k2 - k) * k;
			ll part2 = dsum[n] - dsum[k2];
			ll rem = dsum[k];

			ll cur = base + part1 + part2 - rem;
			val[k - 1] = cur;
		}
	}

	seg_tree seg;
	seg.init(val, n);

	bool ok;
	if (dsum[n] % 2 == 0) {
		ok = true;
		FOR(i, n) if (val[i] < 0) ok = false;
		puts(ok ? "YES" : "ABSOLUTELY NO");
	} else {
		ok = false;
		FOR(i, n) {
			if (i != 0 && d[i] == d[i - 1]) continue;
			if (d[i] == n - 1) continue;

			int md1 = d[i];
			int md2 = i;
			md1 = min(md1, md2);

			bool curok = true;
			if (md1 != 0) {
				int lval = seg.query(0, md1).val;
				if (lval < 0) {
					curok = false;
				}
			}
			if (md1 != md2) {
				int mval = seg.query(md1, md2).val;
				if (mval < -1) {
					curok = false;
				}
			}
			if (md2 != n) {
				int rval = seg.query(md2, n).val;
				if (rval < 1) {
					curok = false;
				}
			}

			if (curok) {
				ok = true;
			}
		}
	
		puts(ok ? "NO" : "ABSOLUTELY NO");
	}




	return 0;
}

Submission Info

Submission Time
Task E - グラフの問題
User math
Language C++14 (GCC 5.4.1)
Score 0
Code Size 6263 Byte
Status
Exec Time 30 ms
Memory 4608 KB

Judge Result

Set Name Score / Max Score Test Cases
Sample 0 / 0 s1.txt, s2.txt, s3.txt
All 0 / 1000 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, 37.txt, 38.txt, 39.txt, 40.txt, 41.txt, 42.txt, 43.txt, 44.txt, 45.txt, 46.txt, 47.txt, 48.txt, 49.txt, 50.txt, 51.txt, 52.txt, 53.txt, 54.txt, 55.txt, 56.txt, 57.txt, 58.txt, 59.txt, 60.txt, 61.txt, 62.txt, 63.txt, 64.txt, 65.txt, 66.txt, 67.txt, 68.txt, 69.txt, 70.txt, 71.txt, 72.txt, 73.txt, 74.txt, 75.txt, 76.txt, s1.txt, s2.txt, s3.txt
Case Name Status Exec Time Memory
01.txt 30 ms 4608 KB
02.txt 6 ms 4608 KB
03.txt 6 ms 4608 KB
04.txt 30 ms 4608 KB
05.txt 30 ms 4608 KB
06.txt 5 ms 4608 KB
07.txt 5 ms 4608 KB
08.txt 5 ms 4608 KB
09.txt 5 ms 4608 KB
10.txt 5 ms 4608 KB
11.txt 5 ms 4608 KB
12.txt 5 ms 4608 KB
13.txt 5 ms 4608 KB
14.txt 5 ms 4608 KB
15.txt 6 ms 4608 KB
16.txt 6 ms 4608 KB
17.txt 5 ms 4608 KB
18.txt 5 ms 4608 KB
19.txt 5 ms 4608 KB
20.txt 5 ms 4608 KB
21.txt 5 ms 4608 KB
22.txt 5 ms 4608 KB
23.txt 5 ms 4608 KB
24.txt 5 ms 4608 KB
25.txt 5 ms 4608 KB
26.txt 5 ms 4608 KB
27.txt 5 ms 4608 KB
28.txt 5 ms 4608 KB
29.txt 5 ms 4608 KB
30.txt 5 ms 4608 KB
31.txt 5 ms 4608 KB
32.txt 5 ms 4608 KB
33.txt 5 ms 4608 KB
34.txt 5 ms 4608 KB
35.txt 5 ms 4608 KB
36.txt 5 ms 4608 KB
37.txt 23 ms 4608 KB
38.txt 6 ms 4608 KB
39.txt 5 ms 4608 KB
40.txt 7 ms 4608 KB
41.txt 23 ms 4608 KB
42.txt 5 ms 4608 KB
43.txt 5 ms 4608 KB
44.txt 5 ms 4608 KB
45.txt 5 ms 4608 KB
46.txt 5 ms 4608 KB
47.txt 9 ms 4608 KB
48.txt 5 ms 4608 KB
49.txt 8 ms 4608 KB
50.txt 25 ms 4608 KB
51.txt 5 ms 4608 KB
52.txt 5 ms 4608 KB
53.txt 5 ms 4608 KB
54.txt 5 ms 4608 KB
55.txt 5 ms 4608 KB
56.txt 6 ms 4608 KB
57.txt 5 ms 4608 KB
58.txt 5 ms 4608 KB
59.txt 6 ms 4608 KB
60.txt 6 ms 4608 KB
61.txt 5 ms 4608 KB
62.txt 5 ms 4608 KB
63.txt 5 ms 4608 KB
64.txt 5 ms 4608 KB
65.txt 5 ms 4608 KB
66.txt 5 ms 4608 KB
67.txt 5 ms 4608 KB
68.txt 6 ms 4608 KB
69.txt 5 ms 4608 KB
70.txt 5 ms 4608 KB
71.txt 1 ms 256 KB
72.txt 1 ms 256 KB
73.txt 1 ms 256 KB
74.txt 1 ms 256 KB
75.txt 1 ms 256 KB
76.txt 1 ms 256 KB
s1.txt 1 ms 256 KB
s2.txt 1 ms 256 KB
s3.txt 1 ms 256 KB