結果
問題 | No.404 部分門松列 |
ユーザー |
|
提出日時 | 2016-07-23 04:07:11 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 3,415 bytes |
コンパイル時間 | 1,522 ms |
コンパイル使用メモリ | 99,404 KB |
実行使用メモリ | 54,068 KB |
最終ジャッジ日時 | 2024-11-06 14:21:29 |
合計ジャッジ時間 | 23,296 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 30 TLE * 1 |
ソースコード
#include <cstdio>#include <vector>#include <algorithm>#include <map>#include <queue>#include <tuple>#include <functional>#include <cmath>#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))#define whole(f,x,...) ([&](decltype((x)) y) { return (f)(begin(y), end(y), ## __VA_ARGS__); })(x)typedef long long ll;using namespace std;template <typename T>struct segment_tree { // on monoidint n;vector<T> a;function<T (T,T)> append; // associativeT unit;template <typename F>segment_tree(int a_n, T a_unit, F a_append) {n = pow(2,ceil(log2(a_n)));a.resize(2*n-1, a_unit);unit = a_unit;append = a_append;}void point_update(int i, T z) {a[i+n-1] = z;for (i = (i+n)/2; i > 0; i /= 2) {a[i-1] = append(a[2*i-1], a[2*i]);}}T range_concat(int l, int r) {return range_concat(0, 0, n, l, r);}T range_concat(int i, int il, int ir, int l, int r) {if (l <= il and ir <= r) {return a[i];} else if (ir <= l or r <= il) {return unit;} else {return append(range_concat(2*i+1, il, (il+ir)/2, l, r),range_concat(2*i+2, (il+ir)/2, ir, l, r));}}};map<int,ll> count_kadomatsu(vector<int> const & as, int first, int last) {int n = as.size();int direction = first < last ? 1 : -1;map<int,ll> acc;acc[first] = 0;map<int,vector<int> > que;repeat (i,n) que[direction * as[i]].push_back(i);segment_tree<int> cnt(n, 0, plus<int>());for (auto & it : que) {int a; vector<int> is; tie(a, is) = it;a *= direction;acc[a] = acc[first];first = a;for (int i : is) {int l = cnt.range_concat(0, i);int r = cnt.range_concat(i+1, n);acc[a] += l *(ll) r;}for (int i : is) {cnt.point_update(i, 1);}}return acc;}map<int,ll> count_same(vector<int> const & as) {int n = as.size();map<int,ll> dp;map<int,int> total; repeat (i,n) total[as[i]] += 1;map<int,int> used;ll cur = 0;for (int a : as) {dp[a] += cur - used[a] *(ll) (total[a] - used[a]);cur -= used[a];used[a] += 1;cur += total[a] - used[a];}map<int,ll> acc;int first = -1;acc[first] = 0;for (auto it : dp) {acc[it.first] = acc[first] + it.second;first = it.first;}acc[1e9+7] = acc[first];return acc;}int main() {// inputint n; scanf("%d", &n);vector<int> a(n); repeat (i,n) scanf("%d", &a[i]);// computemap<int,ll> acch = count_kadomatsu(a, -1, 1e9+7); // a1 < a2, a2 > a3map<int,ll> accl = count_kadomatsu(a, 1e9+7, -1); // a1 > a2, a2 < a3map<int,ll> accs = count_same(a);// outputint q; scanf("%d", &q);while (q --) {int l, h; scanf("%d%d", &l, &h);ll ahr = (-- acch.upper_bound(h ))->second;ll ahl = (-- acch.upper_bound(l-1))->second;ll alr = ( accl.lower_bound(h+1))->second;ll all = ( accl.lower_bound(l ))->second;ll asr = (-- accs.upper_bound(h ))->second;ll asl = (-- accs.upper_bound(l-1))->second;printf("%lld\n", (ahr - ahl) + (all - alr) - (asr - asl));}return 0;}