Submission #940357

#	Time	Username	Problem	Language	Result	Execution time	Memory
940357		emad234	trapezoid (balkan11_trapezoid)	C++17	100 / 100	100 ms	23116 KiB

trapezoid

#include <bits/stdc++.h>
#define all(v) ((v).begin(),(v).end())
#define F first
#define S second
typedef long long ll;
#define pii pair<ll,ll>
using namespace std;
const ll mod = 30013;
const ll mxN = 4e6 + 5;
struct poll{
  ll u,d,id;
};
bool operator<(poll a,poll b){
  return a.u < b.u;
}
pii combine(pii a, pii b){
  if(a.F == b.F) return {a.F,(a.S + b.S) % mod};
  return max(a,b);
}
vector<poll>a;
bool vis[mxN];
pii dp[mxN];
pii seg[mxN];
ll s,e,N;
pii query(ll l = 1,ll r = N,ll ind = 1){
  if(l > e || r < s) return {0,0};
  if(l >= s && r <= e) return seg[ind];
  ll md = (l +r) / 2;
  return combine(query(l,md,ind * 2),query(md + 1,r,ind * 2 + 1));
}
void update(ll ind,pii val){
  ind += N;
  seg[ind] = val;
  while(ind /= 2){
    seg[ind] = combine(seg[ind * 2],seg[ind * 2 + 1]);
  }
}
signed main(){
  ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);
  vector<ll>c;
  ll n;
  cin >>n;
  for(ll i = 0;i < n;i++){
    ll x,x1,y,y1;
    cin >>x>>x1>>y>>y1;
    a.push_back({x,y,i});
    a.push_back({x1,y1,i});
  }
  sort(a.begin(),a.end());
  for(auto x : a){
    c.push_back(x.d);
  }
  ll mx = 0;
  sort(c.begin(),c.end());
  for(auto &x: a){
    x.d = lower_bound(c.begin(),c.end(),x.d) - c.begin() + 1;
    mx = max(mx,x.d);
  }
  N = exp2(ceil(log2(mx + 1)));
  pii ans = {0,0};
  for(auto x : a){
    if(!vis[x.id]){
      s = 1;e = x.d;
      pii ch = query();
      ch.F++;
      dp[x.id] = combine(ch,{1,1});
      ans = combine(ans,dp[x.id]);
    }else{
      update(x.d,dp[x.id]);
    }
    vis[x.id] = 1;
  }
  cout<<ans.F<<' '<<ans.S<<'\n';
}

• Subtask 1: 100 / 100