結果

問題 No.2359 A in S ?
ユーザー Alex WiceAlex Wice
提出日時 2023-06-23 23:03:00
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 7,856 bytes
コンパイル時間 3,937 ms
コンパイル使用メモリ 292,116 KB
実行使用メモリ 17,580 KB
最終ジャッジ日時 2024-07-01 02:50:38
合計ジャッジ時間 8,559 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
13,884 KB
testcase_01 AC 2 ms
6,944 KB
testcase_02 AC 3 ms
6,940 KB
testcase_03 AC 3 ms
6,940 KB
testcase_04 AC 86 ms
8,076 KB
testcase_05 AC 184 ms
7,824 KB
testcase_06 AC 96 ms
7,948 KB
testcase_07 AC 79 ms
7,820 KB
testcase_08 TLE -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include "bits/stdc++.h"
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;

// clang-format off
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...)
#endif

using ll = long long;
using str = string;
using AR2 = array<int, 2>;
template <class T> using oset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <class T> using vec = vector<T>;
template <class T> using vvec = vec<vec<T>>;
template <class T> using vvvec = vec<vvec<T>>;
template <class T, size_t SZ> using vac = vec<array<T, SZ>>;
template <class T, size_t SZ> using vvac = vec<vac<T, SZ>>;
// template <class T> using priority_queue_min = priority_queue<T, vec<T>, greater<T>>;
 
 
#define sz(x) int((x).size())
#define all(x) begin(x), end(x)
#define rall(x) x.rbegin(), x.rend()
#define sor(x) sort(all(x))
#define pb push_back
 
#define F_OR(i, a, b, s) for (int i=(a); (s)>0?i<(int)(b):i>(int)(b); i+=(s))
#define F_OR1(e) F_OR(i, 0, e, 1)
#define F_OR2(i, e) F_OR(i, 0, e, 1)
#define F_OR3(i, b, e) F_OR(i, b, e, 1)
#define F_OR4(i, b, e, s) F_OR(i, b, e, s)
#define GET5(a, b, c, d, e, ...) e
#define F_ORC(...) GET5(__VA_ARGS__, F_OR4, F_OR3, F_OR2, F_OR1)
#define FOR(...) F_ORC(__VA_ARGS__)(__VA_ARGS__)
#define E_ACH2(x, a) for (auto& x: a)
#define E_ACH3(x, y, a) for (auto& [x, y]: a)
#define E_ACH4(x, y, z, a) for (auto& [x, y, z]: a)
#define E_ACHC(...) GET5(__VA_ARGS__, E_ACH4, E_ACH3, E_ACH2)
#define EACH(...) E_ACHC(__VA_ARGS__)(__VA_ARGS__)
#define SUBMASKS(t, s) for (ll t = (s); t >= 0; t = (t == 0 ? -1 : (t - 1) & (s)))
#define MIN(v) *min_element(all(v))
#define MAX(v) *max_element(all(v))

constexpr int popcount(int x) { return __builtin_popcount(x); }
constexpr int bitlength(int x) { return x == 0 ? 0 : 31 - __builtin_clz(x); }
ll cdiv(ll a, ll b) { return a/b + ((a^b) > 0 && a % b); };
ll fdiv(ll a, ll b) { return a/b - ((a^b) < 0 && a % b); };
template <class T> T pop(vec<T> &v) { T x = v.back(); v.pop_back(); return x; }
template <class T> bool bounds(T a, T lo, T hi) { return lo <= a && a <= hi; }
template <class T> T truemod(T x, T M) { return (x % M + M) % M; }
template <class T> bool umin(T &a, const T &b) { return b < a ? a = b, 1 : 0; }
template <class T> bool umax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
template <class T> int lwb(vec<T> &a,  T &b) { return int(lower_bound(all(a), b) - begin(a)); }
template <class T> int upb(vec<T> &a,  T &b) { return int(upper_bound(all(a), b) - begin(a)); }
template <class T> void removeDupes(vec<T> &v) { sort(all(v)); v.erase(unique(all(v)), end(v)); }
template <class T, class U> void eraseOne(T &t,  U &u) { auto it = t.find(u); assert(it != end(t)); t.erase(it); }
template <class T, class U> T firstTrue(T lo, T hi, U f) {
    ++hi; assert(lo <= hi);
    while (lo < hi) {
        T mi = lo + (hi-lo) / 2;
        f(mi) ? hi = mi : lo = mi + 1;
    }
    return lo;
}
template <class T, class U> T lastTrue(T lo, T hi, U f) {
    --lo; assert(lo <= hi);
    while (lo < hi) {
        T mi = lo + (hi-lo+1) / 2;
        f(mi) ? lo = mi : hi = mi - 1;
    }
    return lo;
}
 
template <class T, size_t SZ> istream &operator>>(istream &s, array<T, SZ>& v) { FOR(sz(v)) s >> v[i]; return s; }
template <class T> istream &operator>>(istream &s, vec<T>& v) { FOR(sz(v)) s >> v[i]; return s; }
template <class T> ostream &operator<<(ostream &s, vec<T>& v) { FOR(sz(v)) s << (i?" ":"") << v[i]; return s; }
template <class T> ostream &operator<<(ostream &s, const vec<T>& v) { FOR(sz(v)) s << (i?" ":"") << v[i]; return s; }
 
