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;
}