結果
問題 | No.318 学学学学学 |
ユーザー |
![]() |
提出日時 | 2020-02-14 16:25:43 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 232 ms / 2,000 ms |
コード長 | 7,936 bytes |
コンパイル時間 | 2,153 ms |
コンパイル使用メモリ | 197,180 KB |
実行使用メモリ | 53,376 KB |
最終ジャッジ日時 | 2024-10-06 08:00:20 |
合計ジャッジ時間 | 6,873 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
#include "bits/stdc++.h"#include <unordered_set>#define rep(i,n) for(ll i = 0; i < n; i++)typedef long long ll;typedef unsigned long long ull;using namespace std;#define vll vector<vector<long long>>#define vl vector<long long>#define vi vector<int>#define vii vector<vector<int>>#define pb push_back#define pf push_front#define ld long double#define Sort(a) sort(a.begin(),a.end())#define cSort(a,cmp) sort(a.begin(),a.end(),cmp)#define reSort(a) sort(a.rbegin(), a.rend())static const ll llMAX = numeric_limits<long long>::max();static const int intMAX = numeric_limits<int>::max();static const ll llMIN = numeric_limits<long long>::min();static const int intMIN = numeric_limits<int>::min();static const ll d_5 = 100000;static const ll d9_7 = 1000000007;static const ll d_9 = 1000000000;static const double PI=3.14159265358979323846;template<class T>void Printvector(std::vector<T> a){int size = a.size();rep(i,size){cout<<a[i]<<" ";}cout<<endl;}template<class T>void Printvector(std::vector<std::vector<T>> a){int size = a.size();rep(i,size){int size2=a[i].size();rep(j,size2){cout<<a[i][j]<<" ";}cout<<endl;}cout<<endl;}ll digitpower(ll a,ll b){//aのb乗を計算if(b==1){return a;}else if(b==0){return 1;}int mode=0;if(b%2==1){ll tmp = digitpower(a,(b-1)/2);if(mode==1){tmp%=d9_7;}tmp*=tmp;if(mode==1){tmp%=d9_7;}tmp*=a;if(mode==1){return tmp%d9_7;}else{return tmp;}}else{ll tmp = digitpower(a,(b)/2);if(mode==1){tmp%=d9_7;}tmp*=tmp;if(mode==1){tmp%=d9_7;}if(mode==1){return tmp%d9_7;}else{return tmp;}}}vl facs(2000010,-1);ll Factrial(ll num){if(facs[num]!=-1){return facs[num];}if(num==1||num<=0){return 1;}else if(num<0){printf("ERROR_minus\n");return 0;}else{facs[num]=(num*Factrial(num-1))%d9_7;return facs[num];}}long long modinv(long long a, long long m) {//modの逆元long long b = m, u = 1, v = 0;while (b) {long long t = a / b;a -= t * b; swap(a, b);u -= t * v; swap(u, v);}u %= m;if (u < 0) u += m;return u;}vl invs(2000010,-1);ll linercomb(ll n,ll k, ll mod){//n,kの線形時間で求めるif(n<k)return 0;if(n<0)return 0;if(k==0 || k==n)return 1;ll ans=Factrial(n);if(invs[k]==-1){invs[k]=modinv(Factrial(k),mod);}ans*=invs[k];ans%=d9_7;ll k1=Factrial(n-k);k1%=mod;ans*=modinv(k1,mod);ans%=mod;return ans;}unordered_map<ll,ll> prime_factor(int64_t n) {unordered_map<ll,ll> ret;for(int64_t i = 2; i * i <= n; i++) {while(n % i == 0) {ret[i]++;n /= i;}}if(n != 1) ret[n] = 1;return ret;}template<class T>vector<T> getaccum(vector<T> a){int size=a.size();vector<T> ans(size);ans[0]=a[0];for(int i=0;i<size-1;i++){ans[i+1]=ans[i]+a[i+1];//ans[i+1]%=d9_7;}return ans;}ll getaccumnum(vector<ll> accum,int l,int r){//閉区間[l,r]の総和if(l==0){return accum[r];}else{return accum[r]-accum[l-1];}}struct datas{ll path;ll total;};/*bool cmp(const datas &a, const datas &b){return a.num < b.num;}*/struct opera{int x;int y;datas state;};int LCS(string s,string t) {int n=s.size();int m=t.size();vector<vector<int>> dp=vector<vector<int>>(n+1,vector<int>(m+1,0));for (int i=0; i<n; ++i) {for (int j=0; j<m; ++j) {if (s[i] == t[j]) {dp[i+1][j+1] = dp[i][j] + 1;}else {dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j]);}}}return dp[n][m];}template<class T>class delaySegmentTree{public:int n;vector<T> nodes;vector<T> delaynodes;//constructordelaySegmentTree(int size,T init){initialize(size,init);}//関数を定義(minなのかmaxなのかとか)T thisoperator(T a, T b){return max(a,b);}void update(int x,T a){//xがindexx+=n-1;nodes[x]=a;while(x>0){x=(x-1)/2;nodes[x]=thisoperator(nodes[2*x+1],nodes[2*x+2]);}}void initialize(int inputn,T init){int k=0;while(inputn>(1<<k)){k++;}n=(1<<k);nodes=vector<T> (n*2-1,init);delaynodes=vector<T> (n*2-1,-1);}// k 番目のノードについて遅延評価を行うvoid eval(int k, int l, int r) {//kが今見てるindex// 遅延配列が空でない場合、自ノード及び子ノードへの// 値の伝播が起こるif(delaynodes[k] != -1) {nodes[k] = max(delaynodes[k],nodes[k]);// 最下段かどうかのチェックをしよう// 子ノードは親ノードの 1/2 の範囲であるため、// 伝播させるときは半分にするif(r - l > 1) {delaynodes[2*k+1] = max(delaynodes[k],delaynodes[2*k+1]) ;delaynodes[2*k+2] = max(delaynodes[k],delaynodes[2*k+2]) ;}// 伝播が終わったので、自ノードの遅延配列を空にするdelaynodes[k] = -1;}}void maximaze(int a, int b, T x, int k=0, int l=0, int r=-1) {if(r < 0) r = n;// k 番目のノードに対して遅延評価を行うeval(k, l, r);// 範囲外なら何もしないif(b <= l || r <= a) return;// 完全に被覆しているならば、遅延配列に値を入れた後に評価if(a <= l && r <= b) {delaynodes[k] = max(x,delaynodes[k]);eval(k, l, r);}// そうでないならば、子ノードの値を再帰的に計算して、// 計算済みの値をもらってくるelse {maximaze(a, b, x, 2*k+1, l, (l+r)/2);maximaze(a, b, x, 2*k+2, (l+r)/2, r);nodes[k] = max(nodes[2*k+1] , nodes[2*k+2]);}}T sec_get(int reql,int reqr,int nowindex=0,int nowl=0,int nowr=-1){// 最初に呼び出されたときの対象区間は [0, n)//回区間に注意if(nowr < 0) nowr = n;// 要求区間と対象区間が交わらない -> 適当に返すif(nowr <= reql || reqr <= nowl) return 0;//関数が呼び出されるので評価eval(nowindex,nowl,nowr);// 要求区間が対象区間を完全に被覆 -> 対象区間を答えの計算に使うif(reql <= nowl && nowr <= reqr) return nodes[nowindex];// 要求区間が対象区間の一部を被覆 -> 子について探索を行う// 左側の子を vl ・ 右側の子を vr としている// 新しい対象区間は、現在の対象区間を半分に割ったものT val1 = sec_get(reql, reqr, 2*nowindex+1, nowl, (nowl+nowr)/2);T val2 = sec_get(reql, reqr, 2*nowindex+2, (nowl+nowr)/2, nowr);return thisoperator(val1, val2);}void Printn(){cout<<"Printvector"<<endl;for(int i=0;i<n;i++){cout<<nodes[i+n-1]<<" ";}cout<<endl;}};int main(void){int n;cin>>n;vl a(n);rep(i,n){cin>>a[i];}map<ll,set<int>,greater<ll>> nums;rep(i,n){if(nums.find(a[i])==nums.end()){nums.insert({a[i],{(int)i}});}else{nums[a[i]].insert(i);}}delaySegmentTree<ll> seg(n,(ll)0);rep(i,n){seg.update(i,a[i]);}/*for(auto itr=nums.begin();itr!=nums.end();){if(itr->second.size()==1){nums.erase(itr++);}else{itr++;}}*/for(auto i:nums){int l=*i.second.begin();int r=*--i.second.end();//cout<<l<<" "<<r<<" "<<i.first<<endl;seg.maximaze(l,r,i.first);}rep(i,n){cout<<seg.sec_get(i,i+1,0)<<" ";}cout<<endl;return 0;}//<<std::setprecision(30)w xd