Shawn's Blog

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    string maximumTime(string time) {
        string ans = time;
        if (time[0] == '?') ans[0] = time[1] != '?' && time[1] > '3' ? '1' : '2';
        if (time[1] == '?') ans[1] = ans[0] == '2' ? '3' : '9';
        if (time[3] == '?') ans[3] = '5';
        if (time[4] == '?') ans[4] = '9';
        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 <cstdio>
#include <unordered_map>
using namespace std;
using PII = pair<int, int>;
const int N = 200001;
int k, n, a[N], s;
unordered_map<int, PII> m;
int main() {
    scanf("%d", &k);
    for (int i = 1; i <= k; ++i) {
        scanf("%d", &n);
        s = 0;
        for (int j = 1; j <= n; ++j) {
            scanf("%d", &a[j]);
            s += a[j];
        }
        for (int j = 1; j <= n; ++j) {
            int t = s - a[j];
            if (m.count(t) && m[t].first != i) {
                puts("YES");
                printf("%d %d\n", m[t].first, m[t].second);
                printf("%d %d\n", i, j);
                return 0;
            }
            m[t] = {i, j};
        }
    }
    puts("NO");
    return 0;
}

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
#include <cstdio>
using namespace std;
int t, n;
int main() {
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        printf("%d\n", n - 1);
        for (int i = 1; i <= n - 1;) printf("%d ", ++i);
        puts("");
    }
    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
55
56
57
58
59
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 10010;
int c, n, l, r;
pair<int, int> pos[N];
vector<int> s;
int get(int x) {
    return lower_bound(s.begin(), s.end(), x) - s.begin();
}
struct Node {
    int l, r, lazy;
} t[N << 3];
// segment tree, N << 2;
// 1 <= discretized(l/r) << 10000, (N << 2) << 1.
void build(int u, int l, int r) {
    t[u] = {l, r, 0};
    if (l == r) return;
    int mid = l + r >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
}
bool update(int u, int l, int r) {
    if (t[u].lazy) return false;
    if (t[u].l == t[u].r) return t[u].lazy = true;
    bool res = false;
    int mid = t[u].l + t[u].r >> 1;
    if (l <= mid) res |= update(u << 1, l, r);
    if (r > mid) res |= update(u << 1 | 1, l, r);
    if (t[u << 1].lazy && t[u << 1 | 1].lazy) t[u].lazy = true;
    return res;
}
int main() {
    scanf("%d", &c);
    while (c--) {
        s.clear();
        memset(t, 0, sizeof(t));
        scanf("%d", &n);
        for (int i = 1; i <= n; ++i) {
            scanf("%d%d", &l, &r);
            ++r;
            pos[i] = {l, r};
            s.push_back(l);
            s.push_back(r);
        }
        sort(s.begin(), s.end());
        s.erase(unique(s.begin(), s.end()), s.end());
        int len = s.size();
        build(1, 0, s.size() - 2);
        int ans = 0;
        for (int i = n; i; --i) {
            l = get(pos[i].first), r = get(pos[i].second) - 1;
            if (update(1, l, r)) ++ans;
        }
        printf("%d\n", ans);
    }
    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
55
56
57
58
59
60
#include <cstdio>
using namespace std;
typedef long long LL;
const int N = 100001;
int n, q, l, r, c, a[N << 2];
char ch;
LL d[N << 2], b[N << 2];
void build(int p, int s, int t) {
    if (s == t) {
        d[p] = a[s];
        return;
    }
    int m = s + t >> 1;
    build(p * 2, s, m), build(p * 2 + 1, m + 1, t);
    d[p] = d[p * 2] + d[p * 2 + 1];
}
void update(int p, LL c, int l, int r, int s, int t) {
    if (l <= s && t <= r) {
        d[p] += (t - s + 1) * c, b[p] += c;
        return;
    }
    int m = t + s >> 1;
    if (b[p] && s != t) {
        d[p * 2] += b[p] * (m - s + 1), d[p * 2 + 1] += b[p] * (t - m);
        b[p * 2] += b[p], b[p * 2 + 1] += b[p];
        b[p] = 0;
    }
    if (l <= m) update(p * 2, c, l, r, s, m);
    if (r > m) update(p * 2 + 1, c, l, r, m + 1, t);
    d[p] = d[p * 2] + d[p * 2 + 1];
}
LL getSum(int p, int l, int r, int s, int t) {
    if (l <= s && t <= r) return d[p];
    int m = s + t >> 1;
    if (b[p]) {
        d[p * 2] += b[p] * (m - s + 1), d[p * 2 + 1] += b[p] * (t - m);
        b[p * 2] += b[p], b[p * 2 + 1] += b[p];
        b[p] = 0;
    }
    LL sum = 0;
    if (l <= m) sum = getSum(p * 2, l, r, s, m);
    if (r > m) sum += getSum(p * 2 + 1, l, r, m + 1, t);
    return sum;
}
int main() {
    scanf("%d %d", &n, &q);
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    build(1, 1, n);
    for (int i = 0; i < q; ++i) {
        getchar();
        scanf("%c %d %d", &ch, &l, &r);
        if (ch == 'Q') {
            printf("%lld\n", getSum(1, l, r, 1, n));
        } else {
            scanf("%d", &c);
            update(1, c, l, r, 1, n);
        }
    }
    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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long LL;
const int N = 100001;
int n, q, l, r, c, a[N], L[N], R[N], pos[N];
LL sum[N], add[N];
char ch;
void build() {
    int t = sqrt(n * 1.0);
    int num = n / t;
    if (n % t) ++num;
    for (int i = 1; i <= num; ++i)
        L[i] = (i - 1) * t + 1, R[i] = i * t;
    R[num] = n;
    for (int i = 1; i <= num; ++i)
        for (int j = L[i]; j <= R[i]; ++j)
            pos[j] = i, sum[i] += a[j];
}
void change(int l, int r, int d) {
    int p = pos[l], q = pos[r];
    if (p == q) {
        for (int i = l; i <= r; ++i) a[i] += d;
        sum[p] += d * (r - l + 1);
    } else {
        for (int i = p + 1; i <= q - 1; ++i) add[i] += d;
        for (int i = l; i <= R[p]; ++i) a[i] += d;
        sum[p] += d * (R[p] - l + 1);
        for (int i = L[q]; i <= r; ++i) a[i] += d;
        sum[q] += d * (r - L[q] + 1);
    }
}
LL query(int l, int r) {
    int p = pos[l], q = pos[r];
    LL ans = 0;
    if (p == q) {
        for (int i = l; i <= r; ++i) ans += a[i];
        ans += add[p] * (r - l + 1);
    } else {
        for (int i = p + 1; i <= q - 1; ++i)
            ans += sum[i] + add[i] * (R[i] - L[i] + 1);
        for (int i = l; i <= R[p]; ++i) ans += a[i];
        ans += add[p] * (R[p] -l + 1);
        for (int i = L[q]; i <= r; ++i) ans += a[i];
        ans += add[q] * (r - L[q] + 1);
    }
    return ans;
}
int main() {
    scanf("%d %d", &n, &q);
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    build();
    for (int i = 0; i < q; ++i) {
        getchar();
        scanf("%c %d %d", &ch, &l, &r);
        if (ch == 'Q') {
            printf("%lld\n", query(l, r));
        } else {
            scanf("%d", &c);
            change(l, r, c);
        }
    }
    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
#include <cstdio>

using namespace std;
using LL = long long;
const int N = 2049;
int n, m, a, b, c, d, k;
LL c1[N][N], c2[N][N], c3[N][N], c4[N][N];

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

void add(int x, int y, int k) {
    for (int i = x; i <= n; i += lowbit(i))
        for (int j = y; j <= m; j += lowbit(j)) {
            c1[i][j] += k;
            c2[i][j] += x * k;
            c3[i][j] += y * k;
            c4[i][j] += x * y * k;
        }
}

LL getSum(int x, int y) {
    LL s = 0;
    for (int i = x; i > 0; i -= lowbit(i))
        for (int j = y; j > 0; j -= lowbit(j))
            s += c1[i][j] * (x + 1) * (y + 1) - c2[i][j] * (y + 1) - c3[i][j] * (x + 1) + c4[i][j];
    return s;
}

int main() {
    scanf("%d%d", &n, &m);
    while (scanf("%d", &a) != EOF) {
        if (a == 1) {
            scanf("%d%d%d%d%d", &a, &b, &c, &d, &k);
            add(a, b, k);
            add(a, d + 1, -k);
            add(c + 1, b, -k);
            add(c + 1, d + 1, k);
        } else {
            scanf("%d%d%d%d", &a, &b, &c, &d);
            printf("%lld\n", getSum(c, d) - getSum(a - 1, d) - getSum(c, b - 1) + getSum(a - 1, b - 1));
        }
    }
    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 = 4097;
int n, m, a, b, c, d, k;
LL tree[N][N];

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

void add(int x, int y, int k) {
    for (int i = x; i <= n; i += lowbit(i))
        for (int j = y; j <= m; j += lowbit(j))
            tree[i][j] += k;
}

LL getSum(int x, int y) {
    LL s = 0;
    for (int i = x; i > 0; i -= lowbit(i))
        for (int j = y; j > 0; j -= lowbit(j))
            s += tree[i][j];
    return s;
}

int main() {
    scanf("%d%d", &n, &m);
    while (scanf("%d", &a) != EOF) {
        if (a == 1) {
            scanf("%d%d%d%d%d", &a, &b, &c, &d, &k);
            add(a, b, k);
            add(a, d + 1, -k);
            add(c + 1, b, -k);
            add(c + 1, d + 1, k);
        } else {
            scanf("%d%d", &a, &b);
            printf("%lld\n", getSum(a, b));
        }
    }
    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
#include <cstdio>

using namespace std;
using LL = long long;
const int N = 4097;
int n, m, a, b, c, d;
LL tree[N][N];

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

void add(int x, int y, int k) {
    for (int i = x; i <= n; i += lowbit(i))
        for (int j = y; j <= m; j += lowbit(j))
            tree[i][j] += k;
}

LL getSum(int x, int y) {
    LL s = 0;
    for (int i = x; i > 0; i -= lowbit(i))
        for (int j = y; j > 0; j -= lowbit(j))
            s += tree[i][j];
    return s;
}

int main() {
    scanf("%d%d", &n, &m);
    while (scanf("%d", &a) != EOF) {
        if (a == 1) {
            scanf("%d%d%d", &a, &b, &c);
            add(a, b, c);
        } else {
            scanf("%d%d%d%d", &a, &b, &c, &d);
            printf("%lld\n", getSum(c, d) - getSum(a - 1, d) - getSum(c, b - 1) + getSum(a - 1, b - 1));
        }
    }
    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
#include <cstdio>

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

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

void add(int i, LL k) {
    for (int x = i; i <= n; i += lowbit(i))
        s1[i] += k, s2[i] += k * x;
}

LL getSum(int i) {
    LL s = 0;
    for (int x = i + 1; i > 0; i -= lowbit(i))
        s += s1[i] * x - s2[i];
    return s;
}

int main() {
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &y);
        LL k = y - x;
        s1[i] += k, s2[i] += k * i;
        int j = i + lowbit(i);
        if (j <= n)
            s1[j] += s1[i], s2[j] += s2[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%d", &x, &y);
            printf("%lld\n", getSum(y) - getSum(x - 1));
        }
    }
    return 0;
}
0%