Atcoder357

A - Sanitize Hands

code

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define int long long
const int N = 1e6 + 10;
typedef pair<int, int> pii;

int n, m;

void solve()
{
    cin >> n >> m;
    int sum = 0, cnt = 0;
    for (int i = 1; i <= n; i ++ ) {
        int x;
        cin >> x;
        sum += x;
        if (sum > m) {
            break;
        } 
        cnt ++;
    }   
    cout << cnt << '\n';
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int _ = 1;
    // cin >> _;
    while (_ -- )
    {
        solve();
    }
    return 0;
}

B - Uppercase and Lowercase

code

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define int long long
const int N = 1e6 + 10;
typedef pair<int, int> pii;

void solve()
{
    string s;
    int cnt1 = 0, cnt2 = 0;
    cin >> s;
    for (int i = 0; i < s.length(); i ++ ) {
        if (s[i] >= 'a' && s[i] <= 'z') cnt1 ++;
        else cnt2 ++;
    }   
    if (cnt1 > cnt2) {
        for (int i = 0; i < s.length(); i ++ ) {
            if (s[i] >= 'A' && s[i] <= 'Z') {
                s[i] += 32;
            }
        }
    } else {
        for (int i = 0; i < s.length(); i ++ ) {
            if (s[i] >= 'a' && s[i] <= 'z') {
                s[i] -= 32;
            }
        }
    }
    cout << s << '\n';
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int _ = 1;
    // cin >> _;
    while (_ -- )
    {
        solve();
    }
    return 0;
}

C - Sierpinski carpet

code

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define int long long
const int N = 1010;
typedef pair<int, int> pii;

char g[N][N];
int n;