template<class A> void write(A x) { cout << x; }
template<class H, class... T> void write(const H& h, const T&... t) { 
	write(h); write(t...); }
void print() { write("\n"); }
template<class H, class... T> void print(const H& h, const T&... t) { 
	write(h); if (sizeof...(t)) write(" "); print(t...); }
 
void decrement() {}
template <class T, size_t SZ> void decrement(vec<array<T, SZ>> &v) { EACH(row, v) EACH(x, row) --x; }
template <class T> void decrement(vec<vec<T>> &v) { EACH(row, v) EACH(x, row) --x; }
template <class T> void decrement(vec<T> &v) { EACH(x, v) --x; }
template <class T, class... U> void decrement(T &t, U &...u) { --t; decrement(u...); }
 
template <class T> void read(T& x) { cin >> x; }
template<class T, class... U> void read(T &t, U &...u) { read(t); read(u...); }
#define ints(...) int __VA_ARGS__; read(__VA_ARGS__);
#define int1(...) ints(__VA_ARGS__); decrement(__VA_ARGS__);
#define vint(n, a) int n; cin >> n; vec<int> a(n); cin >> a;
#define vin(n, a) vec<int> a((n)); cin >> a;
#define vvin(n, m, a) vec<vec<int>> a((n), vec<int>((m))); cin >> a;
#define vain(n, m, a) vec<array<int, (m)>> a((n)); cin >> a;
#define graphin(n, m, adj) vvec<int> adj(n); FOR(m) {int1(u, v); adj[u].pb(v); adj[v].pb(u); }
#define lgraphin(n, m, adj) vvac<int, 2> adj(n); FOR(i, m) {int1(u, v); adj[u].pb({v,i}); adj[v].pb({u,i}); }
#define wgraphin(n, m, adj) vvac<int, 2> adj(n); FOR(m) {int1(u, v); ints(w); adj[u].pb({v,w}); adj[v].pb({u,w}); }
#define dgraphin(n, m, adj) vvec<int> adj(n); FOR(m) {int1(u, v); adj[u].pb(v);}
#define dwgraphin(n, m, adj) vvac<int, 2> adj(n); FOR(m) {int1(u, v, w); adj[u].pb({v, w+1});}

// clang-format on

void solve() {
    ints(N);
    str S;
    cin >> S;
    vac<int, 2> segs;

    function<ll(int, int)> count = [&](int l, int r) {
        return (ll)(r - l + 1) * (r - l) / 2;
    };
    int i = 0;
    while (i < N) {
        int j = i + 1;
        while (j < N && S[j] >= S[j - 1])
            j++;
        segs.push_back({i, j});
        i = j;
    }

    vec<ll> P(1, 0);
    EACH(l, r, segs) {
        P.push_back(P.back() + count(l, r));
    }

    ints(Q);
    FOR(qi, Q) {
        int1(L, R);
        array<int, 2> arleft = {L, N + 1}, arright = {R + 1, 0};
        int i = upb(segs, arleft);
        int j = lwb(segs, arright);
        i = max(i - 1, 0);
        j = max(j - 1, i);

        ll ans = P[j + 1] - P[i];
        ans -= count(segs[i][0], segs[i][1]);
        ans += count(L, min(segs[i][1], R + 1));
        if (i != j) {
            ans -= count(segs[j][0], segs[j][1]);
            ans += count(max(L, segs[j][0]), R + 1);
        }
        print(ans);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    const int MAGIC = 300;
    ints(N, M);
    vain(N, 4, segs);
    vac<int, 2> A(M);
    FOR(i, M) {
        cin >> A[i][0];
        A[i][1] = i;
    }
    sor(A);

    vec<array<int, 2>> events;
    FOR(i, N) {
        events.push_back({segs[i][0], i});
        events.push_back({segs[i][1] + 1, -i - 1});
    }
    sor(events);
    map<array<int, 2>, int> blender;
    vec<int> mask(100001);
    vec<int> ans(sz(A));
    int i = 0, j = 0;

    FOR(t, 100001) {
        while (i < sz(A) && A[i][0] < t)
            i++;
        while (j < sz(events) && events[j][0] <= t) {
            int ix = events[j][1];
            if (ix >= 0) {
                auto [l, r, x, y] = segs[ix];
                if (x <= MAGIC) {
                    blender[{x, y}]++;
                } else {
                    FOR(y0, y, 100001, x) mask[y0]++;
                }
            } else {
                auto [l, r, x, y] = segs[-ix - 1];
                if (x <= MAGIC) {
                    blender[{x, y}]--;
                } else {
                    FOR(y0, y, 100001, x) mask[y0]--;
                }
            }
            j++;
        }

        int bns = -1;
        while (i < sz(A) && A[i][0] == t) {
            if (bns == -1) {
                bns = mask[t];
                EACH(pr, v, blender) {
                    if (t % pr[0] == pr[1])
                        bns += v;
                }
            }
            ans[A[i][1]] = bns;
            i++;
        }
    }

    EACH(x, ans) print(x);
    return 0;
}
0