結果

問題 No.877 Range ReLU Query
ユーザー NyaanNyaanNyaanNyaan
提出日時 2019-09-06 23:03:05
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 9,903 bytes
コンパイル時間 2,160 ms
コンパイル使用メモリ 193,496 KB
実行使用メモリ 19,456 KB
最終ジャッジ日時 2024-06-24 20:57:42
合計ジャッジ時間 6,271 ms
ジャッジサーバーID
(参考情報)
judge5 / judge3
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
10,624 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 4 ms
5,376 KB
testcase_09 AC 2 ms
5,376 KB
testcase_10 AC 2 ms
5,376 KB
testcase_11 TLE -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
#define whlie while
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define rep(i,N) for(int i = 0; i < (N); i++)
#define repr(i,N) for(int i = (N) - 1; i >= 0; i--)
#define rep1(i,N) for(int i = 1; i <= (N) ; i++)
#define repr1(i,N) for(int i = (N) ; i > 0 ; i--)
#define each(x,v) for(auto& x : v)
#define all(v) (v).begin(),(v).end()
#define sz(v) ((int)(v).size())
#define vrep(v,it) for(auto it = v.begin(); it != v.end(); it++)
#define vrepr(v,it) for(auto it = v.rbegin(); it != v.rend(); it++)
#define ini(...) int __VA_ARGS__; in(__VA_ARGS__)
#define inl(...) ll __VA_ARGS__; in(__VA_ARGS__)
#define ins(...) string __VA_ARGS__; in(__VA_ARGS__)
using namespace std; void solve();
using ll = long long; using vl = vector<ll>;
using vi = vector<int>; using vvi = vector< vector<int> >;
constexpr int inf = 1001001001;
constexpr ll infLL = (1LL << 61) - 1;
struct IoSetupNya {IoSetupNya() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); cerr << fixed << setprecision(7
    );} } iosetupnya;
template<typename T, typename U> inline bool amin(T &x, U y) { return (y < x) ? (x = y, true) : false; }
template<typename T, typename U> inline bool amax(T &x, U y) { return (x < y) ? (x = y, true) : false; }
template<typename T, typename U> ostream& operator <<(ostream& os, const pair<T, U> &p) { os << p.first << " " << p.second; return os; }
template<typename T, typename U> istream& operator >>(istream& is, pair<T, U> &p) { is >> p.first >> p.second; return is; }
template<typename T> ostream& operator <<(ostream& os, const vector<T> &v) { int s = (int)v.size(); rep(i,s) os << (i ? " " : "") << v[i]; return os;
    }
