結果

問題 No.789 範囲の合計
コンテスト
ユーザー wk1080id
提出日時 2019-05-11 19:04:34
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 196 ms / 1,000 ms
コード長 2,598 bytes
コンパイル時間 989 ms
コンパイル使用メモリ 91,460 KB
実行使用メモリ 16,384 KB
最終ジャッジ日時 2024-07-02 01:16:42
合計ジャッジ時間 3,608 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cctype>
#include<math.h>
#include<string>
#include<string.h>
#include<stack>
#include<queue>
#include<vector>
#include<utility>
#include<set>
#include<map>
#include<stdlib.h>
#include<iomanip>

using namespace std;

#define ll long long
#define ld long double
#define EPS 0.0000000001
#define INF 1e9
#define LINF (ll)INF*INF
#define MOD 1000000007
#define rep(i,n) for(int i=0;i<(n);i++)
#define loop(i,a,n) for(int i=a;i<(n);i++)
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)

#define int ll //!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int,int> pii;
typedef vector<pii> vp;

int gcd(int a, int b){
    if(b==0) return a;
    return gcd(b,a%b);
}
int lcm(int a, int b){
    return a/gcd(a,b)*b;
}

class SegTree{

private:

    int n;
    vector<int> seg;
    int init = 0; //初期化の値（単位元）
    int combine(int a, int b){
        return a+b;
    }

public:

    SegTree (){}

    SegTree(int size){
		n=1;
		while(n<size)n<<=1;
		seg=vector<int>(2*n,init);
	}

	SegTree(const vector<int> &in){
		n=1;
		while(n<in.size())n<<=1;
		seg=vector<int>(2*n,init);
		for(int i=n-1+in.size()-1;i>=0;i--){
			if(n-1<=i)seg[i]=in[i-(n-1)];
			else seg[i]=combine(seg[i*2+1],seg[i*2+2]);
		}
	}


    //k-th(0-indexd) を a
    void update(int k,int a){
      k+=n-1;
      seg[k] += a;
      while(k>0){
        k=(k-1)/2;
        seg[k]=combine(seg[k*2+1],seg[k*2+2]);
      }
    }

    //[a,b)について調べる
    int query(int a,int b,int k=0,int l=0,int r=-1){
        if(r==-1)r=n;
        if(r<=a || b<=l)return init;
        if(a<=l &&r<=b)return seg[k];

        int vl=query(a,b,k*2+1,l,(l+r)/2);
        int vr=query(a,b,k*2+2,(l+r)/2,r);

        return combine(vl,vr);
    }
};

void compress(vi &v){
  sort(all(v));
  v.erase(unique(all(v)),v.end());
}
int idx(int i,vector<int> &c){
  return lower_bound(c.begin(),c.end(),i)-c.begin();
}

signed main(void) {
    int n;
    cin >> n;
    vi qa(n),qb(n),qc(n);
    vi x;
    rep(i,n){
        cin >> qa[i] >> qb[i] >> qc[i];
        x.push_back(qb[i]);
        x.push_back(qb[i]+1);
        if(qa[i]){
            x.push_back(qc[i]);
            x.push_back(qc[i]+1);
        }
    }
    compress(x);
    SegTree st(x.size());
    int ans = 0;
    rep(i,n){
        if(qa[i]){
            ans += st.query(idx(qb[i],x),idx(qc[i]+1,x));
        }else{
            st.update(idx(qb[i],x), qc[i]);
        }
    }
    cout << ans << endl;
}
0