void draw(int u, int x, int y) {
    if (! u) {
        return ;
    }
    for (int i = x + pow(3, u - 1); i < x + 2 * pow(3, u - 1); i ++ ) {
        for (int j = y + pow(3, u - 1); j < y + 2 * pow(3, u - 1); j ++ ) {
            g[i][j] = '.';
        }
    }
    draw(u - 1, x, y);
    draw(u - 1, x + pow(3, u - 1), y);
    draw(u - 1, x + 2 * pow(3, u - 1), y);
    draw(u - 1, x, y + pow(3, u - 1));
    draw(u - 1, x + pow(3, u - 1), y + pow(3, u - 1));
    draw(u - 1, x + 2 * pow(3, u - 1), y + pow(3, u - 1));
    draw(u - 1, x, y + 2 * pow(3, u - 1));
    draw(u - 1, x + pow(3, u - 1), y + 2 * pow(3, u - 1));
    draw(u - 1, x + 2 * pow(3, u - 1), y + 2 * pow(3, u - 1));
}
void solve()
{
    cin >> n;
    for (int i = 1; i < 1 + pow(3, n); i ++ ) {
        for (int j = 1; j < 1 + pow(3, n); j ++ ) {
            g[i][j] = '#';
        }
    }
    draw(n, 1, 1);
    for (int i = 1; i < 1 + pow(3, n); i ++ ) {
        for (int j = 1; j < 1 + pow(3, n); j ++ ) {
            cout << g[i][j];
        }
        cout << '\n';
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int _ = 1;
    // cin >> _;
    while (_ -- )
    {
        solve();
    }
    return 0;
}

D - 88888888

code

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define int long long
const int N = 1e6 + 10;
const int mod = 998244353;
typedef pair<int, int> pii;

int n, m;

int qmi(int a, int k, int p) {
    int res = 1;
    while (k) {
        if (k & 1) res = res * a % p;
        k >>= 1; 
        a = a * a % p;
    }
    return res;
}

void solve()
{
    cin >> n;
    int temp = n, k = 1;
    while (temp) {
        temp /= 10;
        k = k * 10 % mod;
        m ++;
    }
    int ans = n % mod * (qmi(k, n, mod) - 1 + mod) % mod;
    ans = ans * qmi((k - 1 + mod), mod - 2, mod) % mod;
    cout << ans << '\n';
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int _ = 1;
    // cin >> _;
    while (_ -- )
    {
        solve();
    }
    return 0;
}

E - Reachability in Functional Graph

code

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define int long long
const int N = 1e6 + 10;
typedef pair<int, int> pii;

int n, nex[N], ans[N], vis[N], tim, pre, res;

int dfs(int u) {
    vis[u] = ++ tim;
    int son = nex[u];
    if (ans[son]) {
        ans[u] = ans[son] + 1;
        return ans[u];
    }

    if (vis[son]) {
        ans[u] = vis[u] - vis[son] + 1;
        pre = vis[son];
        // cout << u << ' ' << son << '\n';
        return ans[u];
    }

    int huan = dfs(son);

    if (vis[u] >= pre) ans[u] = huan;
    else ans[u] = huan + 1;
    return ans[u];
}

void solve()
{
    cin >> n;
    for (int i = 1; i <= n; i ++ ) {
        cin >> nex[i];
    }

    for (int i = 1; i <= n; i ++ ) {
        if (! vis[i]) {
            pre = 1e9;
            dfs(i);
        }
    }   

    for (int i = 1; i <= n; i ++ ) {
        res += ans[i];
    }
    cout << res << '\n';
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int _ = 1;
    // cin >> _;
    while (_ -- )
    {
        solve();
    }
    return 0;
}

F - Two Sequence Queries

code

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define int long long
const int N = 2e5 + 10;
const int mod = 998244353;
typedef pair<int, int> pii;

int n, q, a[N], b[N];

struct Node {
    int l, r, suma, sumb, sum;
    int tag1, tag2;
}tr[N * 4];

void pushup(Node &root, Node &l, Node &r) {
    root.suma = (l.suma + r.suma) % mod;
    root.sumb = (l.sumb + r.sumb) % mod;
    root.sum = (l.sum + r.sum) % mod;
}

void pushup(int u) {
    pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
}

void pushdown(int u) {
    if (tr[u].tag1) { // (a[l] - a[r]) + x;
        tr[u << 1].tag1 = (tr[u << 1].tag1 + tr[u].tag1) % mod, tr[u << 1 | 1].tag1 = (tr[u << 1 | 1].tag1 + tr[u].tag1) % mod;
        tr[u << 1].suma = ((tr[u << 1].r - tr[u << 1].l + 1) * tr[u].tag1 % mod + tr[u << 1].suma ) % mod;
        tr[u << 1 | 1].suma = ((tr[u << 1 | 1].r - tr[u << 1 | 1].l + 1) * tr[u].tag1 % mod + tr[u << 1 | 1].suma) % mod;
        tr[u << 1].sum = (tr[u << 1].sumb * tr[u].tag1 % mod + tr[u << 1].sum) % mod;
        tr[u << 1 | 1].sum = (tr[u << 1 | 1].sumb * tr[u].tag1 % mod + tr[u << 1 | 1].sum) % mod;
        tr[u].tag1 = 0;
    }
    if (tr[u].tag2) {  // (b[l] - b[r]) + x
        tr[u << 1].tag2 = (tr[u << 1].tag2 + tr[u].tag2) % mod, tr[u << 1 | 1].tag2 = (tr[u << 1 | 1].tag2 + tr[u].tag2) % mod;
        tr[u << 1].sumb = ((tr[u << 1].r - tr[u << 1].l + 1) * tr[u].tag2 % mod + tr[u << 1].sumb ) % mod;
        tr[u << 1 | 1].sumb = ((tr[u << 1 | 1].r - tr[u << 1 | 1].l + 1) * tr[u].tag2 % mod + tr[u << 1 | 1].sumb) % mod;
        tr[u << 1].sum = (tr[u << 1].suma * tr[u].tag2 % mod + tr[u << 1].sum) % mod;
        tr[u << 1 | 1].sum = (tr[u << 1 | 1].suma * tr[u].tag2 % mod + tr[u << 1 | 1].sum) % mod;
        tr[u].tag2 = 0;
    }
}

void build(int u, int l, int r) {
    if (l == r) {
        tr[u] = {l, r, a[l] % mod, b[l] % mod, a[l] * b[l] % mod, 0, 0};
        return ;
    } else {
        tr[u] = {l, r, 0, 0, 0, 0, 0};
        int mid = l + r >> 1;
        build (u << 1, l, mid), build (u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}

void modifya(int u, int l, int r, int v) {
    if (tr[u].l >= l && tr[u].r <= r) {
        tr[u].tag1 = (tr[u].tag1 + v) % mod;
        tr[u].suma = ((tr[u].r - tr[u].l + 1) * v % mod + tr[u].suma) % mod;
        tr[u].sum = (tr[u].sumb * v % mod + tr[u].sum) % mod;
        return ;
    } else {
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        if (l <= mid) modifya(u << 1, l, r, v);
        if (r > mid) modifya(u << 1 | 1, l, r, v);
        pushup(u);
    }
}

void modifyb(int u, int l, int r, int v) {
    if (tr[u].l >= l && tr[u].r <= r) {
        tr[u].tag2 = (tr[u].tag2 + v) % mod;
        tr[u].sumb = ((tr[u].r - tr[u].l + 1) * v % mod + tr[u].sumb) % mod;
        tr[u].sum = (tr[u].suma * v % mod + tr[u].sum) % mod;
        return ;
    } else {
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        if (l <= mid) modifyb(u << 1, l, r, v);
        if (r > mid) modifyb(u << 1 | 1, l, r, v);
        pushup(u);
    }
}

Node query(int u, int l, int r) {
    if (tr[u].l >= l && tr[u].r <= r) {
        return tr[u];
    } else {
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        if (r <= mid) return query(u << 1, l, r);
        else if (l > mid) return query(u << 1 | 1, l, r);
        else {
            Node res;
            auto left = query(u << 1, l, mid);
            auto right = query(u << 1 | 1, mid + 1, r);
            pushup(res, left, right);
            return res;
        }
    }
}

void solve()
{
    cin >> n >> q;
    for (int i = 1; i <= n; i ++ ) cin >> a[i];
    for (int i = 1; i <= n; i ++ ) cin >> b[i];
    build(1, 1, n);
    while (q -- ) {
        int op, l, r, x;
        cin >> op >> l >> r;
        if (op == 3) {
            auto res = query(1, l, r);
            cout << res.sum % mod << '\n';
        } else {
            cin >> x;
            if (op == 1) {
                modifya(1, l, r, x);
            } else {
                modifyb(1, l, r, x);
            }
        }
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int _ = 1;
    // cin >> _;
    while (_ -- )
    {
        solve();
    }
    return 0;
}