头像

Segment_Tree

$Segment$_$Tree$ $can$ $smash$ $any$ $data$ $structure$




离线:1小时前


最近来访(737)
用户头像
杰杰酱
用户头像
不拿周赛牌不改名
用户头像
Charlie0998
用户头像
liuhaijie
用户头像
柳明月清风
用户头像
小zz
用户头像
EnergyMaking
用户头像
LCY_67
用户头像
铁锅炖大鹅
用户头像
非黑即白
用户头像
不到榜一不改名
用户头像
WangJY
用户头像
天元之弈
用户头像
FoLiaGe丶
用户头像
周赛三题必WA
用户头像
梦忆晴天
用户头像
XuYangyang
用户头像
AcWing2AK
用户头像
chyMIT2028
用户头像
她的店里只卖樱花

新鲜事 原文

盼望着,盼望着,模拟赛来了,CSP的脚步近了。 一切都像刚WA的样子,欣欣然重构代码。代码复杂度朗润起来了,时间复杂度涨起来了,CE的标志红起来了。 毒瘤数据偷偷地从土里钻出来,嫩嫩的,绿绿的。洛谷里,CodeForces里,瞧去,一大片一大片满是的。坐着,躺着,写两个for,码几脚while,跑几趟dfs,搜几回暴力。TLE轻悄悄的,MLE软绵绵的。 POJ、HDU、51nod,你不让我,我不让你,都开满了WA赶趟儿。红的像火,粉的像霞,白的像雪。WA里带着RE;闭了眼,评测界面仿佛已经满是UKE、ERR、OLE。花下成千成百的蜜蜂嗡嗡地闹着,大小的蝴蝶飞来飞去。0分遍地是:杂样儿,DP没初始化的,数学公式写错的,散在评测机里,像眼睛,像星星,还眨呀眨的。 “吹面不寒AK风”,不错的,像CCF主席的手抚摸着你。风里带来些新翻的AC的气息,混着打表味儿,还有各种骗分的香,都在微微润湿的AK里酝酿。模拟将巢安在长篇文章当中,高兴起来了,呼朋引伴地卖弄超过200行的代码,唱出宛转的AC音乐,与轻风流水应和着。IOI通过的短笛,这时候也成天嘹亮地响着。 Debug是最寻常的,一调就是三两天。可别恼。看,像无限循环,像scanf不写&,像数组越界,密密地斜织着,人家exe上全笼着一层01串。大佬的评测却AC得发亮,蒟蒻的评测也青蛙得逼你的眼。傍晚时候,上灯了,一点点算法错误的光,烘托出一片贪心错误的夜。在乡下,小路上,石桥边,有撑起伞慢慢走了1e18秒的人。还有地里工作的码农,披着电源戴着黑帽子的。他们的电脑,稀稀疏疏的在调试里静默着。 天上AKIOI渐渐多了,地上AKNOI也多了。俄国中国,克罗地亚,波罗的海,也赶趟儿似的,一个个都出来了。AK CSP-J,AK CSP-S,各AK各的一份事去。“一年之计在于CSP”,刚起头儿,有的是爆零。


活动打卡代码 AcWing 4268. 性感素数

全网最快15ms!!!!!

#include <cstdio>
#include <cmath>

