abc 106 D累積和、二次元累積和

C

ドラえもんのバイバインを思い出した。

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int INF = 1e9;
int main() {
    string S;
    ll K;
    cin >> S >> K;
    int x = min((ll)S.size(), K);
    for (int i = 0; i < x; ++i) {
        if (S[i] != '1') {
            cout << S[i] << endl;
            return 0;
        }
    }
    cout << 1 << endl;
    return 0;
}

これ、

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int INF = 1e9;
int main() {
    string S;
    ll s = S.size();
    ll K;
    cin >> S >> K;
    int x = min(s, K);
    for (int i = 0; i < x; ++i) {
        if (S[i] != '1') {
            cout << S[i] << endl;
            return 0;
        }
    }
    cout << 1 << endl;
    return 0;
}

だと間違いらしい。なんでダメなのか俺にはよくわからないから誰か教えてほしい

D

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<cstdio>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const int INF = 1e9 + 7;
int N, M, Q, L[200009], R[200009], X[509][509] , C[509][509] ;
int main() {
    cin >> N >> M >> Q;
    for (int i = 1; i <= M; ++i) {
        cin >> L[i] >> R[i];
        X[L[i]][R[i]]++;
    }
    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= N; ++j) {
            C[i][j] = C[i][j - 1] + X[i][j];
        }
    }
    for (int i = 1; i <= Q; ++i) {
        int p, q; cin >> p >> q;
        int sum = 0;
        for (int j = p; j <= q; ++j) {
            sum += C[j][q] - C[j][p - 1];
        }
        cout << sum << endl;
    }
    return 0;
}

これが普通の累積和。いもす。
二次元累積和は

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<iomanip>
using namespace std;
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const int dx[4] = { 0, -1, 1, 0 };
const int dy[4] = { -1, 0, 0, 1 };
const int INF = 1e9 + 7;
int gcd(int x, int y) {
    if (x < y)swap(x, y);
    if (y == 0)return x;
    return gcd(y, x%y);
}

template<class T1, class T2> void chmin(T1 &a, T2 b) { if (a>b)a = b; }

template<class T1, class T2> void chmax(T1 &a, T2 b) { if (a<b)a = b; }
template<class T>
void Add(T &a, const T &b, const T &mod = 1000000007) {
    int val = ((a % mod) + (b % mod)) % mod;
    if (val < 0) { val += mod; }
    a = val;
}
////////////////////////////////////////

int main() {
    int N, M, Q;
    cin >> N >> M >> Q;
    int l, r;
    //区間[l,r]を走る列車について考える。これを二次元平面上の(y座標,x座標)=(l,r)
    //の点とみなすとこの列車を完全に含むような区間はy<=lかつr<=xの範囲全てになる
    int imos[550][550];//imos[y][x]でyからxまでの区間に含まれる列車の本数
    for (int i = 0; i < 550; ++i) {
        for (int j = 0; j < 550; ++j) {
            imos[i][j] = 0;
        }
    }
    for (int i = 0; i < M; ++i) {
        cin >> l >> r;
        imos[l][r]++;
    }
    for (int i = 510; i >0; --i) {
        for (int j = 0; j <510; ++j) {
            imos[i - 1][j] += imos[i][j];
        }
    }
    for (int i = 0; i < 510; ++i) {
        for (int j = 0; j < 510; ++j) {
            imos[i][j + 1] += imos[i][j];
        }
    }
    for (int i = 0; i < Q; ++i) {
        cin >> l >> r;
        cout << imos[l][r] << endl;
    }
    return 0;
}