Shawn's Blog

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <cstdio>

using namespace std;
using LL = long long;
const int N = 1000001;
int n, q, x, y, z;
LL c[N];

int lowbit(int x) {
    return x & -x;
}

void add(int i, int k) {
    for (; i <= n; i += lowbit(i))
        c[i] += k;
}

LL getSum(int i) {
    LL s = 0;
    for (; i > 0; i -= lowbit(i))
        s += c[i];
    return s;
}

int main() {
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &y);
        c[i] += y - x;
        int j = i + lowbit(i);
        if (j <= n)
            c[j] += c[i];
        x = y;
    }
    for (int i = 0; i < q; ++i) {
        scanf("%d", &x);
        if (x == 1) {
            scanf("%d%d%d", &x, &y, &z);
            add(x, z);
            add(y + 1, -z);
        } else {
            scanf("%d", &x);
            printf("%lld\n", getSum(x));
        }
    }
    return 0;
}

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <cstdio>

using namespace std;
using LL = long long;
const int N = 1000001;
int n, q, x, y, z;
LL c[N];

int lowbit(int x) {
    return x & -x;
}

void add(int i, int k) {
    for (; i <= n; i += lowbit(i))
        c[i] += k;
}

LL getSum(int i) {
    LL s = 0;
    for (; i > 0; i -= lowbit(i))
        s += c[i];
    return s;
}

int main() {
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &x);
        c[i] += x;
        int j = i + lowbit(i);
        if (j <= n)
            c[j] += c[i];
    }
    for (int i = 0; i < q; ++i) {
        scanf("%d%d%d", &x, &y, &z);
        if (x == 1)
            add(y, z);
        else
            printf("%lld\n", getSum(z) - getSum(y - 1));
    }
    return 0;
}

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> m;
        for (string &s : strs) {
            string key = s;
            sort(key.begin(), key.end());
            m[key].emplace_back(s);
        }
        vector<vector<string>> ans(m.size());
        int i = 0;
        for (auto [_, s] : m)
            ans[i++] = move(s);
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> m;
        for (string &s : strs) {
            m[strSort(s)].emplace_back(s);
        }
        vector<vector<string>> ans(m.size());
        int i = 0;
        for (auto [_, s] : m)
            ans[i++] = move(s);
        return ans;
    }
    string strSort(string &s) {
        int cnt[26] = {0};
        for (auto &c : s)
            ++cnt[c - 'a'];
        string ans;
        for (int i = 0; i < 26; i++)
            ans += string(cnt[i], i + 'a');
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> m;
        for (string &s : strs) {
            m[strCnt(s)].emplace_back(s);
        }
        vector<vector<string>> ans(m.size());
        int i = 0;
        for (auto [_, s] : m)
            ans[i++] = move(s);
        return ans;
    }
    string strCnt(string &s) {
        int cnt[26] = {0};
        for (auto &c : s)
            ++cnt[c - 'a'];
        string ans;
        for (int i = 0; i < 26; i++)
            ans += (i + 'a') + cnt[i];
        return ans;
    }
};

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>

using namespace std;