#pragma GCC target ("avx,sse2,sse3,sse4,mmx")
#pragma GCC optimize (2)
#pragma GCC optimize (3)
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("inline")
#pragma GCC optimize ("-fgcse")
#pragma GCC optimize ("-fgcse-lm")
#pragma GCC optimize ("-fipa-sra")
#pragma GCC optimize ("-ftree-pre")
#pragma GCC optimize ("-ftree-vrp")
#pragma GCC optimize ("-fpeephole2")
#pragma GCC optimize ("-ffast-math")
#pragma GCC optimize ("-fsched-spec")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize ("-falign-jumps")
#pragma GCC optimize ("-falign-loops")
#pragma GCC optimize ("-falign-labels")
#pragma GCC optimize ("-fdevirtualize")
#pragma GCC optimize ("-fcaller-saves")
#pragma GCC optimize ("-fcrossjumping")
#pragma GCC optimize ("-fthread-jumps")
#pragma GCC optimize ("-funroll-loops")
#pragma GCC optimize ("-fwhole-program")
#pragma GCC optimize ("-freorder-blocks")
#pragma GCC optimize ("-fschedule-insns")
#pragma GCC optimize ("inline-functions")
#pragma GCC optimize ("-ftree-tail-merge")
#pragma GCC optimize ("-fschedule-insns2")
#pragma GCC optimize ("-fstrict-aliasing")
#pragma GCC optimize ("-fstrict-overflow")
#pragma GCC optimize ("-falign-functions")
#pragma GCC optimize ("-fcse-skip-blocks")
#pragma GCC optimize ("-fcse-follow-jumps")
#pragma GCC optimize ("-fsched-interblock")
#pragma GCC optimize ("-fpartial-inlining")
#pragma GCC optimize ("no-stack-protector")
#pragma GCC optimize ("-freorder-functions")
#pragma GCC optimize ("-findirect-inlining")
#pragma GCC optimize ("-fhoist-adjacent-loads")
#pragma GCC optimize ("-frerun-cse-after-loop")
#pragma GCC optimize ("inline-small-functions")
#pragma GCC optimize ("-finline-small-functions")
#pragma GCC optimize ("-ftree-switch-conversion")
#pragma GCC optimize ("-foptimize-sibling-calls")
#pragma GCC optimize ("-fexpensive-optimizations")
#pragma GCC optimize ("-funsafe-loop-optimizations")
#pragma GCC optimize ("inline-functions-called-once")
#pragma GCC optimize ("-fdelete-null-pointer-checks")

namespace IO
{
    #define DECIMAL 6
    #define BUF_SIZE 10
    #define LL long long
    char obuf[BUF_SIZE], *p3 = obuf;
    inline char gc () { static char buf[BUF_SIZE], *p1 = buf, *p2 = buf; return p1 == p2 && (p2 = (p1 = buf) + fread (buf, 1, BUF_SIZE, stdin), p1 == p2) ? EOF : *p1++; }
    inline void pc (char x) { (p3 - obuf < (1 << 21)) ? (*p3++ = x) : (fwrite (obuf, p3 - obuf, 1, stdout), p3 = obuf, *p3++ = x); }
    inline void read (char &ch) { ch = gc (); }
    inline void read (char s[]) { char ch = gc (); while (ch != ' ' && ch != '\n') *s++ = ch, ch = gc (); }
    inline void read (int &x) { x = 0; bool f = 0; char ch = gc (); while (ch < '0' || ch > '9') f |= ch == '-', ch = gc (); while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + (ch ^ 48), ch = gc (); x = f ? ~x + 1 : x; }
    inline void read (long long &x) { x = 0; bool f = 0; char ch = gc (); while (ch < '0' || ch > '9') f |= ch == '-', ch = gc (); while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + (ch ^ 48), ch = gc (); x = f ? ~x + 1 : x; }
    inline void read (double &x) { x = 0; bool f = 0; char ch = gc (); while (ch < '0' || ch > '9') f |= ch == '-', ch = gc (); while (ch >= '0' && ch <= '9') x = (x * 10) + (ch ^ 48), ch = gc (); if (ch == '.') { double tmp = 1; ch = getchar(); while(ch >= '0' && ch <= '9') tmp /= 10.0, x += tmp * (ch ^ 48), ch = gc (); } x = f ? -x : x; }
    inline void write (char ch) { pc (ch); }
    inline void write (char s[]) { while (*s) pc (*s++); }
    inline void write (int x) { static char c[11]; unsigned p = 0; if (x < 0) pc ('-'), x = ~x + 1; if (!x) { pc ('0'); return ; } while (x) c[++p] = x % 10 ^ 48, x /= 10; while (p) pc (c[p]), --p; }
    inline void write (long long x) { static char c[20]; unsigned p = 0; if (x < 0) pc ('-'), x = ~x + 1; if (!x) { pc ('0'); return ; } while (x) c[++p] = x % 10 ^ 48, x /= 10; while (p) pc (c[p]), --p; }
    inline void write (double x, int y = DECIMAL) { static LL mul[] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000, 10000000000LL, 100000000000LL, 1000000000000LL, 10000000000000LL, 100000000000000LL, 1000000000000000LL, 10000000000000000LL, 100000000000000000LL}; if (x < -1e-12) pc ('-'), x = -x; x *= mul[y]; LL x1 = (LL) floor (x); if (floor (x) >= 0.5) ++x1; LL x2 = x1 / mul[y], x3 = x1 - x2 * mul[y]; write (x2); pc ('.'); for (size_t i = 1; x3 * mul[i] < mul[y]; ++i) pc ('0'); write (x3); }
    template <class T, class... U> inline void read (T &x, U &...t) { read (x), read (t...); }
    template <class T, class... U> inline void write (T x, U ...t) { write (x), write (t...); }
    inline void flush () { fwrite (obuf, p3 - obuf, 1, stdout); }
};

