QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#402696#2560. Streetlightspeaneval_kalaRE 6ms28328kbC++2013.4kb2024-05-01 10:56:292024-05-01 10:56:29

Judging History

你现在查看的是最新测评结果

  • [2024-05-01 10:56:29]
  • 评测
  • 测评结果:RE
  • 用时:6ms
  • 内存:28328kb
  • [2024-05-01 10:56:29]
  • 提交

answer

#pragma GCC optimize(3, "unroll-loops", "no-stack-protector")
#define atsum(l, r) accumulate(l, r, 0)
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>
using namespace std;
using ll = long long;
using ull = unsigned long long;
constexpr int inf = 0x3f3f3f3f;
constexpr ll INF = 0x3f3f3f3f3f3f3f3f;
template <typename T>
inline void chkmin(T &x, T y) { x = min(x, y); }
template <typename T>
inline void chkmax(T &x, T y) { x = max(x, y); }
namespace FastIO
{
// ------------------------------
#define IN_HAS_NEG
#define OUT_HAS_NEG
#define CHK_EOF
#define DISABLE_MMAP
// ------------------------------
#if __cplusplus < 201400
#error Please use C++14 or higher.
#endif
#if __cplusplus > 201700
#define INLINE_V inline
#else
#define INLINE_V
#endif
#if ( defined(LOCAL) || defined (_WIN32) ) && !defined(DISABLE_MMAP)
#define DISABLE_MMAP
#endif
#ifndef DISABLE_MMAP
#include<sys/mman.h>
#endif
#ifdef LOCAL
    inline char gc() { return getchar(); }
    inline void pc(char c) { putchar(c); }
#else
#ifdef DISABLE_MMAP
    INLINE_V constexpr int _READ_SIZE = 1 << 18;
    INLINE_V static char _read_buffer[_READ_SIZE], *_read_ptr = nullptr, *_read_ptr_end = nullptr;
    inline char gc()
    {
        if ( __builtin_expect(_read_ptr == _read_ptr_end, false) )
        {
            _read_ptr = _read_buffer;
            _read_ptr_end = _read_buffer + fread(_read_buffer, 1, _READ_SIZE, stdin);
#ifdef CHK_EOF
            if ( __builtin_expect(_read_ptr == _read_ptr_end, false) ) return EOF;
#endif
        }
        return *_read_ptr++;
    }
#else
    INLINE_V static const char *_read_ptr = (const char *)mmap(nullptr, INT_MAX, 1, 2, 0, 0);
    inline char gc() { return *_read_ptr++; }
#endif
    INLINE_V constexpr int _WRITE_SIZE = 1 << 18;
    INLINE_V static char _write_buffer[_WRITE_SIZE], *_write_ptr = _write_buffer;
    inline void pc(char c)
    {
        *_write_ptr++ = c;
        if ( __builtin_expect(_write_buffer + _WRITE_SIZE == _write_ptr, false) )
        {
            fwrite(_write_buffer, 1, _write_ptr - _write_buffer, stdout);
            _write_ptr = _write_buffer;
        }
    }
    INLINE_V struct _auto_flush
    {
        ~_auto_flush() { fwrite(_write_buffer, 1, _write_ptr - _write_buffer, stdout); }
    }	_auto_flush;
#endif
#ifdef CHK_EOF
    inline bool _isdigit(char c) { return ( c & 16 ) && c != EOF; }
    inline bool _isgraph(char c) { return c > 32 && c != EOF; }
#else
    inline bool _isdigit(char c) { return c & 16; }
    inline bool _isgraph(char c) { return c > 32; }
#endif
    template < class T >
    INLINE_V constexpr bool _is_integer = numeric_limits < T >::is_integer;
    template < class T >
    INLINE_V constexpr bool _is_signed = numeric_limits < T >::is_signed;
    template < class T >
    INLINE_V constexpr bool _is_unsigned = _is_integer < T > && !_is_signed < T >;
    template <> INLINE_V constexpr bool _is_integer < __int128 > = true;
    template <> INLINE_V constexpr bool _is_integer < __uint128_t > = true;
    template <> INLINE_V constexpr bool _is_signed < __int128 > = true;
    template <> INLINE_V constexpr bool _is_unsigned < __uint128_t > = true;
#undef INLINE_V
    inline void read(char &c) { do c = gc(); while ( !_isgraph(c) ); }
    inline void read_cstr(char *s)
    {
        char c = gc(); while ( !_isgraph(c) ) c = gc();
        while ( _isgraph(c) ) *s++ = c, c = gc();
        *s = 0;
    }
    inline void read(string &s)
    {
        char c = gc(); s.clear(); while ( !_isgraph(c) ) c = gc();
        while ( _isgraph(c) ) s.push_back(c), c = gc();
    }
#ifdef IN_HAS_NEG
    template < class T, enable_if_t < _is_signed < T >, int > = 0 >
    inline void read(T &x)
    {
        char c = gc(); bool f = true; x = 0;
        while ( !_isdigit(c) ) { if ( c == 45 ) f = false; c = gc(); }
        if ( f ) while ( _isdigit(c) ) x = x * 10 + ( c & 15 ), c = gc();
        else     while ( _isdigit(c) ) x = x * 10 - ( c & 15 ), c = gc();
    }
    template < class T, enable_if_t < _is_unsigned < T >, int > = 0 >
#else
    template < class T, enable_if_t < _is_integer < T >, int > = 0 >
#endif
    inline void read(T &x)
    {
        char c = gc(); while ( !_isdigit(c) ) c = gc();
        x = 0; while ( _isdigit(c) ) x = x * 10 + ( c & 15 ), c = gc();
    }
    inline void write(char c) { pc(c); }
    inline void write_cstr(const char *s) { while ( *s ) pc(*s++); }
    inline void write(const string &s) { for ( char c : s ) pc(c); }
#ifdef OUT_HAS_NEG
    template < class T, enable_if_t < _is_signed < T >, int > = 0 >
    inline void write(T x)
    {
        char buffer[numeric_limits < T >::digits10 + 1]; int digits = 0;
        if ( x >= 0 )  do buffer[digits++] =  ( x % 10 ) | 48, x /= 10; while ( x );
        else { pc(45); do buffer[digits++] = -( x % 10 ) | 48, x /= 10; while ( x ); }
        while ( digits ) pc(buffer[--digits]);
    }
    template < class T, enable_if_t < _is_unsigned < T >, int > = 0 >
#else
    template < class T, enable_if_t < _is_integer < T >, int > = 0 >
#endif
    inline void write(T x)
    {
        char buffer[numeric_limits < T >::digits10 + 1]; int digits = 0;
        do buffer[digits++] = ( x % 10 ) | 48, x /= 10; while ( x );
        while ( digits ) pc(buffer[--digits]);
    }
    template < int N > struct _tuple_io_helper
    {
        template < class ...T >
        static inline void _read(tuple < T... > &x)
        { _tuple_io_helper < N - 1 >::_read(x), read(get < N - 1 > (x)); }
        template < class ...T >
        static inline void _write(const tuple < T... > &x)
        { _tuple_io_helper < N - 1 >::_write(x), pc(32), write(get < N - 1 > (x)); }
    };
    template <> struct _tuple_io_helper < 1 >
    {
        template < class ...T >
        static inline void _read(tuple < T... > &x) { read(get < 0 > (x)); }
        template < class ...T >
        static inline void _write(const tuple < T... > &x) { write(get < 0 > (x)); }
    };
    template < class ...T >
    inline void read(tuple < T... > &x) { _tuple_io_helper < sizeof...(T) >::_read(x); }
    template < class ...T >
    inline void write(const tuple < T... > &x) { _tuple_io_helper < sizeof...(T) >::_write(x); }
    template < class T1, class T2 >
    inline void read(pair < T1, T2 > &x) { read(x.first), read(x.second); }
    template < class T1, class T2 >
    inline void write(const pair < T1, T2 > &x) { write(x.first), pc(32), write(x.second); }
    template < class T1, class ...T2 >
    inline void read(T1 &x, T2 &...y) { read(x), read(y...); }
    template < class ...T >
    inline void read_cstr(char *x, T *...y) { read_cstr(x), read_cstr(y...); }
    template < class T1, class ...T2 >
    inline void write(const T1 &x, const T2 &...y) { write(x), write(y...); }
    template < class ...T >
    inline void write_cstr(const char *x, const T *...y) { write_cstr(x), write_cstr(y...); }
    template < class T >
    inline void print(const T &x) { write(x); }
    inline void print_cstr(const char *x) { write_cstr(x); }
    template < class T1, class ...T2 >
    inline void print(const T1 &x, const T2 &...y) { print(x), pc(32), print(y...); }
    template < class ...T >
    inline void print_cstr(const char *x, const T *...y) { print_cstr(x), pc(32), print_cstr(y...); }
    inline void println() { pc(10); }
    inline void println_cstr() { pc(10); }
    template < class ...T >
    inline void println(const T &...x) { print(x...), pc(10); }
    template < class ...T >
    inline void println_cstr(const T *...x) { print_cstr(x...), pc(10); }
}
using namespace FastIO;
template <typename T>
inline void clear(T &x) {
    T y;
    swap(x, y);
}
const int N = 4e5 + 10;
int n, q;
priority_queue<pair<int, int> > q1;
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> >> q2;
struct Uniquer {
    int a[N << 1], len;
    inline void push(int x) { a[++len] = x; }
    inline void uniq() { sort(a + 1, a + len + 1), len = unique(a + 1, a + len + 1) - a - 1; }
    inline int f(int x) { int c = lower_bound(a + 1, a + len + 1, x) - a; assert(a[c] == x); return lower_bound(a + 1, a + len + 1, x) - a; }
} tab, T, T2;
ll ans[N];
struct Segtree {
    int mx[N << 2], mn[N << 2], smx[N << 2], smn[N << 2], res[N << 2];
    void build(int u, int L, int R) {
        mx[u] = n + 1, mn[u] = 0, smx[u] = -inf, smn[u] = inf, res[u] = 0;
        if (L == R) return;
        int M = L + R >> 1;
        build(u << 1, L, M), build(u << 1 | 1, M + 1, R);
    }
    inline void pushdown(int u) {
        chkmin(mx[u << 1], mx[u]), chkmin(mx[u << 1 | 1], mx[u]);
        chkmax(mn[u << 1], mn[u]), chkmax(mn[u << 1 | 1], mn[u]);
        if (mx[u << 1] == mx[u] && mn[u << 1] == mn[u]) res[u << 1] += res[u];
        if (mx[u << 1 | 1] == mx[u] && mn[u << 1 | 1] == mn[u]) res[u << 1 | 1] += res[u];
        res[u] = 0;
    }
    inline void pushup(int u) {
        smn[u] = inf, smx[u] = -inf, mx[u] = max(mx[u << 1], mx[u << 1 | 1]), mn[u] = min(mn[u << 1], mn[u << 1 | 1]);
        chkmax(smx[u], mx[u] == mx[u << 1] ? smx[u << 1] : mx[u << 1]);
        chkmax(smx[u], mx[u] == mx[u << 1 | 1] ? smx[u << 1 | 1] : mx[u << 1 | 1]);
        chkmin(smn[u], mn[u] == mn[u << 1] ? smn[u << 1] : mn[u << 1]);
        chkmin(smn[u], mn[u] == mn[u << 1 | 1] ? smn[u << 1 | 1] : mn[u << 1 | 1]);
    }
    inline void update(int u, int L, int R, int l, int r, int pl, int pr ){
        if (L > r || R < l) return;
        assert(mx[u] != smx[u] && mn[u] != smn[u]);
        if (L >= l && R <= r) {
            if (mx[u] <= pr && mn[u] >= pl) return;
            if (smx[u] < pr && smn[u] > pl) {
                if (mx[u] > pr && mn[u] < pl) return mx[u] = pr, mn[u] = pl, void(++res[u]);
                return chkmin(mx[u], pr), chkmax(mn[u], pl);            
            }
        }
        int M = L + R >> 1;
        pushdown(u);
        update(u << 1, L, M, l, r, pl, pr);
        update(u << 1 | 1, M + 1, R, l, r, pl, pr);
        pushup(u);
    }
    inline void print(int u, int L, int R) {
        if (L == R) {
            ans[T2.a[L]] += res[u], ans[T2.a[L + 1]] -= res[u];
            return;
        }
        int M = L + R >> 1;
        pushdown(u);
        print(u << 1, L, M), print(u << 1 | 1, M + 1, R);
    }
} seg;
// struct Brute {
//     int mx[N], mn[N], res[N];
//     inline void build(int u, int L, int R) {
//         for (int i = L; i <= R; i++) res[i] = 0, mx[i] = n + 1, mn[i] = 0;
//     }
//     inline void update(int u, int L, int R, int l, int r, int pl, int pr) {
//         for (int i = l; i <= r; i++) {
//             if (mx[i] > pr && mn[i] < pl) ++res[i];
//             chkmin(mx[i], pr), chkmax(mn[i], pl);
//         }
//     }
//     inline void print(int u, int L, int R) {
//         for (int i = L; i <= R; i++) ans[T2.a[i]] += res[i], ans[T2.a[i + 1]] -= res[i];
//     }
// } seg;
int a[N], pr[N];
vector<pair<int, int> > vec[N];
vector<tuple<int, int, int, int> > pa[N];
vector<tuple<int, int, int>  > qa[N];
void solvex(int x, int M) {
    clear(q1), clear(q2);
    q1.emplace(-1, 0), q2.emplace(n + 2, 0);
    T.len = 0;
    int cc = 0;
    sort(qa[x].begin(), qa[x].end());
    int p = 0;
    T.push(q + 1);
    for (auto [l, r, v] : qa[x]) T.push(l), T.push(r);
    T.uniq();
    for (int i = 1; i < T.len; i++) {
        while (p < qa[x].size() && get<0>(qa[x][p]) <= T.a[i]) {
            auto [l, r, v] = qa[x][p++];
            pr[++cc] = r;
            if (v <= M) q1.emplace(v, cc);
            else q2.emplace(v, cc);
        }
        while (pr[q1.top().second] <= T.a[i]) q1.pop();
        while (pr[q2.top().second] <= T.a[i]) q2.pop();
        pa[x].emplace_back(T.a[i], T.a[i + 1], q1.top().first, q2.top().first);
    }
    clear(qa[x]);
}
int pl = 0;
void solve(int L, int R) {
    if (L == R) return;
    int M = L + R >> 1;
    solve(L, M), solve(M + 1, R);
    tab.len = 0, T2.len = 0;
    T2.push(q + 1);
    for (int i = L; i <= R; i++) {
        for (int j = 0; j + 1 < vec[i].size(); j++) qa[vec[i][j].second].emplace_back(vec[i][j].first, vec[i][j + 1].first, i), tab.push(vec[i][j].second), T2.push(vec[i][j].first);
        qa[vec[i].back().second].emplace_back(vec[i].back().first, q + 1, i), tab.push(vec[i].back().second);
        T2.push(vec[i].back().first);
    }
    tab.uniq(), T2.uniq();
    for (int i = 1; i <= tab.len; i++) solvex(tab.a[i], M);
    seg.build(1, 1, T2.len - 1);
    pl += T2.len;
    assert(pl <= 4000000);
    for (int i = tab.len; i; i--) {
        for (auto [tl, tr, pl, pr] : pa[tab.a[i]]) {
            // cerr << "find x:" << L << ' ' << R << ' ' << tab.a[i] << ' ' << tl << ' ' << tr << ' ' << pl << ' ' << pr << endl;
            int ptl = T2.f(tl), ptr = T2.f(tr);
            seg.update(1, 1, T2.len - 1, ptl, ptr - 1, pl, pr);
        }
        clear(pa[tab.a[i]]);
    }
    seg.print(1, 1, T2.len - 1);
}
int main() {
    pr[0] = inf;
    read(n, q);
    for (int i = 1; i <= n; i++) read(a[i]), vec[i].emplace_back(0, a[i]), tab.push(a[i]);
    for (int i = 1; i <= q; i++) {
        int x, h;
        read(x, h), vec[x].emplace_back(i, h), tab.push(h);
    }
    tab.uniq();
    for (int i = 1; i <= n; i++)
        for (auto &[t, v] : vec[i]) v = tab.f(v);
    solve(1, n);
    for (int i = 1; i <= q;i ++) ans[i] += ans[i - 1];
    for (int i  = 0; i <= q; i++) println(ans[i]);
    return 0;
}
/*
6 2
4 2 2 2 4 6
4 6
6 4
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 26228kb

input:

6 2
4 2 2 2 4 6
4 6
6 4

output:

3
2
2

result:

ok 3 lines

Test #2:

score: 0
Accepted
time: 0ms
memory: 24192kb

input:

50 100
310081863 722273055 654741011 310081863 654741011 722273055 654741011 722273055 654741011 654741011 654741011 310081863 310081863 722273055 654741011 654741011 654741011 722273055 310081863 654741011 310081863 310081863 310081863 722273055 310081863 654741011 654741011 310081863 722273055 722...

output:

28
28
28
29
30
31
31
31
31
31
31
31
31
32
33
34
34
33
33
33
33
32
32
31
31
31
32
32
31
31
31
31
30
30
30
31
31
31
31
31
31
30
30
29
30
31
32
32
32
32
32
31
32
33
33
33
33
32
32
31
32
33
31
31
32
31
32
31
31
31
30
31
30
29
29
28
28
29
28
28
27
27
27
27
27
27
26
27
28
27
28
29
28
28
28
28
29
29
28
29
28

result:

ok 101 lines

Test #3:

score: 0
Accepted
time: 3ms
memory: 24172kb

input:

50 100
93308794 275481889 130830018 675774101 130830018 93308794 275481889 999873895 275481889 104418887 130830018 275481889 675774101 999873895 130830018 841188804 360486542 104418887 140762403 275481889 275481889 770511267 104418887 140762403 93308794 675774101 104418887 770511267 130830018 933087...

output:

12
12
11
11
11
11
11
11
10
10
10
10
10
10
10
11
11
11
11
12
12
12
12
12
11
10
11
11
11
11
11
12
13
12
12
13
13
14
12
11
11
10
10
10
10
10
9
9
9
9
9
9
8
9
10
10
9
10
9
9
9
10
10
11
12
12
13
13
13
13
14
14
13
13
13
12
12
12
12
13
12
12
12
12
12
12
13
13
13
13
15
15
15
17
18
18
17
17
16
16
15

result:

ok 101 lines

Test #4:

score: 0
Accepted
time: 6ms
memory: 24152kb

input:

50 100
195248019 905127308 129122336 764519854 338556860 795943323 554412442 338556860 217191782 140699690 654772489 386182517 217191782 37485244 795943323 924638428 795943323 820028162 855279832 795943323 129122336 554412442 195248019 764519854 810525122 554412442 201706134 661330059 129122336 2090...

output:

5
5
6
5
5
5
4
4
3
3
3
3
3
2
4
3
3
3
4
5
5
5
5
5
5
5
5
4
4
4
5
6
6
5
5
4
4
4
3
3
3
3
3
3
4
4
4
4
3
3
4
3
3
3
3
3
3
3
3
3
3
3
4
4
4
4
4
5
5
5
5
6
6
6
5
5
5
5
5
6
6
6
6
7
7
7
7
7
7
7
7
7
7
7
7
7
7
8
8
8
7

result:

ok 101 lines

Test #5:

score: 0
Accepted
time: 0ms
memory: 28328kb

input:

50 100
772094573 19576803 263817454 873867094 557813690 952336439 500513802 392057352 305209480 199018938 206776586 514630037 466387810 403552086 50423285 658534934 19576803 404488754 179660945 591777562 262850065 817419372 680762089 591777562 424021147 403552086 718896141 456431927 680762089 595426...

output:

1
1
0
0
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
0
0
0
0
0
1
1
1
1
1
1
0
0
0
0
1
2
2
2
3
3
3
3
3
3
2
2
2
2
2
2
2
1
1
1
0
0
0
0
0
0
0
0
0
1
2
2
3
3
3
3
3
3
2
2
2
3
3
3
3
3
3
3

result:

ok 101 lines

Test #6:

score: 0
Accepted
time: 0ms
memory: 28184kb

input:

50 100
5096114 61078240 254964021 318250156 571031769 256037951 208426954 833646260 732869624 746606948 226729785 151221431 611264696 351005299 205027954 706057630 453231547 874058912 462474957 366832522 823051853 289489922 109072951 103985450 269915659 377686154 809672410 12123621 732787174 9017273...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

result:

ok 101 lines

Test #7:

score: 0
Accepted
time: 3ms
memory: 26212kb

input:

50 100
976187983 976187983 879080743 976187983 827737130 827737130 827737130 827737130 815905933 811453113 789018592 789018592 681089922 675640665 659464656 635119734 635119734 633485638 633485638 567930339 552957008 484438465 484438465 484438465 387753272 377659696 376161946 976187983 367642977 376...

output:

16
15
14
14
15
16
17
17
18
18
31
30
29
28
27
26
25
24
23
22
21
20
20
19
20
19
18
18
18
18
18
17
17
16
16
16
16
15
15
15
15
14
13
12
12
12
12
11
11
10
9
9
9
8
8
7
7
6
7
6
7
7
7
8
8
7
8
10
10
10
10
10
11
10
10
12
14
15
15
16
16
15
16
18
19
20
26
26
27
28
29
28
28
27
26
25
24
23
23
22
21

result:

ok 101 lines

Test #8:

score: 0
Accepted
time: 0ms
memory: 24104kb

input:

50 100
843864537 245114944 227661173 137675097 918583745 80278395 44678681 37169219 37007425 27167524 4382795 4043558 3655016 3624538 2994987 1979195 1407769 819862 771067 665903 137891 137891 665903 771067 819862 1407769 1979195 2994987 3624538 3655016 4043558 4382795 27167524 37007425 37142735 305...

output:

17
17
16
15
7
7
8
5
5
5
5
5
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
1
0
0
0
1
1
2
3
3
4
4
4
4
5
6
6
7
8
9
10
11
12
13
14
14
14
14
14
15
16
16
16
16
17
18
19
19
20
21
20
19
18
15
14
14
14
13
7
6
6
6
6
6
6
6
6
6
6
5
5
4
4
4
3
3
3
3
3
3
2
2
2
2

result:

ok 101 lines

Test #9:

score: 0
Accepted
time: 3ms
memory: 24120kb

input:

50 100
920202355 768392166 755066475 630812635 617367313 601334965 450742259 367726734 265094786 151773018 77676966 53524889 53524889 77676966 151773018 265094786 205222950 154745305 57476426 57476426 154745305 294856628 367726734 450742259 601334965 617367313 630812635 481253037 481253037 755066475...

output:

19
20
20
19
18
17
16
15
14
13
12
11
10
10
10
10
9
8
7
7
7
8
7
7
7
6
6
5
5
5
5
4
4
3
3
4
3
3
3
3
3
3
3
3
2
2
3
3
3
3
3
4
4
5
5
5
6
6
6
6
8
10
10
11
12
13
13
14
14
15
15
15
20
21
22
21
19
17
17
17
15
14
13
13
13
13
13
12
12
11
10
8
8
8
8
7
7
7
7
7
7

result:

ok 101 lines

Test #10:

score: -100
Runtime Error

input:

100000 250000
10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 1...

output:


result: