2020-02-24 21:50:46 C++

C++

Copy Copied! Full
#include <bits/stdc++.h> #define ALL(A) (A).begin(), (A).end() #define ll long long #define rep(i, n) for (int i = 0; i < (n); i++) using namespace std; template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } const ll mod = 1e9 + 7; const ll INF = -1 * ((1LL << 63) + 1); const int inf = -1 * ((1 << 31) + 1); template<typename T> struct BIT { int n; vector<T> d; BIT(int n=0):n(n),d(n+1) {} void add(int i,T x=1){ for(i; i < n; i |= i+1){ d[i] += x; } } T sum(int i){ T x = 0; for(;i>=0;i= (i&(i+1))-1) { x += d[i]; } return x; } T query(int x){ int ret = 0; for(;x>=0;x=(x&(x+1))-1){ // -> 0-indexedに変換 ret = max(ret, d[x]); } return ret; } void set(int x, int v){ for(;x<n;x|=x+1){ // -> 0-indexedに変換 d[x] = max(d[x], v); } } }; int main(void){ cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20); BIT<int> bit(1005); bit.add(0,1000); bit.add(1,500); cout << bit.query(1000) << endl; }
RECOMMEND