using namespace IO;

const int p[] = {7, 11, 13, 17, 19, 23, 29, 31};

inline bool isPrime (int x) noexcept
{
    if (x < 7) return x == 2 || x == 3 || x == 5;
    if (!(x & 1 && x % 3 && x % 5) || x % 6 != 1 && x % 6 != 5) return false;
    for (int i = 0; 1ll * i * i <= x; i += 30)
        for (int j = 0; j < 8 && x > i + p[j]; ++j)
            if (x % (i + p[j]) == 0) return false;
    return true;
}

signed main ()
{
    int x;
    read (x);
    if (!isPrime (x)) write ((char *) "No\n");
    else
    {    
        bool f = false;
        if (f |= isPrime (x - 6)) write ((char *) "Yes\n", x - 6);
        else if (f |= isPrime (x + 6)) write ((char *) "Yes\n", x + 6);
        if (f) goto exit;
        else write ((char *) "No\n");
    }
    for (int i = x + 1; ; ++i)
        if (isPrime (i) && (isPrime (i - 6) || isPrime (i + 6)))
        {
            write (i);
            goto exit;
        }
    exit : flush ();
    return 0;
}



利用车轮分解法判断素数,其原理是把素数映射到一个轮上, 时间复杂度大约为$O(\frac {\sqrt n}{3.75})$(别搜了,网上找不到)

Code:

#include <cstdio>
#include <cmath>

#pragma GCC target ("avx,sse2,sse3,sse4,mmx")
#pragma GCC optimize (2)
#pragma GCC optimize (3)
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("inline")
#pragma GCC optimize ("-fgcse")
#pragma GCC optimize ("-fgcse-lm")
#pragma GCC optimize ("-fipa-sra")
#pragma GCC optimize ("-ftree-pre")
#pragma GCC optimize ("-ftree-vrp")
#pragma GCC optimize ("-fpeephole2")
#pragma GCC optimize ("-ffast-math")
#pragma GCC optimize ("-fsched-spec")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize ("-falign-jumps")
#pragma GCC optimize ("-falign-loops")
#pragma GCC optimize ("-falign-labels")
#pragma GCC optimize ("-fdevirtualize")
#pragma GCC optimize ("-fcaller-saves")
#pragma GCC optimize ("-fcrossjumping")
#pragma GCC optimize ("-fthread-jumps")
#pragma GCC optimize ("-funroll-loops")
#pragma GCC optimize ("-fwhole-program")
#pragma GCC optimize ("-freorder-blocks")
#pragma GCC optimize ("-fschedule-insns")
#pragma GCC optimize ("inline-functions")
#pragma GCC optimize ("-ftree-tail-merge")
#pragma GCC optimize ("-fschedule-insns2")
#pragma GCC optimize ("-fstrict-aliasing")
#pragma GCC optimize ("-fstrict-overflow")
#pragma GCC optimize ("-falign-functions")
#pragma GCC optimize ("-fcse-skip-blocks")
#pragma GCC optimize ("-fcse-follow-jumps")
#pragma GCC optimize ("-fsched-interblock")
#pragma GCC optimize ("-fpartial-inlining")
#pragma GCC optimize ("no-stack-protector")
#pragma GCC optimize ("-freorder-functions")
#pragma GCC optimize ("-findirect-inlining")
#pragma GCC optimize ("-fhoist-adjacent-loads")
#pragma GCC optimize ("-frerun-cse-after-loop")
#pragma GCC optimize ("inline-small-functions")
#pragma GCC optimize ("-finline-small-functions")
#pragma GCC optimize ("-ftree-switch-conversion")
#pragma GCC optimize ("-foptimize-sibling-calls")
#pragma GCC optimize ("-fexpensive-optimizations")
#pragma GCC optimize ("-funsafe-loop-optimizations")
#pragma GCC optimize ("inline-functions-called-once")
#pragma GCC optimize ("-fdelete-null-pointer-checks")

