Submission #1125594

#TimeUsernameProblemLanguageResultExecution timeMemory
1125594Warinchai허수아비 (JOI14_scarecrows)C++20
0 / 100
389 ms50380 KiB
#include<bits/stdc++.h> #define int long long using namespace std; int inf=1e18; struct point{ int id,x,y; point(int _id=0,int _x=0,int _y=0){ id=_id,x=_x,y=_y; } friend bool operator<(point a,point b){ return a.x>b.x; } }; int val[200005]; struct segtree{ struct node{ int mn,mn2,mx,mx2,fmn,fmx; node(int _mn=inf,int _mn2=inf,int _mx=-inf,int _mx2=-inf,int _fmn=1,int _fmx=1){ mn=_mn,mn2=_mn2,mx=_mx,mx2=_mx2,fmn=_fmn,fmx=_fmx; } friend node operator+(node a,node b){ node c; c.mn=min(a.mn,b.mn); c.mx=max(a.mx,b.mx); c.fmn=(a.mn==b.mn?a.fmn+b.fmn:(a.mn<b.mn?a.fmn:b.fmn)); c.fmx=(a.mx==b.mx?a.fmx+b.fmx:(a.mx>b.mx?a.fmx:b.fmx)); c.mn2=(a.mn==b.mn?min(a.mn2,b.mn2):(a.mn<b.mn?min(a.mn2,b.mn):min(a.mn,b.mn2))); c.mx2=(a.mx==b.mx?max(a.mx2,b.mx2):(a.mx>b.mx?max(a.mx2,b.mx):max(a.mx,b.mx2))); return c; } }; node info[800005]; int ch[800005]; void push(int st,int en,int i){ if(!ch[i])return; if(ch[i]<=info[i].mn)return; info[i].mn=ch[i]; if(ch[i]>info[i].mx)info[i].mx=ch[i],info[i].mx2=-inf; else if(ch[i]>info[i].mx2)info[i].mx2=ch[i]; if(st!=en){ ch[i*2]=max(ch[i],ch[i*2]); ch[i*2+1]=max(ch[i],ch[i*2+1]); } ch[i]=0; } void build(int st,int en,int i){ if(st==en)return void(info[i]=node(inf,inf,inf,-inf)); int m=(st+en)/2; build(st,m,i*2); build(m+1,en,i*2+1); info[i]=info[i*2]+info[i*2+1]; } int chmax(int st,int en,int i,int l,int r,int val){ push(st,en,i); if(st>r||en<l||val<=info[i].mn)return 0; if(st>=l&&en<=r&&val<info[i].mn2){ //cerr<<st<<" "<<en<<" "<<info[i].mn<<" "<<info[i].mn2<<":"<<val<<"\n"; ch[i]=val; push(st,en,i); return info[i].fmn; } int m=(st+en)/2; int tans=chmax(st,m,i*2,l,r,val)+chmax(m+1,en,i*2+1,l,r,val); info[i]=info[i*2]+info[i*2+1]; return tans; } void upd(int st,int en,int i,int pos,int val){ push(st,en,i); if(st>pos||en<pos)return; if(st==en)return void(info[i]=node(val,inf,val,-inf)); int m=(st+en)/2; upd(st,m,i*2,pos,val); upd(m+1,en,i*2+1,pos,val); info[i]=info[i*2]+info[i*2+1]; } }tr; int32_t main(){ ios_base::sync_with_stdio(false); cin.tie(0); int n;cin>>n; vector<point>p; vector<int>y; for(int i=0;i<n;i++){ int a,b;cin>>a>>b; p.push_back(point(i,a+1,b+1)); y.push_back(b+1); } sort(p.begin(),p.end()); sort(y.begin(),y.end()); int ans=0; tr.build(1,n,1); for(int i=0;i<p.size();i++){ int id=lower_bound(y.begin(),y.end(),p[i].y)-y.begin()+1; //cerr<<"chmax:\n"; ans+=tr.chmax(1,n,1,id+1,n,id); //cerr<<p[i].id<<" "<<ans<<" "<<id<<"\n"; tr.upd(1,n,1,id,0); } cout<<ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...