Submission #1195331

#TimeUsernameProblemLanguageResultExecution timeMemory
1195331vnedu허수아비 (JOI14_scarecrows)C++17
100 / 100
267 ms6336 KiB
#include<bits/stdc++.h> using namespace std; typedef long long ll; template<class T> bool maximize(T &a, const T &b){ return (a < b ? a = b, 1 : 0); } template<class T> bool minimize(T &a, const T &b){ return (a > b ? a = b, 1 : 0); } #define fi first #define se second #define pb push_back #define ii pair<int, int> #define all(x) x.begin(), x.end() #define TASK "nonsense" /// end of template /// mt19937 gen(std::chrono::steady_clock::now().time_since_epoch().count()); int rdint(int l, int r) { return uniform_int_distribution<int>(l,r)(gen); } const int N = 2e5 + 10; struct Point { int x,y; Point() {} void input() { cin>>x>>y; } bool operator < (const Point &S) const { return x<S.x; } } point[N]; int n,a[N],track[N],bit[N]; ii p[N]; vector<int> nen; ll dnc(int l, int r) { if(l==r) return 0; int mid((l+r)>>1); int ptr=0; for(int i=l;i<=r;++i) p[++ptr]={a[i],i}; sort(p+1,p+1+ptr); int num=0; ll ans=0; for(int tri=1;tri<=ptr;++tri) { int pos=p[tri].se; if(pos<=mid) { while(num>0 && track[num]<pos) --num; track[++num]=pos; } else { int mx=0; int x=pos; while(x>=mid+1) { maximize(mx,bit[x]); x-=x&-x; } int lo=1,hi=num,mid,cm=num+1; while(lo<=hi) { mid=(lo+hi)>>1; if(a[track[mid]]>mx) cm=mid,hi=mid-1; else lo=mid+1; } ans+=num-cm+1; x=pos; while(x<=r) { maximize(bit[x],a[pos]); x+=x&-x; } } } for(int i=mid+1;i<=r;++i) bit[i]=0; ans+=dnc(l,mid); ans+=dnc(mid+1,r); return ans; } void solve() { cin>>n; for(int i=1;i<=n;++i) point[i].input(); sort(point+1,point+1+n); for(int i=1;i<=n;++i) a[i]=point[i].y,nen.pb(a[i]); sort(all(nen)); nen.erase(unique(all(nen)),nen.end()); for(int i=1;i<=n;++i) a[i]=lower_bound(all(nen),a[i])-nen.begin()+1; cout<<dnc(1,n); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); // freopen(TASK".inp","r",stdin); // freopen(TASK".out","w",stdout); int testcase=1; // cin>>testcase; while (testcase--) solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...