namespace IO
{
    #define DECIMAL 6
    #define BUF_SIZE 10
    #define LL long long
    char obuf[BUF_SIZE], *p3 = obuf;
    inline char gc () { static char buf[BUF_SIZE], *p1 = buf, *p2 = buf; return p1 == p2 && (p2 = (p1 = buf) + fread (buf, 1, BUF_SIZE, stdin), p1 == p2) ? EOF : *p1++; }
    inline void pc (char x) { (p3 - obuf < (1 << 21)) ? (*p3++ = x) : (fwrite (obuf, p3 - obuf, 1, stdout), p3 = obuf, *p3++ = x); }
    inline void read (char &ch) { ch = gc (); }
    inline void read (char s[]) { char ch = gc (); while (ch != ' ' && ch != '\n') *s++ = ch, ch = gc (); }
    inline void read (int &x) { x = 0; bool f = 0; char ch = gc (); while (ch < '0' || ch > '9') f |= ch == '-', ch = gc (); while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + (ch ^ 48), ch = gc (); x = f ? ~x + 1 : x; }
    inline void read (long long &x) { x = 0; bool f = 0; char ch = gc (); while (ch < '0' || ch > '9') f |= ch == '-', ch = gc (); while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + (ch ^ 48), ch = gc (); x = f ? ~x + 1 : x; }
    inline void read (double &x) { x = 0; bool f = 0; char ch = gc (); while (ch < '0' || ch > '9') f |= ch == '-', ch = gc (); while (ch >= '0' && ch <= '9') x = (x * 10) + (ch ^ 48), ch = gc (); if (ch == '.') { double tmp = 1; ch = getchar(); while(ch >= '0' && ch <= '9') tmp /= 10.0, x += tmp * (ch ^ 48), ch = gc (); } x = f ? -x : x; }
    inline void write (char ch) { pc (ch); }
    inline void write (char s[]) { while (*s) pc (*s++); }
    inline void write (int x) { static char c[11]; unsigned p = 0; if (x < 0) pc ('-'), x = ~x + 1; if (!x) { pc ('0'); return ; } while (x) c[++p] = x % 10 ^ 48, x /= 10; while (p) pc (c[p]), --p; }
    inline void write (long long x) { static char c[20]; unsigned p = 0; if (x < 0) pc ('-'), x = ~x + 1; if (!x) { pc ('0'); return ; } while (x) c[++p] = x % 10 ^ 48, x /= 10; while (p) pc (c[p]), --p; }
    inline void write (double x, int y = DECIMAL) { static LL mul[] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000, 10000000000LL, 100000000000LL, 1000000000000LL, 10000000000000LL, 100000000000000LL, 1000000000000000LL, 10000000000000000LL, 100000000000000000LL}; if (x < -1e-12) pc ('-'), x = -x; x *= mul[y]; LL x1 = (LL) floor (x); if (floor (x) >= 0.5) ++x1; LL x2 = x1 / mul[y], x3 = x1 - x2 * mul[y]; write (x2); pc ('.'); for (size_t i = 1; x3 * mul[i] < mul[y]; ++i) pc ('0'); write (x3); }
    template <class T, class... U> inline void read (T &x, U &...t) { read (x), read (t...); }
    template <class T, class... U> inline void write (T x, U ...t) { write (x), write (t...); }
    inline void flush () { fwrite (obuf, p3 - obuf, 1, stdout); }
};

using namespace IO;

