Submission #945620

#TimeUsernameProblemLanguageResultExecution timeMemory
945620vjudge1trapezoid (balkan11_trapezoid)C++17
100 / 100
154 ms15488 KiB
#include<bits/stdc++.h> using namespace std; struct C{ int x=0,y=0; void operator+=(C z){ if(x<z.x) x=z.x,y=0; if(x==z.x) y=(y+z.y)%30013; } } T[1<<18],ans[1<<18],res; map<int,int> mp; int cnt; void upd(int x,C z){ while(x<=cnt) T[x]+=z,x+=x&-x; } C q(int x){ C z; while(x) z+=T[x],x-=x&-x; return z; } priority_queue<array<int,4>,vector<array<int,4>>,greater<>>pq; int main(){ cin.tie(0)->sync_with_stdio(0); int n; cin>>n; for(int i=0;i<n;i++){ int a,b,c,d; cin>>a>>b>>c>>d; pq.push({a,c,1,i}); pq.push({b,d,0,i}); mp[c],mp[d]; } for(auto&[i,j]:mp) j=++cnt; upd(1,{0,1}); while(pq.size()){ auto[a,b,c,d]=pq.top(); pq.pop(); if(c) ans[d]=q(mp[b]),ans[d].x++; else upd(mp[b],ans[d]); } for(int i=0;i<n;i++) res+=ans[i]; cout<<res.x<<' '<<res.y; }
#Verdict Execution timeMemoryGrader output
Fetching results...