template<typename T> istream& operator >>(istream& is, vector<T> &v) { for(auto &x : v) is >> x; return is; }
void in(){} template <typename T,class... U> void in(T &t,U &...u){ cin >> t; in(u...);}
void out(){cout << "\n";} template <typename T,class... U> void out(const T &t,const U &...u){ cout << t; if(sizeof...(u)) cout << " "; out(u...);}
template<typename T>void die(T x){out(x); exit(0);}
#ifdef NyaanDebug
#include "NyaanDebug.h"
#define trc(...) do { cerr << #__VA_ARGS__ << " = "; dbg_out(__VA_ARGS__);} while(0)
#define trca(v,...) do { cerr << #v << " = "; array_out(v , __VA_ARGS__ );} while(0)
#else
#define trc(...)
#define trca(...)
int main(){solve();}
#endif
using P = pair<int,int>;
using vp = vector<P>;
constexpr int MOD = /**/ 1000000007; //*/ 998244353;
/////////////////
//
template<typename T,typename F>
struct ST{
int size;
vector<T> seg;
const F func;
const T UNIT;
ST(int N,F func , T UNIT): func(func) , UNIT(UNIT) {
size = 1;
while(size < N) size <<= 1;
seg.assign(2 * size, UNIT);
}
ST(const vector<T> &v,F func , T UNIT) : func(func) , UNIT(UNIT){
// initialize
int N = (int)v.size();
size = 1;
while(size < N) size <<= 1;
seg.assign(2 * size , UNIT);
// set
for(int i = 0; i < N; i++){
seg[i + size] = v[i];
}
build();
}
void set(int k, T x){
seg[k + size] = x;
}
void build(){
for(int k = size-1; k > 0; k--){
seg[k] = func(seg[2 * k] , seg[2 * k + 1] );
}
}
void update(int k, T x){
k += size; seg[k] = x;
while(k >>= 1){
seg[k] = func( seg[2 * k] , seg[2 * k + 1] );
}
}
void add(int k , T x){
k += size; seg[k] += x;
while(k >>= 1){
seg[k] = func(seg[2 * k] , seg[2 * k + 1] );
}
}
// [a,b)
T query(int a, int b){
T L = UNIT, R = UNIT;
for(a+=size,b+=size; a<b; a>>=1,b>>=1){
if(a & 1) L = func(L,seg[a++]);
if(b & 1) R = func(seg[--b],R);
}
return func(L, R);
}
T operator[](const int &k) const{
return seg[k + size];
}
};
//
template <typename T,typename E,typename F,typename G,typename H>
struct LST{
int n,height;
F f;
G g;
H h;
T ti;
E ei;
vector<T> dat;
vector<E> laz;
LST(int n, F f,G g,H h,T ti,E ei):
f(f),g(g),h(h),ti(ti),ei(ei){
init(n);
}
LST(const vector<T> &v, F f,G g,H h,T ti,E ei):
f(f),g(g),h(h),ti(ti),ei(ei){
init( (int)v.size() );
build(v);
}
void init(int n_){
n=1;height=0;
while(n<n_) n<<=1,height++;
dat.assign(2*n,ti);
laz.assign(2*n,ei);
}
void build(const vector<T> &v){
int n_=v.size();
init(n_);
for(int i=0;i<n_;i++) dat[n+i]=v[i];
for(int i=n-1;i;i--)
dat[i]=f(dat[(i<<1)|0],dat[(i<<1)|1]);
}
inline T reflect(int k){
return laz[k]==ei?dat[k]:g(dat[k],laz[k]);
}
inline void eval(int k){
if(laz[k]==ei) return;
laz[(k<<1)|0]=h(laz[(k<<1)|0],laz[k]);
laz[(k<<1)|1]=h(laz[(k<<1)|1],laz[k]);
dat[k]=reflect(k);
laz[k]=ei;
}
inline void thrust(int k){
for(int i=height;i;i--) eval(k>>i);
}
inline void recalc(int k){
while(k>>=1)
dat[k]=f(reflect((k<<1)|0),reflect((k<<1)|1));
}
void update(int a,int b,E x){
thrust(a+=n);
thrust(b+=n-1);
for(int l=a,r=b+1;l<r;l>>=1,r>>=1){
if(l&1) laz[l]=h(laz[l],x),l++;
if(r&1) --r,laz[r]=h(laz[r],x);
}
recalc(a);
recalc(b);
}
void set_val(int a,T x){
thrust(a+=n);
dat[a]=x;laz[a]=ei;
recalc(a);
}
T query(int a,int b){
thrust(a+=n);
thrust(b+=n-1);
T vl=ti,vr=ti;
for(int l=a,r=b+1;l<r;l>>=1,r>>=1) {
if(l&1) vl=f(vl,reflect(l++));
if(r&1) vr=f(reflect(--r),vr);
}
return f(vl,vr);
}
};
// BIT
template< typename T >
struct BIT {
int N; int max_2beki;
vector< T > data;
// 1-indexed 0
BIT(int size){
N = ++size;
data.assign(N, 0);
max_2beki = 1;
while(max_2beki * 2 <= N) max_2beki *= 2;
}
// [0,k]()
T sum(int k) {
if(k < 0) return 0; // k<00
T ret = 0;
for(++k; k > 0; k -= k & -k) ret += data[k];
return (ret);
}
// [l,r]()
inline T sum(int l,int r){
return sum(r) - sum(l-1);
}
//
inline T operator[](int k){
return sum(k) - sum(k-1);
}
// data[k] += x;
void add(int k, T x) {
for(++k; k < N; k += k & -k) data[k] += x;
}
// imos [l,r]x
void imos(int l,int r,T x){
add(l , x); add(r + 1 , -x);
}
// lower_bound sum(i)vali
int lower_bound(T w){
if(w <= 0) return 0;
int x = 0;
for(int k = max_2beki; k > 0; k /= 2){
if(x+k <= N - 1 && data[x + k] < w){
w -= data[x + k];
x += k;
}
}
return x;
}
// upper_bound sum(i)vali
int upper_bound(T w){
if(w < 0) return 0;
int x = 0;
for(int k = max_2beki; k > 0; k /= 2){
if(x+k <= N - 1 && data[x + k] <= w){
w -= data[x + k];
x += k;
}
}
return x;
}
};
template<typename T>
struct BIT2D{
int H,W;
vector<vector<T>> bit;
BIT2D(int H,int W):H(H),W(W){
bit.resize(H + 1 , vector<T>(W + 1 , 0));
}
// index0-origin
// (x,y)w
//
void add(int x, int y, T w){
if(x < 0 || x >= H || y < 0 || y >= W) return;
for(int a = (++y , ++x); a <= H; a += a & -a){
for(int b = y ; b <= W; b += b & -b){
bit[a][b] += w;
}
}
}
// imos[(x1,y1) , (x2,y2)]w
void imos(int x1, int y1, int x2, int y2, T w){
add(x1 , y1 , w);
add(x1 , y2 + 1 , -w);
add(x2 + 1 , y1 , -w);
add(x2 + 1 , y2 + 1 , w);
}
// [(0,0) , (x,y)] 
// x,y<00 x>=H y>=Wx=H-1,y=W-1
// ( imos (x,y) )
T sum(int x, int y){
if(x < 0 || y < 0) return 0;
if(x >= H) return 0;
if(y >= W) return 0;
T ret = 0;
for(int a = (++y , ++x) ; a > 0; a -= a & -a){
for(int b = y; b > 0; b -= b & -b){
ret += bit[a][b];
}
}
return ret;
}
// [(x1,y1) , (x2,y2)]
// x1 > x2, y1 > y2swap
T sum(int x1,int y1, int x2, int y2){
if(x1 > x2) swap(x1 , x2);
if(y1 > y2) swap(y1 , y2);
return sum(x2,y2)-sum(x2,y1-1)-sum(x1-1,y2)+sum(x1-1,y1-1);
}
};
void solve(){
/*
using Monoid = ll;
auto f = [](Monoid a,Monoid b){return a + b; };
using SEG = ST<Monoid , decltype(f)>;
*/
ini(N,Q);
vl a(N) ; in(a);
vi ord(N); iota(all(ord) , 0);
sort(all(ord),[&](int l,int r){return a[l] < a[r];});
trc(ord);
vi invord(N); rep(i,N) invord[ord[i]] = i;
int bitn = min(N,4);
BIT2D<ll> bit(N , bitn);
BIT2D<int> bitexist(N,bitn);
auto bidx = [&](int idx)->int{return int(1LL * idx * bitn / N);};
vi l(bitn) , r(bitn) , li(bitn) , ri(bitn);
l[0] = a[ord[0]] , r[bitn-1] = a[ord[N-1]];
li[0] = 0 , ri[bitn-1] = N-1;
rep(i,N-1){
if(bidx(i) + 1 == bidx(i+1)){
r[bidx(i)] = a[ord[i]] , l[bidx(i+1)] = a[ord[i+1]];
ri[bidx(i)] = i, li[bidx(i+1)] = i + 1;
}
}
trc(l,r);
rep(i,N){
trc(i , bidx(invord[i]));
bit.add(i , bidx(invord[i]) , a[i]);
bitexist.add(i , bidx(invord[i]) , 1);
}
rep(hoge,Q){
ini(c,ln,rn); ln--; rn--; inl(x);
auto itr = lower_bound(all(r) , x);
if(itr == r.end()){out(0); continue;}
int nya = itr - r.begin();
ll ans = 0;
trc(nya);
if(nya != bitn - 1){
ans += bit.sum(ln , nya + 1 , rn , bitn-1);
trc(ans);
ans -= x * bitexist.sum(ln , nya + 1 , rn, bitn-1);
trc(ans);
}
// itr
for(int idx = li[nya]; idx <= ri[nya]; idx++){
trc(idx , ord[idx]);
if(ln <= ord[idx] && ord[idx] <= rn && a[ord[idx]] >= x)
ans += a[ord[idx]] - x;
}
out(ans);
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0