const int p[] = {7, 11, 13, 17, 19, 23, 29, 31};

inline bool isPrime (int x) noexcept
{
    if (x < 7) return x == 2 || x == 3 || x == 5;
    if (!(x & 1 && x % 3 && x % 5) || x % 6 != 1 && x % 6 != 5) return false;
    for (int i = 0; 1ll * i * i <= x; i += 30)
        for (int j = 0; j < 8 && x > i + p[j]; ++j)
            if (x % (i + p[j]) == 0) return false;
    return true;
}

signed main ()
{
    int x;
    read (x);
    if (!isPrime (x)) write ((char *) "No\n");
    else
    {    
        bool f = false;
        if (f |= isPrime (x - 6)) write ((char *) "Yes\n", x - 6);
        else if (f |= isPrime (x + 6)) write ((char *) "Yes\n", x + 6);
        if (f) goto exit;
        else write ((char *) "No\n");
    }
    for (int i = x + 1; ; ++i)
        if (isPrime (i) && (isPrime (i - 6) || isPrime (i + 6)))
        {
            write (i);
            goto exit;
        }
    exit : flush ();
    return 0;
}


新鲜事 原文

AcWing《暑假每日一题2022》拼团优惠!https://www.acwing.com/activity/content/introduction/1934/group_buy/71416/, 6.18-6.20限时狂欢,全场6折起!


活动打卡代码 AcWing 851. spfa求最短路

#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>

#pragma GCC optimize (2, 3, "Ofast", "-ffast-math")

using namespace std;

const int N = 1e5 + 10, INF = 0x3f3f3f3f;

struct edge
{
    int v, w;
};

int n, m;
vector <edge> g[N];

inline int spfa (vector <edge> g[N], int srt, int end) noexcept
{
    int dist[N];
    bool st[N];
    queue <int> q;
    memset (dist, INF, sizeof dist);
    dist[srt] = 0;
    memset (st, false, sizeof st);
    st[srt] = true;
    q.push (srt);

    while (!q.empty ())
    {
        int u = q.front (); q.pop ();
        st[u] = false;

        for (auto &it : g[u])
        {
            auto &v = it.v, &w = it.w;
            if (dist[v] > dist[u] + w)
            {
                dist[v] = dist[u] + w;
                if (!st[v]) q.push (v), st[v] = true;
            }
        }
    }

    return dist[end];
}

int main ()
{
    scanf ("%d %d", &n, &m);
    while (m--)
    {
        int u, v, w;
        scanf ("%d %d %d", &u, &v, &w);
        g[u].push_back ({v, w});
    }

    int ans = spfa (g, 1, n);
    if (ans == INF) puts ("impossible");
    else printf ("%d\n", ans);
    return 0;
}


活动打卡代码 AcWing 902. 最短编辑距离

#include <cstdio>
#include <algorithm>

#pragma GCC optimize (2, 3, "Ofast", "-ffast-math")

using std :: min;

const int N = 1e3 + 10;

int n, m, opt[N][N];
char a[N], b[N];

int main ()
{
    scanf ("%d %s %d %s", &n, a + 1, &m, b + 1);

    for (int i = 1; i <= m; ++i) opt[0][i] = i;
    for (int i = 1; i <= n; ++i) opt[i][0] = i;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
        {
            opt[i][j] = min (opt[i - 1][j] + 1, opt[i][j - 1] + 1);
            if (a[i] == b[j]) opt[i][j] = min (opt[i][j], opt[i - 1][j - 1]);
            else opt[i][j] = min (opt[i][j], opt[i - 1][j - 1] + 1);
        }

    printf ("%d\n", opt[n][m]);
    return 0;
}


题目讨论 AcWing 4429. v

m



新鲜事 原文

Segment_Tree
1个月前
y总邮箱:yanlaodaweiwoshiye@163.com



Segment_Tree
1个月前

双指针大法好!!!

将数组扫一遍,每次找到相邻两个$0$位置, $0_1$的下标记为lst($last$),$0_2$的下标记为cur($current$),将$[lst, cur]$这个区间的中点的下标记为mid.

对于每个$i$ $(lst < i \le mid)$,$b_i = i - lst$.

