結果

問題 No.318 学学学学学
ユーザー ensembleaverageensembleaverage
提出日時 2024-04-02 00:12:14
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 222 ms / 2,000 ms
コード長 4,964 bytes
コンパイル時間 3,699 ms
コンパイル使用メモリ 260,184 KB
実行使用メモリ 16,640 KB
最終ジャッジ日時 2024-09-30 22:56:05
合計ジャッジ時間 7,193 ms
ジャッジサーバーID
(参考情報)
judge2 / judge5
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

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

#include "bits/stdc++.h"
/*
#include "boost/multiprecision/cpp_int.hpp"
namespace mp = boost::multiprecision;
using i128=mp::cpp_int;
*/
using namespace std;
typedef long long ll;
typedef int64_t i64;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<vvll> vvvll;
typedef vector<string> vs;
typedef vector<char> vc;
typedef vector<vc> vvc;
typedef vector<double> vd;
typedef vector<vd> vvd;
#define rep(i,a,n) for(int i=a;i<n;i++)
#define drep(i,a,n) for(int i=a;i>n;i--)
#define yes(ans) if(ans)cout<<"yes"<<endl;else cout<<"no"<<endl;
#define Yes(ans) if(ans)cout<<"Yes"<<endl;else cout<<"No"<<endl;
#define YES(ans) if(ans)cout<<"YES"<<endl;else cout<<"NO"<<endl;
#define iINF 1000000007
#define lINF 10000000000007
#define llINF 4000000000000000007
#define all(x) x.begin(),x.end()
#define so(x) sort(all(x))
#define re(x) reverse(all(x))
const double PI = acos(-1);
//
template<typename S,S op(S l,S r),S e(),typename F,S mapping(F f,S prev),F composition(F f,F g),F id()>
struct lazysegment{
vector<S> tree;
vector<F> func;
int x=2;
lazysegment(vector<S> &data){ //n data(n)
int n=data.size();
while(x<2*n) x*=2;
tree.assign(x-1,e()); //(0~x-2)
func.assign(x-1,id());
int y=x/2;
rep(i,y-1,x-1){
if(i-y+1>=n) continue;
tree[i]=data[i-y+1];
}
drep(i,y-2,-1){
tree[i]=op(tree[2*i+1],tree[2*i+2]);
}
}
lazysegment(int n){
while(x<2*n) x*=2;
tree.assign(x-1,e()); //(0~x-2)
func.assign(x-1,id());
}
void update(int a,int b,int k,int l,int r,F f,F g){ //query(a,b,0,0,x/2,,id())
//[a,b) [l,r) ktreeindex
if(r<=a||b<=l){
func[k]=composition(g,func[k]);
tree[k]=mapping(func[k],tree[k]);
if(k<x/2-1){
func[2*k+1]=composition(func[k],func[2*k+1]);
func[2*k+2]=composition(func[k],func[2*k+2]);
}
func[k]=id();
return;
}//[l,r)[a,b)
if(a<=l&&r<=b){
func[k]=composition(composition(f,g),func[k]);
tree[k]=mapping(func[k],tree[k]);
if(k<x/2-1){
func[2*k+1]=composition(func[k],func[2*k+1]);
func[2*k+2]=composition(func[k],func[2*k+2]);
}
func[k]=id();
return;
}//[l,r)[a,b)
func[k]=composition(g,func[k]);
update(a,b,2*k+1,l,(r+l)/2,f,func[k]);
update(a,b,2*k+2,(r+l)/2,r,f,func[k]);
tree[k]=op(tree[2*k+1],tree[2*k+2]);
func[k]=id();
return;
}
S qu(int a,int b,int k,int l,int r,F f){ //query(a,b,0,0,x/2,id())
//[a,b) [l,r) ktreeindex
if(r<=a||b<=l){
func[k]=composition(f,func[k]);
tree[k]=mapping(func[k],tree[k]);
if(k<x/2-1){
func[2*k+1]=composition(func[k],func[2*k+1]);
func[2*k+2]=composition(func[k],func[2*k+2]);
}
func[k]=id();
return e();
}//[l,r)[a,b)
if(a<=l&&r<=b){
func[k]=composition(f,func[k]);
tree[k]=mapping(func[k],tree[k]);
if(k<x/2-1){
func[2*k+1]=composition(func[k],func[2*k+1]);
func[2*k+2]=composition(func[k],func[2*k+2]);
}
func[k]=id();
return tree[k];
}//[l,r)[a,b)
func[k]=composition(f,func[k]);
S ans=op(qu(a,b,2*k+1,l,(r+l)/2,func[k]),qu(a,b,2*k+2,(r+l)/2,r,func[k]));
tree[k]=op(tree[2*k+1],tree[2*k+2]);
func[k]=id();
return ans;
}
};
//
struct S{
int x;
};
S op(S l,S r){
//S×S→S
return S{l.x+r.x};
}
S e(){
//
return S{0};
}
struct F{
int a;
};
S mapping(F f,S prev){
//
if(f.a==0) return prev;
return {f.a};
}
F composition(F f,F g){
//f(g(x)) gf
if(f.a==0) return g;
return f;
}
F id(){
//
return F{0};
}
int main(){
int n; cin>>n;
lazysegment seg=lazysegment<S,op,e,F,mapping,composition,id>(n);
vi a(n);
map<int,vi> mp;
rep(i,0,n){
cin>>a[i];
mp[a[i]].push_back(i);
}
for(auto &[key,value]:mp){
seg.update(value[0],value[value.size()-1]+1,0,0,seg.x/2,F{key},id());
}
rep(i,0,n){
cout<<seg.qu(i,i+1,0,0,seg.x/2,id()).x<<" ";
}
cout<<endl;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0