int main() {
    int n, v, s, k;
    long ans = 0, sum = 0;
    cin >> n;
    vector<pair<int, int>> solders(n);
    for (int i = 0; i < n; i++) {
        cin >> v >> s;
        solders[i] = {s, v};
    }
    sort(solders.begin(), solders.end());
    priority_queue<int, vector<int>, greater<int>> q;
    for (int i = n - 1; i >= 0; --i) {
        auto[s, v] = solders[i];
        q.push(v);
        sum += v;
        k = s;
        while (q.size() > k) {
            sum -= q.top();
            q.pop();
        }
        ans = max(ans, sum);
    }
    cout << ans << endl;
    return 0;
}

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <bits/stdc++.h>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<vector<vector<bool>>> jellies(n, vector<vector<bool>>(n, vector<bool>(n, false)));
    string s;
    for (int z = 0; z < n; z++)
        for (int x = 0; x < n; x++) {
            cin >> s;
            for (int y = 0; y < n; y++)
                if (s[y] == '.') jellies[z][x][y] = true;
        }
    int ds[] = {0, 0, 1, 0, 0, -1, 0, 0}, steps = 1;
    queue<tuple<int, int, int>> q;
    q.emplace(0, 0, 0);
    jellies[0][0][0] = false;
    while (!q.empty()) {
        int size = q.size();
        while (size--) {
            auto[z, x, y] = q.front();
            q.pop();
            if (z == n - 1 && x == n - 1 && y == n - 1) {
                cout << steps << endl;
                return 0;
            }
            for (int i = 0; i < 6; ++i) {
                int nz = z + ds[i], nx = x + ds[i + 1], ny = y + ds[i + 2];
                if (nz < 0 || nz > n - 1 || nx < 0 || nx > n - 1 || ny < 0 || ny > n - 1
                    || !jellies[nz][nx][ny])
                    continue;
                jellies[nz][nx][ny] = false;
                q.emplace(nz, nx, ny);
            }
        }
        ++steps;
    }
    cout << -1 << endl;
    return 0;
}

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
const int N = 30001;
int tree[N << 2];
class NumArray {
private:
    vector<int> nums;
    int n;
    void build(int p, int l, int r) {
        if (l == r) {
            tree[p] = nums[l - 1];
            return;
        }
        int m = l + r >> 1;
        build(p * 2, l, m), build(p * 2 + 1, m + 1, r);
        tree[p] = tree[p * 2] + tree[p * 2 + 1];
    }
    int query(int p, int l, int r, int i, int j) {
        if (i <= l && r <= j) return tree[p];
        int m = l + r >> 1, s = 0;
        if (i <= m) s += query(p * 2, l, m, i, j);
        if (j > m) s += query(p * 2 + 1, m + 1, r, i, j);
        return s;
    }
    void update(int p, int l, int r, int i, int v) {
        if (l == r) {
            tree[p] = v;
            return;
        }
        int m = l + r >> 1;
        if (i <= m) update(p * 2, l, m, i, v);
        else update(p * 2 + 1, m + 1, r, i, v);
        tree[p] = tree[p * 2] + tree[p * 2 + 1];
    }
public:
    NumArray(vector<int>& nums) {
        this->nums = nums;
        this->n = nums.size();
        memset(tree, 0, (n + 1) * 8);
        build(1, 1, n);
    }
    
    void update(int index, int val) {
        update(1, 1, n, index + 1, val);
    }
    
