結果
| 問題 | No.789 範囲の合計 |
| ユーザー |
 mizuho0613
|
| 提出日時 | 2024-09-29 20:30:32 |
| 言語 | C++23(gcc13) (gcc 13.2.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 82 ms / 1,000 ms |
| コード長 | 36,276 bytes |
| コンパイル時間 | 9,179 ms |
| コンパイル使用メモリ | 361,404 KB |
| 実行使用メモリ | 6,824 KB |
| 最終ジャッジ日時 | 2024-09-29 20:30:49 |
| 合計ジャッジ時間 | 10,710 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge3 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
6,820 KB |
| testcase_01 | AC | 2 ms
6,816 KB |
| testcase_02 | AC | 80 ms
6,816 KB |
| testcase_03 | AC | 61 ms
6,820 KB |
| testcase_04 | AC | 81 ms
6,820 KB |
| testcase_05 | AC | 67 ms
6,816 KB |
| testcase_06 | AC | 71 ms
6,820 KB |
| testcase_07 | AC | 51 ms
6,824 KB |
| testcase_08 | AC | 69 ms
6,820 KB |
| testcase_09 | AC | 64 ms
6,820 KB |
| testcase_10 | AC | 82 ms
6,816 KB |
| testcase_11 | AC | 61 ms
6,816 KB |
| testcase_12 | AC | 57 ms
6,816 KB |
| testcase_13 | AC | 1 ms
6,816 KB |
| testcase_14 | AC | 1 ms
6,820 KB |
ソースコード
#include<bits/stdc++.h>
#include<atcoder/all>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define rep(i,n) for(ll i = 0LL; i < (ll)n; ++i)
#define rep1(i,n) for(ll i = 1LL; i <= (ll)n; ++i)
#define rep2(i,m,n) for(ll i = (ll)m; i < (ll)n; ++i)
#define rrep(i,n) for(ll i = (ll)n - 1; i >= 0LL; --i)
#define rrep1(i,n) for(ll i = (ll)n; i > 0LL; --i)
#define rrep2(i,m,n) for(ll i = (ll)m; i > (ll)n; --i)
#define lb(a,x) static_cast<ll>(lower_bound(all(a), x) - a.begin())
#define ub(a,x) static_cast<ll>(upper_bound(all(a), x) - a.begin())
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define SORT(a) sort(all(a));
#define RSORT(a) sort(rall(a));
#define REV(a) reverse(all(a));
#define CEIL(x,y) (x + y - 1) / y
#define pb push_back
#define eb emplace_back
#define _GLIBCXX_DEBUG
#define _CRT_SECURE_NO_WARNINGS
#define INT(...) int __VA_ARGS__;in(__VA_ARGS__)
#define LL(...) ll __VA_ARGS__;in(__VA_ARGS__)
#define STR(...) string __VA_ARGS__;in(__VA_ARGS__)
#define CHR(...) char __VA_ARGS__;in(__VA_ARGS__)
#define DBL(...) double __VA_ARGS__;in(__VA_ARGS__)
#define LD(...) ld __VA_ARGS__;in(__VA_ARGS__)
using namespace std;
using namespace chrono;
using ld = long double;
using ll = long long;
using ull = unsigned long long;
using vi = vector<int>;
using vl = vector<ll>;
using vc = vector<char>;
using vb = vector<bool>;
using vs = vector<string>;
using vvi = vector<vi>;
using vvl = vector<vl>;
using vvc = vector<vc>;
using vvb = vector<vb>;
using vvs = vector<vs>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using si = set<int>;
using sl = set<ll>;
using mii = map<int, int>;
using mll = map<ll, ll>;
//in
void in(){}
template<class T>void in(vector<T> &v){
for(T &t : v)cin >> t;
}
template<class T>void in(vector<vector<T>> &v){
for(auto &row : v)for(T&element : row)cin >> element;
}
template<class Head, class... Tail>void in(Head &head, Tail &...tail){
cin >> head; in(tail...);
}
//out
void out(){}
template<class T>void out(const T &t){
cout << t << endl;
}
template<class T>void out(vector<T> &v){
for(T &t : v)cout << t << ' ';
cout << endl;
}
template<class T>void out(vector<vector<T>> &v){
for(vector<T> &row : v){
for(T &element : row){
cout << element << ' ';
}
cout << endl;
}
}
template<class Head, class...Tail>void out(const Head &head, const Tail &...tail){
cout << head; out(tail...);
}
//chmax
template<typename T>bool chmax(T &a, T b){
return((a < b)? (a = b, true) : (false));
}
//chmin
template<typename T>bool chmin(T &a, T b){
return((a > b)? (a = b, true) : (false));
}
//min
template<typename T>T MIN(vector<T> &v){
T mn = numeric_limits<T>::max();
for(T &e : v){
mn = min(mn, e);
}
return mn;
}
//max
template<typename T>T MAX(vector<T> &v){
T mx = numeric_limits<T>::min();
for(T &e : v){
mx = max(mx, e);
}
return mx;
}
//sum
template<typename T>T SUM(vector<T> &v){
T sum = 0;
for(T &e : v){
sum += e;
}
return sum;
}
//l_sort
template<typename T>void l_sort(vector<T> &l, vector<T> &r){
assert(l.size() == r.size());
long long n = l.size();
vector<pair<T, T>> p;
for(ll i = 0; i < n; i++){
p.emplace_back(l[i], r[i]);
}
sort(p.begin(), p.end());
for(ll i = 0; i < n; i++){
l[i] = p[i].first;
r[i] = p[i].second;
}
}
//r_sort
template<typename T>void r_sort(vector<T> &l, vector<T> &r){
assert(l.size() == r.size());
long long n = l.size();
vector<pair<T, T>> p;
for(ll i = 0; i < n; i++){
p.emplace_back(r[i], l[i]);
}
sort(p.begin(), p.end());
for(ll i = 0; i < n; i++){
l[i] = p[i].second;
r[i] = p[i].first;
}
}
//-----------------------array-----------------------//
//cumulative_sum
template<typename T> vector<T> cumulative_sum(vector<T> &v){
ll n = v.size();
vector<T> res(n + 1);
for(ll i = 0; i < n; ++i){
res[i + 1] = res[i] + v[i];
}
return res;
}
//LCS
ll LCS(string s, string t){
vector dp(s.size() + 1,vector<ll>(t.size() + 1));
rep(i,s.size()){
rep(j,t.size()){
if(s[i] == t[j]){
dp[i + 1][j + 1] = max({dp[i][j + 1], dp[i + 1][j], dp[i][j] + 1});
}else{
dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j]);
}
}
}
return dp[s.size()][t.size()];
}
//LIS
template<typename T>ll LIS(vector<T> &a){
vector<T> dp;
for (T &e : a){
auto it = lower_bound(dp.begin(), dp.end(), e);
if (it == dp.end()){
dp.push_back(e);
}else{
*it = e;
}
}
return (ll)dp.size();
}
template< typename T > struct Compress {
vector<T> xs;
Compress() = default;
Compress(const vector< T > &vs) {
add(vs);
}
Compress(const initializer_list< vector< T > > &vs) {
for(auto &p : vs) add(p);
}
void add(const vector< T > &vs) {
copy(begin(vs), end(vs), back_inserter(xs));
}
void add(const T &x) {
xs.emplace_back(x);
}
void build() {
sort(begin(xs), end(xs));
xs.erase(unique(begin(xs), end(xs)), end(xs));
}
vector< ll > get(const vector< T > &vs) const {
vector<ll> ret;
transform(begin(vs), end(vs), back_inserter(ret), [&](const T &x) {
return lower_bound(begin(xs), end(xs), x) - begin(xs);
});
return ret;
}
ll get(const T &x) const {
return lower_bound(begin(xs), end(xs), x) - begin(xs);
}
const T &operator[](ll k) const {
return xs[k];
}
};
//編集距離
ll edit_distance(string &s, string &t){
ll n = s.size(), m = t.size();
vector dp(n + 1, vector<ll>(m + 1));
for(ll i = 1; i <= n; i++)dp[i][0] = i;
for(ll j = 1; j <= m; j++)dp[0][j] = j;
for(ll i = 1; i <= n; i++)for(ll j = 1; j <= m; j++){
dp[i][j] = min({dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + (s[i - 1] == t[j - 1]? 0 : 1)});
}
return dp[n][m];
}
//エラトステネスの篩
vector<bool> sieve(ll N) {
vector<bool> isprime(N+1, true);
isprime[0] = false;
isprime[1] = false;
for (ll p = 2; p <= N; ++p){
if (!isprime[p]) continue;
for (ll q = p * 2; q <= N; q += p){
isprime[q] = false;
}
}
return isprime;
}
//--------------------data_structure-----------------//
//suffix_array
struct suffix_array{
vector<ll> sa, rank, tmp;
ll n;
string base;
//suffix_arrayを構築
suffix_array(const string s){
n = s.size();
base = s;
sa.resize(n);
rank.resize(n);
tmp.resize(n);
for(ll i = 0; i < n; i++){
sa[i] = i;
rank[i] = s[i];
}
for(ll k = 1; k < n; k *= 2){
auto compare_sa = [&](ll i, ll j){
if(rank[i] != rank[j])return rank[i] < rank[j];
ll ri = (i + k < n) ? rank[i + k] : -1;
ll rj = (j + k < n) ? rank[j + k] : -1;
return ri < rj;
};
sort(sa.begin(), sa.end(), compare_sa);
tmp[sa[0]] = 0;
for(ll i = 1; i < n; i++){
tmp[sa[i]] = tmp[sa[i - 1]] + (compare_sa(sa[i - 1], sa[i])? 1 : 0);
}
rank = tmp;
}
}
//部分文字列の個数を求める
ll counts(string t){
string u = t + "彁";
ll num1, num2;
{
ll m = t.size();
ll ng = -1, ok = n;
while(ok - ng > 1){
ll mid = (ng + ok) / 2;
ll l = sa[mid];
if(base.substr(l, m) >= t){
ok = mid;
}else{
ng = mid;
}
}
num1 = ok;
}
{
ll m = u.size();
ll ng = -1, ok = n;
while(ok - ng > 1){
ll mid = (ng + ok) / 2;
ll l = sa[mid];
if(base.substr(l, m) >= u){
ok = mid;
}else{
ng = mid;
}
}
num2 = ok;
}
return num2 - num1;
}
};
//-----------------------check-----------------------//
//is_prime
template<typename T> bool is_prime(T n){
if(n <= 1)return false;
T m = sqrt(n);
for(ll i = 2; i <= m; ++i){
if(n % i == 0)return false;
}
return true;
}
//is_square
template<typename T> bool is_square(T n){
if(n < 0)return false;
T m = sqrt(n);
if(n == m * m){
return true;
}else{
return false;
}
}
//is_substring
bool is_substring(const string& s, const string& t){
const ll n = s.size(), m = t.size();
for(ll i = 0; i + m <= n; ++i){
if(s.substr(i, m) == t)return true;
}
return false;
}
//-----------------------math------------------------//
//gcd(faster)
ll GCD(ll A, ll B){
if(B == 0){
return A;
}else{
return GCD(B, A % B);
}
}
//lcm(faster)
ll LCM(ll A, ll B){
return A / GCD(A, B) * B;
}
//comb
ll comb(ll n, ll r){
assert(n >= 2);
vector dp(n + 1, vector<ll>(r + 1));
for(ll i = 0; i < n + 1; ++i){
dp[i][0] = 1;
}
for(ll i = 0; i < r + 1; ++i){
dp[i][i] = 1;
}
for(ll i = 1; i < n + 1; ++i){
for(ll j = 1; j < min(i, r + 1); ++j){
dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
}
}
return dp[n][r];
}
// comb_mod
using mint_comb = atcoder::static_modint<1000000007>;
vector<mint_comb> fac, finv, inv;
// テーブルを作る前処理
void init_comb_mod(ll size) {
size += 109;
fac.resize(size);
finv.resize(size);
inv.resize(size);
const ll MOD = mint_comb::mod();
fac[0] = fac[1] = 1;
finv[0] = finv[1] = 1;
inv[1] = 1;
for (ll i = 2; i < size; i++){
fac[i] = fac[i - 1] * i;
inv[i] = MOD - inv[MOD%i] * (MOD / i);
finv[i] = finv[i - 1] * inv[i];
}
}
// 二項係数計算
mint_comb comb_mod(ll n, ll k){
if (n < k) return 0;
if (n < 0 || k < 0) return 0;
return fac[n] * finv[k] * finv[n - k];
}
//make_random
//long long
ll rand_ll(ll l, ll r){
if(l > r)swap(l, r);
random_device rd;
mt19937_64 gen(rd());
uniform_int_distribution<ll>dis(l, r);
return dis(gen);
}
//int
int rand_int(int l, int r){
if(l > r)swap(l, r);
return l + rand() % (r - l + 1);
}
//double
ld rand_double(){
return (ld)1.0 * rand() / RAND_MAX;
}
//base_conversion
ll ntodec(const char c){
if(c >= '0' && c <= '9'){
return (ll)c - '0';
}else{
return (ll)c - 55;
}
}
char decton(const ll n){
if(n >= 0 && n <= 9){
return (char)'0' + n;
}else{
return (char)55 + n;
}
}
inline ll pow_ll(ll x,ll n){
ll ret = 1;
rep(i,n){
ret *= x;
}
return ret;
}
string base_conversion(string str, ll n, ll m){
ull tmp = 0;
string ret;
rep(i,str.size()){
tmp += (ull)ntodec(str[str.size() - 1 - i]) * pow_ll(n, i);
}
if(tmp == 0){
return "0";
}
while(tmp != 0){
ret = decton(tmp % m) + ret;
tmp /= m;
}
return ret;
}
//calc_triangle
long double calc_triangle(long double x1,long double y1,long double x2,long double y2,long double x3,long double y3){
return abs((x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2)) / 2.0);
}
//文字列の最小周期
vector<ll> computeLPSArray(const string& pattern) {
ll m = pattern.length();
vector<ll> lps(m);
ll len = 0;
lps[0] = 0;
ll i = 1;
while (i < m) {
if (pattern[i] == pattern[len]) {
len++;
lps[i] = len;
i++;
} else {
if (len != 0) {
len = lps[len - 1];
} else {
lps[i] = 0;
i++;
}
}
}
return lps;
}
ll findMinimumPeriod(const string& str) {
ll n = str.length();
vector<ll> lps = computeLPSArray(str);
ll len = lps[n - 1];
ll period = n - len;
if (n % period == 0) {
return period;
} else {
return n;
}
}
//-----------------------graph-----------------------//
//graph_template
struct Edge{
ll to;
ll cost;
Edge(ll to, ll cost) : to(to), cost(cost) {}
bool operator>(const Edge &e) const{
return cost > e.cost;
}
bool operator<(const Edge &e) const{
return cost < e.cost;
}
};
struct Edge2{
ll from;
ll to;
ll cost;
Edge2(ll from, ll to, ll cost) : from(from), to(to), cost(cost) {}
bool operator>(const Edge2 &e) const{
return cost > e.cost;
}
bool operator<(const Edge2 &e) const{
return cost < e.cost;
}
};
struct Edge3 {
ll to;
Edge3(ll to) : to(to) {}
};
struct Graph{
Graph() = default;
vector<vector<Edge>> G;
Graph(ll N){
G.resize(N);
}
ll size(){
return G.size();
}
void add(ll from, ll to, ll cost = 1){
G[from].push_back(Edge(to, cost));
G[to].push_back(Edge(from, cost));
}
void add_di(ll from, ll to, ll cost = 1){
G[from].push_back(Edge(to, cost));
}
vector<Edge> &operator[](ll v){
return G[v];
}
};
//bfs1(単一始点最短経路)
struct bfs1{
vector<bool> visited;
vector<ll> dist;
vector<ll> parent;
//bfs1(単一始点最短経路)を構築
bfs1(Graph &g, ll s){
ll n = g.size();
visited.assign(n, false);
dist.assign(n, -1);
parent.assign(n, -1);
visited[s] = true;
dist[s] = 0;
parent[s] = -1;
queue<ll> que;
que.push(s);
while(!que.empty()){
ll cur = que.front();
que.pop();
for(auto nxt : g[cur]){
if(!visited[nxt.to]){
que.push(nxt.to);
visited[nxt.to] = true;
dist[nxt.to] = dist[cur] + 1;
parent[nxt.to] = cur;
}
}
}
}
//最小コストを求める
ll cost(ll to){
return dist[to];
}
//最短経路を求める
vector<ll> path(ll to){
vector<ll> path;
if(!visited[to]){
return path;
}
for(ll i = to; i != -1; i = parent[i]){
path.push_back(i);
}
reverse(path.begin(), path.end());
return path;
}
//到達可能か調べる
bool cango(ll to){
return visited[to];
}
};
//bfs2(全点対最短経路)
struct bfs2{
vector<vector<bool>> visited;
vector<vector<ll>> dist;
vector<vector<ll>> parent;
bfs2(Graph &g){
ll n = g.size();
visited.assign(n, vector<bool>(n, false));
dist.assign(n, vector<ll>(n, -1));
parent.assign(n, vector<ll>(n, -1));
for(ll s = 0; s < n; s++){
visited[s][s] = true;
dist[s][s] = 0;
parent[0][0] = -1;
queue<ll> que;
que.push(s);
while(!que.empty()){
ll cur = que.front();
que.pop();
for(auto nxt : g[cur]){
if(!visited[s][nxt.to]){
que.push(nxt.to);
visited[s][nxt.to] = true;
dist[s][nxt.to] = dist[s][cur] + 1;
parent[s][nxt.to] = cur;
}
}
}
}
}
//最小コストを求める
ll cost(ll from, ll to){
return dist[from][to];
}
//最短経路を求める
vector<ll> path(ll from, ll to){
vector<ll> path;
if(!visited[from][to]){
return path;
}
for(ll i = to; i != -1; i = parent[from][i]){
path.push_back(i);
}
reverse(path.begin(), path.end());
return path;
}
//到達可能か調べる
bool cango(ll from, ll to){
return visited[from][to];
}
};
//dijkstra
struct dijkstra{
vector<ll> dist;
vector<ll> prev;
//dijkstraを構築
dijkstra(Graph &G, ll s){
ll N = G.size();
dist.assign(N, 1LL << 60);
prev.assign(N, -1);
priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq;
dist[s] = 0;
pq.emplace(dist[s], s);
while (!pq.empty()){
auto p = pq.top();
pq.pop();
ll v = p.second;
if(dist[v] < p.first)continue;
for (auto &e : G[v]){
if (dist[e.to] > dist[v] + e.cost){
dist[e.to] = dist[v] + e.cost;
prev[e.to] = v;
pq.emplace(dist[e.to], e.to);
}
}
}
}
//最小コストを求める
ll cost(ll to){
return dist[to];
}
//最短経路を求める
vector<ll> path(ll to){
vector<ll> get_path;
for (ll i = to; i != -1; i = prev[i]){
get_path.push_back(i);
}
reverse(get_path.begin(), get_path.end());
return get_path;
}
//到達可能か調べる
bool cango(ll to){
return dist[to] != 1LL << 60;
}
};
//bellman_ford
struct bellman_ford{
vector<ll> dist;
vector<ll> prev;
ll start;
ll n;
bool cl = false;
//bellman_fordを構築
bellman_ford(Graph &g, ll s){
start = s;
n = g.size();
dist.assign(n, 1LL << 60);
prev.assign(n, -1);
vector<ll> counts(n);
vector<bool> inqueue(n);
queue<ll> q;
dist[s] = 0;
q.push(s);
inqueue[s] = true;
while(!q.empty()){
ll from = q.front();
q.pop();
inqueue[from] = false;
for(auto &e : g[from]){
ll d = dist[from] + e.cost;
if(d < dist[e.to]){
dist[e.to] = d;
prev[e.to] = from;
if(!inqueue[e.to]){
q.push(e.to);
inqueue[e.to] = true;
++counts[e.to];
if(n < counts[e.to])cl = true;
}
}
}
}
}
//最小コストを求める
ll cost(ll to){
return dist[to];
}
//最短経路を求める
vector<ll> path(ll to){
vector<ll> path;
if(dist[to] != 1LL << 60){
for(ll i = to; i != -1; i = prev[i]){
path.push_back(i);
}
reverse(path.begin(), path.end());
}
return path;
}
//到達可能か調べる
bool cango(ll to){
return (dist[to] != 1LL << 60);
}
//負の閉路の有無を調べる
bool closed(){
return cl;
}
};
//warshall_floyd
struct warshall_floyd{
vector<vector<ll>> d;
vector<vector<ll>> next;
bool cl = false;
//warshall_floydを構築
warshall_floyd(Graph &g){
ll n = g.size();
d.resize(n, vector<ll>(n, 1LL << 60));
next.resize(n, vector<ll>(n, -1));
for(ll i = 0; i < n; i++){
d[i][i] = 0;
}
for(ll i = 0; i < n; i++){
for(auto e : g[i]){
d[i][e.to] = e.cost;
next[i][e.to] = e.to;
}
}
for(ll k = 0; k < n; ++k){
for(ll i = 0; i < n; ++i){
for(ll j = 0; j < n; ++j){
if(d[i][k] == 1LL << 60 || d[k][j] == 1LL << 60)continue;
if(d[i][j] > d[i][k] + d[k][j]){
d[i][j] = d[i][k] + d[k][j];
next[i][j] = next[i][k];
}
}
}
}
for(ll i = 0; i < n; i++){
if(d[i][i] < 0){
cl = true;
break;
}
}
}
//最小コストを求める
ll cost(ll from, ll to){
return d[from][to];
}
//最短経路を求める
vector<ll> path(ll from, ll to) {
if (d[from][to] == 1LL << 60) return {};
vector<ll> path;
for(ll at = from; at != to; at = next[at][to]){
if (at == -1) return {};
path.push_back(at);
}
path.push_back(to);
return path;
}
//到達可能か調べる
bool cango(ll from, ll to){
return d[from][to] != 1LL << 60;
}
//負の閉路の有無を調べる
bool closed(){
return cl;
}
};
//DSU
struct DSU{
vector<ll>par, rank, siz;
DSU(ll n):par(n, -1), rank(n, 0), siz(n, 1){}
//根を求める
ll leader(ll x){
if(par[x] == -1){
return x;
}else{
return par[x] = leader(par[x]);
}
}
//連結判定
bool same(ll x, ll y){
return leader(x) == leader(y);
}
//連結
bool merge(ll x, ll y){
ll rx = leader(x), ry = leader(y);
if(rx == ry){
return false;
}
if(rank[rx] < rank[ry]){
swap(rx, ry);
}
par[ry] = rx;
if(rank[rx] == rank[ry]){
rank[rx]++;
}
siz[rx] += siz[ry];
return true;
}
//集合の大きさを求める
ll size(ll x){
return siz[leader(x)];
}
};
template<class Abel>struct Weighted_UnionFind{
vector<ll> par;
vector<ll> rank;
vector<Abel> diff_weight;
Weighted_UnionFind(ll n = 1, Abel SUM_UNITY = 0){
init(n, SUM_UNITY);
}
void init(ll n = 1, Abel SUM_UNITY = 0){
par.resize(n);
rank.resize(n);
diff_weight.resize(n);
for(ll i = 0; i < n; ++i)par[i] = i, rank[i] = 0, diff_weight[i] = SUM_UNITY;
}
ll root(ll x){
if(par[x] == x){
return x;
}else{
ll r = root(par[x]);
diff_weight[x] += diff_weight[par[x]];
return par[x] = r;
}
}
Abel weight(ll x){
root(x);
return diff_weight[x];
}
bool issame(ll x, ll y){
return root(x) == root(y);
}
//x + w = y
bool unite(ll x, ll y, Abel w){
w += weight(x); w -= weight(y);
x = root(x); y = root(y);
if(x==y)return false;
if(rank[x] < rank[y])swap(x, y), w = -w;
if(rank[x]==rank[y])++rank[x];
par[y] = x;
diff_weight[y] = w;
return true;
}
Abel diff(ll x, ll y){
return weight(y) - weight(x);
}
};
struct kruskal{
ll n;
vector<Edge2> edges;
bool mn_finish = false, mx_finish = false;
ll mn, mx;
set<ll> mn_node, mx_node;
set<ll> mn_path, mx_path;
//kruskalの構築
kruskal(Graph &g){
n = g.size();
for(ll i = 0; i < n; i++){
for(auto e : g[i]){
edges.emplace_back(i, e.to, e.cost);
}
}
}
//最小全域木のコストを求める
ll min_cost(){
if(mn_finish){
return mn;
}
sort(edges.begin(), edges.end());
DSU dsu(n);
ll ret = 0;
for(auto e : edges){
if(dsu.merge(e.from, e.to)){
ret += e.cost;
mn_node.insert(e.from);
mn_node.insert(e.to);
}
}
return mn = ret;
}
//最大全域木のコストを求める
ll max_cost(){
if(mx_finish){
return mx;
}
sort(edges.rbegin(), edges.rend());
DSU dsu(n);
ll ret = 0;
for(auto e : edges){
if(dsu.merge(e.from, e.to)){
ret += e.cost;
mx_node.insert(e.from);
mx_node.insert(e.to);
}
}
return mx = ret;
}
//最小全域木のノードをsetで求める
set<ll> min_node(){
if(mn_finish){
return mn_node;
}
sort(edges.begin(), edges.end());
DSU dsu(n);
ll ret = 0;
for(auto e : edges){
if(dsu.merge(e.from, e.to)){
ret += e.cost;
mn_node.insert(e.from);
mn_node.insert(e.to);
}
}
return mn_node;
}
//最大全域木のノードをsetで求める
set<ll> max_node(){
if(mx_finish){
return mx_node;
}
sort(edges.rbegin(), edges.rend());
DSU dsu(n);
ll ret = 0;
for(auto e : edges){
if(dsu.merge(e.from, e.to)){
ret += e.cost;
mx_node.insert(e.from);
mx_node.insert(e.to);
}
}
return mx_node;
}
//最小全域木のパスをsetで求める
set<ll> min_path(){
if(mn_finish){
return mn_path;
}
sort(edges.begin(), edges.end());
DSU dsu(n);
ll ret = 0;
for(auto e : edges){
if(dsu.merge(e.from, e.to)){
ret += e.cost;
mn_node.insert(e.from);
mn_node.insert(e.to);
}
}
return mn_node;
}
};
//LCA
struct LCA {
vector<vector<ll>> parent;
vector<ll> dist;
LCA(Graph &g, ll root = 0){
vector<vector<Edge3>> G(g.size());
for(ll i = 0; i < g.size(); i++){
for(auto e : g[i]){
G[i].emplace_back(e.to);
}
}
ll V = G.size();
ll K = 1;
while ((1 << K) < V) K++;
parent.assign(K, vector<ll>(V, -1));
dist.assign(V, -1);
dfs(G, root, -1, 0);
for (ll k = 0; k + 1 < K; k++) {
for (ll v = 0; v < V; v++) {
if (parent[k][v] < 0) {
parent[k + 1][v] = -1;
} else {
parent[k + 1][v] = parent[k][parent[k][v]];
}
}
}
}
void dfs(const vector<vector<Edge3>> &G, ll v, ll p, ll d) {
parent[0][v] = p;
dist[v] = d;
for (auto e : G[v]) {
if (e.to != p) dfs(G, e.to, v, d + 1);
}
}
//最小共通祖先を求める
ll query(ll u, ll v) {
if (dist[u] < dist[v]) swap(u, v);
ll K = parent.size();
for (ll k = 0; k < K; k++) {
if ((dist[u] - dist[v]) >> k & 1) {
u = parent[k][u];
}
}
if (u == v) return u;
for (ll k = K - 1; k >= 0; k--) {
if (parent[k][u] != parent[k][v]) {
u = parent[k][u];
v = parent[k][v];
}
}
return parent[0][u];
}
//最短距離を求める
ll get_dist(ll u, ll v){
return dist[u] + dist[v] - 2 * dist[query(u, v)];
}
//aがuとvのpath上にあるか
bool is_on_path(ll u, ll v, ll a){
return get_dist(u, a) + get_dist(a, v) == get_dist(u, v);
}
};
struct AuxiliaryTree {
vector<vector<ll>> G0;
LCA &lca;
AuxiliaryTree(LCA &lca) : lca(lca) {}
void build(ll k, vector<ll> &vs) {
sort(vs.begin(), vs.begin() + k, [&](ll a, ll b) { return lca.dist[a] < lca.dist[b]; });
stack<ll> stk;
stk.push(vs[0]);
G0[vs[0]].clear();
for (ll i = 1; i < k; ++i) {
ll w = lca.query(vs[i - 1], vs[i]);
if (w != vs[i - 1]) {
ll last = stk.top(); stk.pop();
while (!stk.empty() && lca.dist[w] < lca.dist[stk.top()]) {
G0[stk.top()].push_back(last);
last = stk.top(); stk.pop();
}
if (stk.empty() || stk.top() != w) {
stk.push(w);
vs.push_back(w);
G0[w] = { last };
} else {
G0[w].push_back(last);
}
}
stk.push(vs[i]);
G0[vs[i]].clear();
}
while (stk.size() > 1) {
ll u = stk.top(); stk.pop();
G0[stk.top()].push_back(u);
}
}
};
//centroid_decomposition
struct centroid_decomposition{
Graph g;
ll n;
vector<ll> size;
ll centroid;
centroid_decomposition(Graph f) : g(f){
g = f;
n = g.size();
size.resize(n, 1);
stack<tuple<ll, ll, ll>> st;
st.push({0, 0, 0});
while (!st.empty()) {
ll v, p, t;
tie(v, p, t) = st.top();
st.pop();
if (t == 0) {
st.push({v, p, 1});
for (auto [c, d] : g[v]) {
if (c != p) {
st.push({c, v, 0});
}
}
} else {
bool is_centroid = true;
for (auto [c, d] : g[v]) {
if (c != p) {
size[v] += size[c];
if (size[c] > n / 2) {
is_centroid = false;
}
}
}
if (is_centroid && n - size[v] <= n / 2) {
centroid = v;
}
}
}
}
//木の重心を求める
ll get_centroid(){
return centroid;
}
//重心によって分解された部分木を求める
vector<vector<ll>> get_subtree(){
vector<vector<ll>> comp(n);
stack<tuple<ll, ll, ll>> st;
for(auto [v, w] : g[centroid]){
st.push({v, centroid, v});
}
while(!st.empty()){
auto[v, p, i] = st.top();
st.pop();
comp[i].push_back(v);
for(auto [c, d] : g[v]){
if(c != p){
st.push({c, v, i});
}
}
}
return comp;
}
};
//動的セグ木
template <class S, S (*op)(S, S), S (*e)()> class dynamic_segtree {
public:
dynamic_segtree(size_t n) : n(n), root(nullptr) {}
void set(size_t p, S x) {
assert(p < n);
set(root, 0, n, p, x);
}
S get(size_t p) const {
assert(p < n);
return get(root, 0, n, p);
}
S prod(size_t l, size_t r) const {
assert(l <= r && r <= n);
return prod(root, 0, n, l, r);
}
S all_prod() const { return root ? root->product : e(); }
void reset(size_t l, size_t r) {
assert(l <= r && r <= n);
return reset(root, 0, n, l, r);
}
template <bool (*f)(S)> size_t max_right(size_t l) const {
return max_right(l, [](S x) { return f(x); });
}
template <class F> size_t max_right(size_t l, const F& f) const {
assert(l <= n);
S product = e();
assert(f(product));
return max_right(root, 0, n, l, f, product);
}
template <bool (*f)(S)> size_t min_left(size_t r) const {
return min_left(r, [](S x) { return f(x); });
}
template <class F> size_t min_left(size_t r, const F& f) const {
assert(r <= n);
S product = e();
assert(f(product));
return min_left(root, 0, n, r, f, product);
}
private:
struct node;
using node_ptr = std::unique_ptr<node>;
struct node {
size_t index;
S value, product;
node_ptr left, right;
node(size_t index, S value)
: index(index),
value(value),
product(value),
left(nullptr),
right(nullptr) {}
void update() {
product = op(op(left ? left->product : e(), value),
right ? right->product : e());
}
};
const size_t n;
node_ptr root;
void set(node_ptr& t, size_t a, size_t b, size_t p, S x) const {
if (!t) {
t = std::make_unique<node>(p, x);
return;
}
if (t->index == p) {
t->value = x;
t->update();
return;
}
size_t c = (a + b) >> 1;
if (p < c) {
if (t->index < p) std::swap(t->index, p), std::swap(t->value, x);
set(t->left, a, c, p, x);
} else {
if (p < t->index) std::swap(p, t->index), std::swap(x, t->value);
set(t->right, c, b, p, x);
}
t->update();
}
S get(const node_ptr& t, size_t a, size_t b, size_t p) const {
if (!t) return e();
if (t->index == p) return t->value;
size_t c = (a + b) >> 1;
if (p < c) return get(t->left, a, c, p);
else return get(t->right, c, b, p);
}
S prod(const node_ptr& t, size_t a, size_t b, size_t l, size_t r) const {
if (!t || b <= l || r <= a) return e();
if (l <= a && b <= r) return t->product;
size_t c = (a + b) >> 1;
S result = prod(t->left, a, c, l, r);
if (l <= t->index && t->index < r) result = op(result, t->value);
return op(result, prod(t->right, c, b, l, r));
}
void reset(node_ptr& t, size_t a, size_t b, size_t l, size_t r) const {
if (!t || b <= l || r <= a) return;
if (l <= a && b <= r) {
t.reset();
return;
}
size_t c = (a + b) >> 1;
reset(t->left, a, c, l, r);
reset(t->right, c, b, l, r);
t->update();
}
template <class F>
size_t max_right(const node_ptr& t, size_t a, size_t b,
size_t l, const F& f, S& product) const {
if (!t || b <= l) return n;
if (f(op(product, t->product))) {
product = op(product, t->product);
return n;
}
size_t c = (a + b) >> 1;
size_t result = max_right(t->left, a, c, l, f, product);
if (result != n) return result;
if (l <= t->index) {
product = op(product, t->value);
if (!f(product)) return t->index;
}
return max_right(t->right, c, b, l, f, product);
}
template <class F>
size_t min_left(const node_ptr& t, size_t a, size_t b,
size_t r, const F& f, S& product) const {
if (!t || r <= a) return 0;
if (f(op(t->product, product))) {
product = op(t->product, product);
return 0;
}
size_t c = (a + b) >> 1;
size_t result = min_left(t->right, c, b, r, f, product);
if (result != 0) return result;
if (t->index < r) {
product = op(t->value, product);
if (!f(product)) return t->index + 1;
}
return min_left(t->left, a, c, r, f, product);
}
};
//----------------------normal-----------------------//
const ld PI = 3.1415926535897932;
const ll mod = 998244353;
const ll MOD = 1000000007;
const ll LINF = 1001001001001001001;
const ll INF = 1001001001;
const ll dx[] = {-1, 0, 1, 0, -1, 1, 1, -1};
const ll dy[] = {0, 1, 0, -1, 1, 1, -1, -1};
const string ALPHA = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const string alpha = "abcdefghijklmnopqrstuvwxyz";
//using mint = atcoder::modint;
//using mint = atcoder::static_modint<1000000021>;
//using mint = atcoder::modint998244353;
using mint = atcoder::modint1000000007;
/*-----------------------function------------------------*/
using S = long long;
S op(S a, S b){
return a + b;
}
S e(){
return 0LL;
}
/*------------------------solve--------------------------*/
void solve(){
ll n; cin >> n;
dynamic_segtree<S, op, e> sg(1000000001);
ll ans = 0;
while(n--){
ll t; cin >> t;
if(t == 0){
ll x, y; cin >> x >> y;
sg.set(x, sg.get(x) + y);
}else{
ll l, r; cin >> l >> r;
ans += sg.prod(l, r + 1);
}
}
cout << ans << endl;
}
int main(){
cin.tie(nullptr);
cout.tie(nullptr);
ios::sync_with_stdio(false);
cout << fixed << setprecision(20);
srand((unsigned)time(NULL));
//ll T; cin >> T;
ll T = 1;
while(T--){
solve();
}
return 0;
}