对于每个$j$ $(mid < j \le cur)$,$b_j = cur - j$.

边界情况: 当最后一个$cur$找不到时 ($a_i != 0$, $lst \le i \le n$), 将$b_j$标记为$j - lst$ $(lst \le j \le cur)$.

Code:

#include <cstdio>

const int N = 2e5 + 10;

int n, a[N], b[N], lst = -N, cur;

int main ()
{
    scanf ("%d", &n);
    for (int i = 1; i <= n; ++i) scanf ("%d", &a[i]);
    for (int i = 1; i <= n; ++i)
    {
        for (int j = i; j <= n; ++j)
            if (!a[cur = j]) break;
        if (!a[cur])
            for (int j = i; j <= cur; ++j) b[j] = j <= lst + cur >> 1 ? j - lst : cur - j;
        else
        {
            for (int j = i; j <= n; ++j) b[j] = j - lst;
            break;
        }
        lst = cur, i = lst;
    }
    for (int i = 1; i <= n; ++i) printf ("%d ", b[i]); 
    return 0;
}

终极卡常版: $113ms$

#include <cstdio>
#include <cmath>

#pragma GCC target ("avx,sse2,sse3,sse4,mmx")
#pragma GCC optimize (2)
#pragma GCC optimize (3)
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("inline")
#pragma GCC optimize ("-fgcse")
#pragma GCC optimize ("-fgcse-lm")
#pragma GCC optimize ("-fipa-sra")
#pragma GCC optimize ("-ftree-pre")
#pragma GCC optimize ("-ftree-vrp")
#pragma GCC optimize ("-fpeephole2")
#pragma GCC optimize ("-ffast-math")
#pragma GCC optimize ("-fsched-spec")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize ("-falign-jumps")
#pragma GCC optimize ("-falign-loops")
#pragma GCC optimize ("-falign-labels")
#pragma GCC optimize ("-fdevirtualize")
#pragma GCC optimize ("-fcaller-saves")
#pragma GCC optimize ("-fcrossjumping")
#pragma GCC optimize ("-fthread-jumps")
#pragma GCC optimize ("-funroll-loops")
#pragma GCC optimize ("-fwhole-program")
#pragma GCC optimize ("-freorder-blocks")
#pragma GCC optimize ("-fschedule-insns")
#pragma GCC optimize ("inline-functions")
#pragma GCC optimize ("-ftree-tail-merge")
#pragma GCC optimize ("-fschedule-insns2")
#pragma GCC optimize ("-fstrict-aliasing")
#pragma GCC optimize ("-fstrict-overflow")
#pragma GCC optimize ("-falign-functions")
#pragma GCC optimize ("-fcse-skip-blocks")
#pragma GCC optimize ("-fcse-follow-jumps")
#pragma GCC optimize ("-fsched-interblock")
#pragma GCC optimize ("-fpartial-inlining")
#pragma GCC optimize ("no-stack-protector")
#pragma GCC optimize ("-freorder-functions")
#pragma GCC optimize ("-findirect-inlining")
#pragma GCC optimize ("-fhoist-adjacent-loads")
#pragma GCC optimize ("-frerun-cse-after-loop")
#pragma GCC optimize ("inline-small-functions")
#pragma GCC optimize ("-finline-small-functions")
#pragma GCC optimize ("-ftree-switch-conversion")
#pragma GCC optimize ("-foptimize-sibling-calls")
#pragma GCC optimize ("-fexpensive-optimizations")
#pragma GCC optimize ("-funsafe-loop-optimizations")
#pragma GCC optimize ("inline-functions-called-once")
#pragma GCC optimize ("-fdelete-null-pointer-checks")

const int N = 2e5 + 10;

int n, a[N], b[N], lst = -N, cur;

