Submission #1201883

#TimeUsernameProblemLanguageResultExecution timeMemory
1201883Warinchai허수아비 (JOI14_scarecrows)C++20
0 / 100
123 ms25960 KiB
#include<bits/stdc++.h> #define int long long using namespace std; //int mn[200005]; int inf=1e9+5; vector<pair<int,int>>v; vector<int>val; int ans=0; struct node{ int mx,mx2,fmx; node(int _mx=-inf,int _mx2=-inf,int _fmx=1){ mx=_mx,mx2=_mx2,fmx=_fmx; } friend node operator+(node a,node b){ node c; if(a.mx>b.mx){ c.mx=a.mx; c.fmx=a.fmx; c.mx2=max(a.mx2,b.mx); }else if(a.mx<b.mx){ c.mx=b.mx; c.fmx=b.fmx; c.mx2=max(a.mx,b.mx2); }else{ c.mx=a.mx; c.fmx=a.fmx+b.fmx; c.mx2=max(a.mx2,b.mx2); } return c; } }; struct segtree_beats{ node info[800005]; void pushmx(int st,int en,int i,int mx){ if(mx>info[i].mx)return; info[i].mx=mx; } void push(int st,int en,int i){ int m=(st+en)/2; if(st==en)return; pushmx(st,m,i*2,info[i].mx); pushmx(m+1,en,i*2+1,info[i].mx); } void chmin(int st,int en,int i,int l,int r,int val){ if(st>r||en<l||info[i].mx<val)return; if(st>=l&&en<=r&&val>info[i].mx2)return ans+=info[i].fmx,pushmx(st,en,i,val); push(st,en,i); int m=(st+en)/2; chmin(st,m,i*2,l,r,val); chmin(m+1,en,i*2+1,l,r,val); info[i]=info[i*2]+info[i*2+1]; } void upd(int st,int en,int i,int pos,int val){ push(st,en,i); if(st==en)return void(info[i].mx=val); int m=(st+en)/2; if(st<=m)upd(st,m,i*2,pos,val); else upd(m+1,en,i*2+1,pos,val); info[i]=info[i*2]+info[i*2+1]; } }tr; int32_t main(){ int n;cin>>n; for(int i=1;i<=n;i++){ int x,y;cin>>x>>y; v.push_back({x,y}); val.push_back(y); } sort(val.begin(),val.end()); sort(v.begin(),v.end()); //for(int i=0;i<n;i++)mn[i]=inf; for(int i=0;i<n;i++){ v[i].second=lower_bound(val.begin(),val.end(),v[i].second)-val.begin()+1; } for(int i=0;i<n;i++){ //cerr<<"i:"<<1<<" "<<v[i].second<<"\n"; tr.chmin(1,n,1,1,v[i].second-1,v[i].second); tr.upd(1,n,1,i,inf); //cerr<<ans<<"\n"; } cout<<ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...