結果
| 問題 | No.2650 [Cherry 6th Tune *] セイジャク |
| ユーザー |
 Taiki0715
|
| 提出日時 | 2024-02-23 21:39:19 |
| 言語 | C++17(clang) (17.0.6 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 481 ms / 2,500 ms |
| コード長 | 6,507 bytes |
| コンパイル時間 | 4,761 ms |
| コンパイル使用メモリ | 182,272 KB |
| 実行使用メモリ | 13,100 KB |
| 最終ジャッジ日時 | 2024-09-29 05:53:11 |
| 合計ジャッジ時間 | 17,021 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 31 |
ソースコード
#include <bits/stdc++.h>using namespace std;#if __has_include(<atcoder/all>)#include <atcoder/all>using namespace atcoder;template<int mod>istream &operator>>(istream &is,static_modint<mod> &a){long long b;is>>b;a=b;return is;}istream &operator>>(istream &is,modint &a){long long b;cin>>b;a=b;return is;}#endif#ifdef LOCAL#include "debug.h"#else#define debug(...) static_cast<void>(0)#define debugg(...) static_cast<void>(0)template<typename T1,typename T2>ostream &operator<<(ostream &os,const pair<T1,T2>&p){os<<p.first<<' '<<p.second;return os;}#endifusing ll=long long;using ull=unsigned long long;using P=pair<ll,ll>;template<typename T>using minque=priority_queue<T,vector<T>,greater<T>>;template<typename T>bool chmax(T &a,const T &b){return (a<b?(a=b,true):false);}template<typename T>bool chmin(T &a,const T &b){return (a>b?(a=b,true):false);}template<typename T1,typename T2>istream &operator>>(istream &is,pair<T1,T2>&p){is>>p.first>>p.second;return is;}template<typename T>istream &operator>>(istream &is,vector<T> &a){for(auto &i:a)is>>i;return is;}template<typename T1,typename T2>void operator++(pair<T1,T2>&a,int n){a.first++,a.second++;}template<typename T1,typename T2>void operator--(pair<T1,T2>&a,int n){a.first--,a.second--;}template<typename T>void operator++(vector<T>&a,int n){for(auto &i:a)i++;}template<typename T>void operator--(vector<T>&a,int n){for(auto &i:a)i--;}#define reps(i,a,n) for(int i=(a);i<(n);i++)#define rep(i,n) reps(i,0,n)#define all(x) x.begin(),x.end()#define pcnt(x) __builtin_popcountll(x)ll myceil(ll a,ll b){return (a+b-1)/b;}template<typename T,size_t n,size_t id=0>auto vec(const int (&d)[n],const T &init=T()){if constexpr (id<n)return vector(d[id],vec<T,n,id+1>(d,init));else return init;}void SOLVE();int main(){ios::sync_with_stdio(false);cin.tie(nullptr);#ifdef LOCALclock_t start=clock();#endifint testcase=1;//cin>>testcase;for(int i=0;i<testcase;i++){SOLVE();}#ifdef LOCALcerr<<"time:";cerr<<(clock()-start)/1000;cerr<<"ms\n";#endif}template<typename T>struct SegmentTreeBeats{private:static constexpr T INF=numeric_limits<T>::max()/2;struct node{T sum;T mx,mx2,mn,mn2;int mxcnt,mncnt;node(T x):sum(x),mx(x),mx2(-INF),mn(x),mn2(INF),mxcnt(1),mncnt(1){}node():sum(0),mx(-INF),mx2(-INF),mn(INF),mn2(INF),mxcnt(0),mncnt(0){}};struct F{T chmax,chmin,add;F(T x,int id):chmax(-INF),chmin(INF),add(0){if(id==0)chmin=x;else if(id==1)chmax=x;else if(id==2)add=x;else chmax=chmin=x;}F():chmax(-INF),chmin(INF),add(0){}};int n,z,log2n;vector<node>dat;vector<F>lazy;void update(int id){node &ret=dat[id],&a=dat[id*2],&b=dat[id*2+1];ret.sum=a.sum+b.sum;if(a.mx==b.mx){ret.mx=a.mx;ret.mxcnt=a.mxcnt+b.mxcnt;ret.mx2=max(a.mx2,b.mx2);}else if(a.mx<b.mx){ret.mx=b.mx;ret.mxcnt=b.mxcnt;ret.mx2=max(a.mx,b.mx2);}else{ret.mx=a.mx;ret.mxcnt=a.mxcnt;ret.mx2=max(a.mx2,b.mx);}if(a.mn==b.mn){ret.mn=a.mn;ret.mncnt=a.mncnt+b.mncnt;ret.mn2=min(a.mn2,b.mn2);}else if(a.mn<b.mn){ret.mn=a.mn;ret.mncnt=a.mncnt;ret.mn2=min(a.mn2,b.mn);}else{ret.mn=b.mn;ret.mncnt=b.mncnt;ret.mn2=min(a.mn,b.mn2);}}bool mapping(F &f,int id){node &x=dat[id];if(x.mn<f.chmax){if(x.mx<=f.chmax){x.sum=(f.chmax+f.add)<<(__builtin_clz(id)+log2n-31);x.mx=x.mn=f.chmax+f.add;x.mxcnt=x.mncnt=1<<(__builtin_clz(id)+log2n-31);x.mx2=-INF,x.mn2=INF;return true;}if(x.mn2<=f.chmax)return false;x.sum+=x.mncnt*(f.chmax-x.mn);x.mn=f.chmax;if(x.mx2<f.chmax)x.mx2=f.chmax;}if(x.mx>f.chmin){if(x.mn>=f.chmin){x.sum=(f.chmin+f.add)<<(__builtin_clz(id)+log2n-31);x.mx=x.mn=f.chmin+f.add;x.mxcnt=x.mncnt=1<<(__builtin_clz(id)+log2n-31);x.mx2=-INF,x.mn2=INF;return true;}if(x.mx2>=f.chmin)return false;x.sum-=x.mxcnt*(x.mx-f.chmin);x.mx=f.chmin;if(x.mn2>f.chmin)x.mn2=f.chmin;}x.sum+=f.add<<(__builtin_clz(id)+log2n-31);x.mx+=f.add;x.mx2+=f.add;x.mn+=f.add;x.mn2+=f.add;return true;}void composition(F f,F &g){f.chmax-=g.add;f.chmin-=g.add;g.add+=f.add;if(f.chmin<=g.chmax)g.chmax=g.chmin=f.chmin;else if(f.chmax>=g.chmin)g.chmax=g.chmin=f.chmax;else{if(g.chmax<f.chmax)g.chmax=f.chmax;if(g.chmin>f.chmin)g.chmin=f.chmin;}}void apply2(int id,F &f){if(id<z)composition(f,lazy[id]);if(!mapping(f,id))push(id),update(id);}void push(int id){apply2(id*2,lazy[id]);apply2(id*2+1,lazy[id]);lazy[id]=F();}void apply(int l,int r,F f){l+=z,r+=z;for(int i=log2n;i>=1;i--){if(((l>>i)<<i)!=l)push(l>>i);if(((r>>i)<<i)!=r)push((r-1)>>i);}int a=l,b=r;while(l<r){if(l&1)apply2(l++,f);if(r&1)apply2(--r,f);l>>=1,r>>=1;}swap(a,l),swap(b,r);for(int i=1;i<=log2n;i++){if(((l>>i)<<i)!=l)update(l>>i);if(((r>>i)<<i)!=r)update((r-1)>>i);}}public:SegmentTreeBeats(vector<T>a):n(a.size()),z(1),log2n(0){while(z<n)z<<=1,log2n++;dat.resize(z*2);lazy.resize(z);rep(i,n)dat[i+z]=node(a[i]);for(int i=z-1;i>=1;i--)update(i);}inline void chmin(int l,int r,T x){apply(l,r,F(x,0));}inline void chmax(int l,int r,T x){apply(l,r,F(x,1));}inline void add(int l,int r,T x){apply(l,r,F(x,2));}inline void assign(int l,int r,T x){apply(l,r,F(x,3));}T sum(int l,int r){l+=z,r+=z;for(int i=log2n;i>=1;i--){if(((l>>i)<<i)!=l)push(l>>i);if(((r>>i)<<i)!=r)push((r-1)>>i);}T ret=0;while(l<r){if(l&1)ret+=dat[l++].sum;if(r&1)ret+=dat[--r].sum;l>>=1,r>>=1;}return ret;}};void SOLVE(){int n,m;cin>>n>>m;vector<int>a(n);cin>>a;auto z(a);sort(all(z)),z.erase(unique(all(z)),z.end());rep(i,n)a[i]=lower_bound(all(z),a[i])-z.begin();SegmentTreeBeats<int>seg(vector<int>(z.size(),-1));int t;cin>>t;rep(i,t){int l,r;cin>>l>>r;r++;l=lower_bound(all(z),l)-z.begin();r=lower_bound(all(z),r)-z.begin();seg.chmax(l,r,i+1);}rep(i,n)cout<<seg.sum(a[i],a[i]+1)<<endl;}