結果
| 問題 | No.1031 いたずら好きなお姉ちゃん |
| ユーザー |
 Thistle
|
| 提出日時 | 2020-04-04 03:36:40 |
| 言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 308 ms / 3,500 ms |
| コード長 | 4,825 bytes |
| コンパイル時間 | 8,297 ms |
| コンパイル使用メモリ | 197,252 KB |
| 最終ジャッジ日時 | 2025-01-09 13:57:37 |
|
ジャッジサーバーID （参考情報） |
judge4 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 53 |
ソースコード
#pragma GCC target ("avx")#pragma GCC optimize("O3")#pragma GCC optimize("unroll-loops")//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")#define _USE_MATH_DEFINES#include<iostream>#include<string>#include<queue>#include<cmath>#include<map>#include<set>#include<list>#include<iomanip>#include<vector>#include<random>#include<functional>#include<algorithm>#include<stack>#include<cstdio>#include<cstring>#include<bitset>#include<unordered_map>#include<climits>#include<fstream>#include<complex>#include<time.h>#include<cassert>#include<functional>#include<numeric>#include<tuple>using namespace std;using ll = int_fast64_t;using ld = long double;#define int ll#define all(a) (a).begin(),(a).end()#define fs first#define sc second#define xx first#define yy second.first#define zz second.second#define H pair<int, int>#define P pair<int, pair<int, int>>#define Q(i,j,k) mkp(i,mkp(j,k))#define rep(i,n) for(int (i) = 0 ; (i) < (n) ; (i)++)#define rng(i,s,n) for(int (i) = (s) ; (i) < (n) ; (i)++)#define mkp make_pair#define vec vector#define pb emplace_back#define crdcomp(b) sort(all((b)));(b).erase(unique(all((b))),(b).end())#define getidx(b,i) lower_bound(all(b),(i))-b.begin()#define ssp(i,n) (i==(ll)(n)-1?"\n":" ")#define ctoi(c) (int)(c-'0')#define itoc(c) (char)(c+'0')#define pp(x,y) pb(H{x,y})#define ppp(x,y,z) pb(Q(x,y,z))#define cdf int q810; cin>>q810; rep(q114,q810)//#define endl "\n"constexpr int mod = 1e9 + 7;constexpr int Mod = 998244353;constexpr int MXN = 500000 + 100;constexpr ld EPS = 1e-10;constexpr ll inf = 3 * 1e18;constexpr int Inf = 15 * 1e8;const vec<int>dx{ -1,1,0,0 }, dy{ 0,0,-1,1 };template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }ll read() { ll u, k = scanf("%lld", &u); return u; }string reads() { string s; cin >> s; return s; }H readh(bool g = 0) { H u; ll k = scanf("%lld %lld", &u.fs, &u.sc); if (g) u.fs--, u.sc--; return u; }void printh(H t) { printf("%lld %lld\n", t.fs, t.sc); }bool inarea(H t, int h, int w) { return 0 <= t.fs && t.fs < h && 0 <= t.sc && t.sc < w; }ll gcd(ll i, ll j) { return j ? gcd(j, i % j) : i; }ll mod_pow(ll x, ll n, ll p = mod) {ll res = 1;while (n > 0) {if (n & 1) res = res * x % p;x = x * x % p;n >>= 1;}return res;}//x^n%pll bitcount(ll x) {int sum = 0; for (int i = 0; i < 60; i++)if ((1ll << i) & x) sum++;return sum;}/*constexpr int fn_ = 1000005;ll fact_[fn_], comp_[fn_];ll comb(ll x, ll y, ll Mod = mod) {if (!fact_[0]) {fact_[0] = 1; comp_[0] = 1;for (int i = 1; i < fn_; i++)fact_[i] = fact_[i - 1] * i % Mod;comp_[fn_ - 1] = mod_pow(fact_[fn_ - 1], Mod - 2, Mod);for (int i = fn_ - 2; i > 0; i--)comp_[i] = comp_[i + 1] * (i + 1) % Mod;}if (x < y) return 0;return fact_[x] * comp_[x - y] % Mod * comp_[y] % Mod;}*///--------------------------------------------------------------int n; vec<int>a;int sq;//バケットサイズvec<int>c[10000][2];//これに入った後使える個数vec<int>d[10000];//このバケットに入っているものH e[10000];signed main() {cin >> n; sq = sqrt(n);rep(i, n) {a.pb(read());d[i / sq].pb(a[i]);}int m = (n - 1) / sq + 1;rep(i, m) {e[i].fs = i * sq;e[i].sc = min(n, (i + 1) * sq);sort(all(d[i]));}rep(i, m) {c[i][0].pb(0);//魔境c[i][1].pb(0);for (auto g : d[i]) {//g以上d[i][g+1]未満の値が来た場合int sum = 0, t = g;rng(j, e[i].fs, e[i].sc) {if (a[j] <= t) {t = a[j]; sum++;}}c[i][0].pb(sum);sum = 0, t = g;for (int j = e[i].sc - 1; j >= e[i].fs; j--) {if (a[j] <= t) {t = a[j]; sum++;}}c[i][1].pb(sum);}}int res = 0;rep(i, n) {//左方向int t = a[i], ans = 0;for (int j = i - 1; j >= e[i / sq].fs; j--) {if (a[j] > a[i]) goto loop;if (a[j] < t) ans++, t = a[j];}for (int j = i / sq - 1; j >= 0; j--) {int k = lower_bound(all(d[j]), t) - d[j].begin();if (d[j][d[j].size() - 1] > a[i]) {for (int z = e[j].sc - 1; z >= e[j].fs; z--) {if (a[z] > a[i]) goto loop;if (a[z] < t) ans++, t = a[z];}}ans += c[j][1][k];chmin(t, d[j][0]);}loop:;t = a[i];rng(j, i + 1, e[i / sq].sc) {if (a[j] > a[i]) goto roop;if (a[j] < t) {ans++;t = a[j];}}rng(j, i / sq + 1, m) {int k = lower_bound(all(d[j]), t) - d[j].begin();if (d[j][d[j].size() - 1] > a[i]) {for (int z = e[j].fs; z < e[j].sc; z++) {if (a[z] > a[i]) goto roop;if (a[z] < t) ans++, t = a[z];}}ans += c[j][0][k];chmin(t, d[j][0]);}roop:;res += ans;}cout << res << endl;}