    int sumRange(int left, int right) {
        return query(1, 1, n, left + 1, right + 1);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
const int N = 30001;
int c[N];
class NumArray {
private:
    vector<int> nums;
    int n;
    void build() {
        for (int i = 0; i < n; ++i) {
            // add(i + 1, nums[i]);
            c[i + 1] += nums[i];
            int j = i + lowbit(i);
            if (j <= n)
                c[j] += c[i];
        }
    }
    int lowbit(int x) {
        return x & -x;
    }
    void add(int i, int k) {
        while (i <= n) {
            c[i] += k;
            i += lowbit(i);
        }
    }
    int query(int i) {
        int s = 0;
        while (i > 0) {
            s += c[i];
            i -= lowbit(i);
        }
        return s;
    }
public:
    NumArray(vector<int>& nums) {
        this->nums = nums;
        this->n = nums.size();
        memset(c, 0, (n + 1) * 4);
        build();
    }
    
    void update(int index, int val) {
        add(index + 1, val - nums[index]);
        nums[index] = val;
    }
    
    int sumRange(int left, int right) {
        return query(right + 1) - query(left);
    }
};

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int s = 0, mins = 0, ans = INT_MIN;
        for (int num : nums) {
            s += num;
            ans = max(ans, s - mins);
            mins = min(mins, s);
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size(), ans;
        vector<int> dp(n);
        ans = dp[0] = nums[0];
        for (int i = 1; i < n; ++i) {
            dp[i] = max(nums[i], dp[i - 1] + nums[i]);
            ans = max(ans, dp[i]);
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size(), maxPrevSum = 0, ans = INT_MIN;
        for (int num : nums) {
            maxPrevSum = max(num, maxPrevSum + num);
            ans = max(ans, maxPrevSum);
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    struct Status {
        int lSum, rSum, mSum, iSum;
    };

    Status pushUp(Status l, Status r) {
        int iSum = l.iSum + r.iSum;
        int lSum = max(l.lSum, l.iSum + r.lSum);
        int rSum = max(r.rSum, r.iSum + l.rSum);
        int mSum = max({l.mSum, r.mSum, l.rSum + r.lSum});
        return (Status) {lSum, rSum, mSum, iSum};
    };

    Status get(vector<int> &a, int l, int r) {
        if (l == r) {
            return (Status) {a[l], a[l], a[l], a[l]};
        }
        int m = l + r >> 1;
        Status lSub = get(a, l, m);
        Status rSub = get(a, m + 1, r);
        return pushUp(lSub, rSub);
    }

    int maxSubArray(vector<int>& nums) {
        return get(nums, 0, nums.size() - 1).mSum;
    }
};

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <cstdio>

using namespace std;
const int N = 500001;
int n, m, x, y, k, a[N], c[N];

int lowbit(int x) {
    return x & (-x);
}

void update(int i, int k) {
    while (i <= n) {
        c[i] += k;
        i += lowbit(i);
    }
}

int sum(int i) {
    int s = 0;
    while (i > 0) {
        s += c[i];
        i -= lowbit(i);
    }
    return s;
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
        update(i, a[i] - a[i - 1]);
    }
    for (int i = 0; i < m; ++i) {
        scanf("%d", &x);
        if (x == 1) {
            scanf("%d%d%d", &x, &y, &k);
            update(x, k);
            update(y + 1, -k);
        } else {
            scanf("%d", &x);
            printf("%d\n", sum(x));
        }
    }
    return 0;
}

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <cstdio>
#include <cstring>

using namespace std;
const int N = 50001;
int T, n, x, y, a[N], c[N];
char s[5];

int lowbit(int x) {
    return x & (-x);
}

void update(int i, int k) {
    while (i <= n) {
        c[i] += k;
        i += lowbit(i);
    }
}

int sum(int i) {
    int s = 0;
    while (i > 0) {
        s += c[i];
        i -= lowbit(i);
    }
    return s;
}

int main() {
    scanf("%d", &T);
    for (int t = 1; t <= T; ++t) {
        scanf("%d", &n);
        memset(a, 0, (n + 1) * 4);
        memset(c, 0, (n + 1) * 4);
        for (int i = 1; i <= n; ++i) {
            scanf("%d", &a[i]);
            update(i, a[i]);
        }
        printf("Case %d:\n", t);
        while (true) {
            scanf("%s", s);
            if (s[0] == 'E') break;
            scanf("%d%d", &x, &y);
            if (s[0] == 'Q') {
                printf("%d\n", sum(y) - sum(x - 1));
            } else if (s[0] == 'A') {
                update(x, y);
            } else {
                update(x, -y);
            }
        }
    }
    return 0;
}

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;
const int N = 15000;
int ans[N];
int n, x, y;

int main() {
    scanf("%d", &n);
    vector<int> xs;
    for (int i = 0; i < n; ++i) {
        scanf("%d%d", &x, &y);
        vector<int>::iterator it = upper_bound(xs.begin(), xs.end(), x);
        int idx = it - xs.begin();
        ++ans[idx];
        xs.insert(it, x);
    }
    for (int i = 0; i < n; ++i)
        printf("%d\n", ans[i]);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <cstdio>

using namespace std;
const int N = 15000, X = 32002;
int ans[N], tree[X << 2];
int n, x, y;

void update(int p, int l, int r, int x) {
    if (l == r) {
        ++tree[p];
        return;
    }
    int mid = l + r >> 1;
    if (x <= mid) update(p * 2, l, mid, x);
    else update(p * 2 + 1, mid + 1, r, x);
    tree[p] = tree[p * 2] + tree[p * 2 + 1];
}

int query(int p, int l, int r, int i, int j) {
    if (i <= l && r <= j) return tree[p];
    int mid = l + r >> 1, sum = 0;
    if (i <= mid) sum += query(p * 2, l, mid, i, j);
    if (j > mid) sum += query(p * 2 + 1, mid + 1, r, i, j);
    return sum;
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%d%d", &x, &y);
        ++x;
        ++ans[query(1, 1, X - 1, 1, x)];
        update(1, 1, X - 1, x);
    }
    for (int i = 0; i < n; ++i)
        printf("%d\n", ans[i]);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <cstdio>

using namespace std;
const int N = 15000, X = 32002;
int c[X], ans[N];
int n, x, y;

int lowbit(int x) {
    return x & -x;
}

int add(int i, int k) {
    while (i <= X) {
        c[i] += k;
        i += lowbit(i);
    }
}

int query(int i) {
    int s = 0;
    while (i > 0) {
        s += c[i];
        i -= lowbit(i);
    }
    return s;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d%d", &x, &y);
        ++x;
        add(x, 1);
        ++ans[query(x) - 1];
    }
    for (int i = 0; i < n; ++i)
        printf("%d\n", ans[i]);
    return 0;
}
0%