namespace IO
{
    #define DECIMAL 6
    #define BUF_SIZE 400010
    #define LL long long
    char obuf[BUF_SIZE], *p3 = obuf;
    inline char gc () { static char buf[BUF_SIZE], *p1 = buf, *p2 = buf; return p1 == p2 && (p2 = (p1 = buf) + fread (buf, 1, BUF_SIZE, stdin), p1 == p2) ? EOF : *p1++; }
    inline void pc (char x) { (p3 - obuf < (1 << 31)) ? (*p3++ = x) : (fwrite (obuf, p3 - obuf, 1, stdout), p3 = obuf, *p3++ = x); }
    inline void read (char &ch) { ch = gc (); }
    inline void read (char s[]) { char ch = gc (); while (ch != ' ' && ch != '\n') *s++ = ch, ch = gc (); }
    inline void read (int &x) { x = 0; bool f = 0; char ch = gc (); while (ch < '0' || ch > '9') f |= ch == '-', ch = gc (); while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + (ch ^ 48), ch = gc (); x = f ? ~x + 1 : x; }
    inline void read (long long &x) { x = 0; bool f = 0; char ch = gc (); while (ch < '0' || ch > '9') f |= ch == '-', ch = gc (); while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + (ch ^ 48), ch = gc (); x = f ? ~x + 1 : x; }
    inline void read (double &x) { x = 0; bool f = 0; char ch = gc (); while (ch < '0' || ch > '9') f |= ch == '-', ch = gc (); while (ch >= '0' && ch <= '9') x = (x * 10) + (ch ^ 48), ch = gc (); if (ch == '.') { double tmp = 1; ch = getchar(); while(ch >= '0' && ch <= '9') tmp /= 10.0, x += tmp * (ch ^ 48), ch = gc (); } x = f ? -x : x; }
    inline void write (char ch) { pc (ch); }
    inline void write (char s[]) { while (*s) pc (*s++); }
    inline void write (int x) { static char c[11]; unsigned p = 0; if (x < 0) pc ('-'), x = ~x + 1; if (!x) { pc ('0'); return ; } while (x) c[++p] = x % 10 ^ 48, x /= 10; while (p) pc (c[p]), --p; }
    inline void write (long long x) { static char c[20]; unsigned p = 0; if (x < 0) pc ('-'), x = ~x + 1; if (!x) { pc ('0'); return ; } while (x) c[++p] = x % 10 ^ 48, x /= 10; while (p) pc (c[p]), --p; }
    inline void write (double x, int y = DECIMAL) { static LL mul[] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000, 10000000000LL, 100000000000LL, 1000000000000LL, 10000000000000LL, 100000000000000LL, 1000000000000000LL, 10000000000000000LL, 100000000000000000LL}; if (x < -1e-12) pc ('-'), x = -x; x *= mul[y]; LL x1 = (LL) floor (x); if (floor (x) >= 0.5) ++x1; LL x2 = x1 / mul[y], x3 = x1 - x2 * mul[y]; write (x2); pc ('.'); for (size_t i = 1; x3 * mul[i] < mul[y]; ++i) pc ('0'); write (x3); }
    template <class T, class... U> inline void read (T &x, U &...t) { read (x), read (t...); }
    template <class T, class... U> inline void write (T x, U ...t) { write (x), write (t...); }
    inline void flush () { fwrite (obuf, p3 - obuf, 1, stdout); }
};

using namespace IO;

int main ()
{
    read (n);
    for (int i = 1; i <= n; ++i) read (a[i]);
    for (int i = 1; i <= n; ++i)
    {
        for (int j = i; j <= n; ++j)
            if (!a[cur = j]) break;
        if (!a[cur])
            for (int j = i; j <= cur; ++j) b[j] = j <= lst + cur >> 1 ? j - lst : cur - j;
        else
        {
            for (int j = i; j <= n; ++j) b[j] = j - lst;
            break;
        }
        lst = cur, i = lst;
    }
    for (int i = 1; i <= n; ++i) write (b[i], ' ');
    flush ();
    return 0;
}

Author: $Segment$_$Tree$



活动打卡代码 AcWing 4419. 上车

Segment_Tree
1个月前
#include <cstdio>

#pragma GCC optimize (2, 3, "Ofast", "-ffast-math")

int main ()
{
    int n, x, y, ans = 0;
    scanf ("%d", &n);
    while (n--) scanf ("%d %d", &x, &y), ans += x + 2 <= y;
    printf ("%d\n", ans);
    return 0;
}