제출 #345750

#제출 시각아이디문제언어결과실행 시간메모리
345750rrrr10000벽 (IOI14_wall)C++14
100 / 100
1886 ms203628 KiB
#include <bits/stdc++.h> using namespace std; #define rep(i, n) for(long long i=0;i<(long long)(n);i++) #define REP(i,k,n) for(long long i=k;i<(long long)(n);i++) #define all(a) a.begin(),a.end() #define rsort(a) {sort(all(a));reverse(all(a));} #define pb emplace_back #define eb emplace_back #define lb(v,k) (lower_bound(all(v),(k))-v.begin()) #define ub(v,k) (upper_bound(all(v),(k))-v.begin()) #define fi first #define se second #define pi M_PI #define PQ(T) priority_queue<T> #define SPQ(T) priority_queue<T,vector<T>,greater<T>> #define dame(a) {out(a);return 0;} #define decimal cout<<fixed<<setprecision(15); #define dupli(a) {sort(all(a));a.erase(unique(all(a)),a.end());} typedef long long ll; typedef pair<ll,ll> P; typedef tuple<ll,ll,ll> PP; typedef tuple<ll,ll,ll,ll> PPP; typedef multiset<ll> S; using vi=vector<ll>; using vvi=vector<vi>; using vvvi=vector<vvi>; using vvvvi=vector<vvvi>; using vp=vector<P>; using vvp=vector<vp>; using vb=vector<bool>; using vvb=vector<vb>; using vpp=vector<PP>; const ll inf=1001001001001001001; const ll INF=1001001001; const ll mod=1000000007; const double eps=1e-10; template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;} template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;} template<class T> void out(T a){cout<<a<<'\n';} template<class T> void outp(T a){cout<<'('<<a.fi<<','<<a.se<<')'<<'\n';} template<class T> void outvp(T v){rep(i,v.size())cout<<'('<<v[i].fi<<','<<v[i].se<<')';cout<<'\n';} template<class T> void outvvp(T v){rep(i,v.size())outvp(v[i]);} template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<'\n';} template<class T> void outvv(T v){rep(i,v.size())outv(v[i]);} template<class T> bool isin(T x,T l,T r){return (l)<=(x)&&(x)<=(r);} template<class T> void yesno(T b){if(b)out("yes");else out("no");} template<class T> void YesNo(T b){if(b)out("Yes");else out("No");} template<class T> void YESNO(T b){if(b)out("YES");else out("NO");} template<class T> void noyes(T b){if(b)out("no");else out("yes");} template<class T> void NoYes(T b){if(b)out("No");else out("Yes");} template<class T> void NOYES(T b){if(b)out("NO");else out("YES");} void outs(ll a,ll b){if(a>=inf-100)out(b);else out(a);} ll gcd(ll a,ll b){if(b==0)return a;return gcd(b,a%b);} ll modpow(ll a,ll b){ll res=1;a%=mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;} class segtree{ ll N=1; vvp seg; public: segtree(ll n){ while(N<n)N*=2; seg=vvp(N*2-1); } void add(ll k,P p){ if(p.se==2)seg[k]=vp(1,p); else if(seg[k].size()==0)seg[k].pb(p); else if(seg[k].size()==1){ if(seg[k][0].se==2){ if(p.fi*p.se>seg[k][0].fi*p.se)seg[k][0].fi=p.fi; } else if(seg[k][0].se==p.se){ if(p.fi*p.se>seg[k][0].fi*p.se)seg[k][0].fi=p.fi; } else if(p.fi*p.se>seg[k][0].fi*p.se)seg[k][0]=P(p.fi,2); else seg[k].pb(p); } else{ if(p.se!=seg[k][1].se)swap(seg[k][0],seg[k][1]); if(p.fi*p.se>seg[k][1].fi*p.se){ seg[k].pop_back();add(k,p); } } } void eval(ll k){ for(P p:seg[k])add(k*2+1,p); for(P p:seg[k])add(k*2+2,p); seg[k]=vp(0); } void update(P x,ll a,ll b,ll k=0,ll l=0,ll r=-1){ if(r==-1)r=N; if(a<=l&&r<=b){ add(k,x); return; } if(r<=a||b<=l)return; eval(k); update(x,a,b,k*2+1,l,(l+r)/2); update(x,a,b,k*2+2,(l+r)/2,r); } vi g(ll n){ vi res(n); rep(i,N-1)eval(i); rep(i,n){ for(auto x:seg[i+N-1]){ if(x.se==2)res[i]=x.fi; if(x.se==1)chmax(res[i],x.fi); if(x.se==-1)chmin(res[i],x.fi); } } return res; } }; void buildWall(int n,int k,int op[],int left[],int right[],int height[],int finalHeight[]){ segtree seg(n); rep(i,k)if(op[i]==2)op[i]=-1; rep(i,k)seg.update(P(height[i],op[i]),left[i],right[i]+1); vi res=seg.g(n); rep(i,n)finalHeight[i]=res[i]; } /* int main(){ ll n,k;cin>>n>>k; int op[100],l[100],r[100],h[100],res[100]; rep(i,k)cin>>op[i]>>l[i]>>r[i]>>h[i]; buildWall(n,k,op,l,r,h,res); rep(i,n)cout<<res[i]<<' '; }*/
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...